AcWing 787. 归并排序（模板）

活动 - AcWing

 

【归并排序】和快排一样也是分治的思想

（1）确定分界点

（2）分界点两侧分别排序

（3）合并两个排好序的数组

（4）复制回原数组中

妥妥的O(nlogn)的时间复杂度，合并需要用O(n)的时间，共logn层

package AcWing.course;
import java.io.StreamTokenizer;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class _787_归并排序_1 {

    // 8：38 8:50
    static int n;
    static int[] arr, tmp;
    static StreamTokenizer st;

    static int nextInt() throws Exception {
        st.nextToken();
        return (int)st.nval;
    }

    static void mergeSort(int l, int r){
        if(l >= r) return;
        int mid = (l + r) >>> 1, i = l, j = mid + 1, k = 0;
        mergeSort(l, mid); mergeSort(mid + 1, r);
        while(i <= mid && j <= r){
            if(arr[i] <= arr[j]) tmp[k++] = arr[i++];
            else tmp[k++] = arr[j++];
        }
        while(i <= mid) tmp[k++] = arr[i++];
        while(j <= r) tmp[k++] = arr[j++];
        for(i = l, j = 0; j < k; j++, i++) arr[i] = tmp[j];
    }

    public static void main(String[] args) throws Exception {
        st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter pw = new PrintWriter(System.out);
        n = nextInt();
        arr = new int[n];
        tmp = new int[n];
        for(var i = 0; i < n; i++) arr[i] = nextInt();
        mergeSort(0, n - 1);
        for(var x: arr){
            pw.print(x);
            pw.print(" ");
        }
        pw.flush();
    }

}