ACWing787. 归并排序

原题链接：https://www.acwing.com/problem/content/789/

1. 思路

①确定分界点mid，mid为区间 l 到 r 的中间位置上面的点

②递归排序左右两边

③将排序好的左右两边合并 (难点)

2. 代码模板

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()) {
            int n = in.nextInt();
            int[] a = new int[n];
            for(int i = 0; i < n; i++)
                a[i] = in.nextInt();
            merge_Sort(a, 0, n - 1);
            for(int i : a)
                System.out.print(i + " ");
            System.out.println();
        }
        in.close();
    }
    //a为要排序数组,l为左边界，r为右边界
    public static void merge_Sort(int[] a, int l, int r) {
        if(l >= r) return;		//如果区间只有一个元素，或者没有元素直接返回
        int mid = l + r >> 1;	//取区间[l,r]中间位置的点，（l + r >> 1）=>(l + r)/2,两者等价，位运算更加快
        merge_Sort(a, l, mid);		//递归排序左边，以中间点为分界点
        merge_Sort(a, mid + 1, r);	//递归排序右边
        int[] n = new int[r - l + 1];	//创建一个临时数组，用于保存归并之后的数组
        int i = l, j = mid + 1;		//要合并的两个数组开始的位置
        int k = 0;					//记录临时的下标
        while(i <= mid && j <= r) {		//合并数组
            if(a[i] < a[j])			//从小到大排序
                n[k++] = a[i++];
            else
                n[k++] = a[j++];
        }
        while(i <= mid)				
            n[k++] = a[i++];
        while(j <= r)
            n[k++] = a[j++];
        for(int t = 0; t < k; t++)		//将排序并合并完的临时数组保存到原数组中
            a[l + t] = n[t];
    }
}

3. 复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)