数据结构与算法之归并排序

归并排序（Merge Sort）

归并排序的核心思想并不复杂，要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

看下面的例子：

数组初始顺序[3, 2, 6, 10, 7, 1, 5, 8]

[3, 2, 6, 10, 	7, 1, 5, 8]	|	初始数组
[3, 2, 6, 10]	[7, 1, 5, 8]	|	拆分任务
[3, 2][6, 10]	[7, 1][5, 8]	|	拆分任务
-------------排序-----------
[2, 3][6, 10]	[1, 7][5, 8]	|	比较合并
[2, 3, 6, 10]	[1, 5, 7, 8]	|	比较合并
[1, 2, 3, 5, 6, 7, 8, 10]	|	比较合并,最终结果

归并排序使用的就是分治思想
分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。
小的子问题解决了，大问题也就解决了。

代码：

public static void sort(int[] arrs, int p, int r) {
        if(p>=r) {return;}
        int q = (p+r)/2;
        sort(arrs, p, q);
        sort(arrs, q+1, r);
        merge(arrs, p, q, r);
    }

    public static void merge(int[] arrs, int left, int mid, int right) {
        int[] temp = new int[right-left+1];
        int i=left, j=mid+1, k=0;
        while(i<=mid && j<=right) {
            if(arrs[i]<=arrs[j]) {
                temp[k] = arrs[i];
                i++;
            } else {
                temp[k] = arrs[j];
                j++;
            }
            k++;
        }

        //判断哪个数据中有剩余数据
        int start=i,end=mid;
        if(j<=right) {
            start = j;
            end = right;
        }

        //将剩余数据拷贝到临时数组
        while(start<=end) {
            temp[k] = arrs[start];
            k++;start++;
        }

        //将temp中的数据拷贝回原来的数组
        k=0;
        while(left <= right){
            arrs[left++] = temp[k++];
        }

        System.out.println();
        System.out.println("排序后的数组:");
        Arrays.stream(arrs).forEach(x->System.out.print(x + " "));
        
    }

输出：

排序前的数组:
6 2 7 1 2 10 3 
排序中间结果:
2 6 7 1 2 10 3 
排序中间结果:
2 6 1 7 2 10 3 
排序中间结果:
1 2 6 7 2 10 3 
排序中间结果:
1 2 6 7 2 10 3 
排序中间结果:
1 2 6 7 2 3 10 
排序中间结果:
1 2 2 3 6 7 10 
排序后的数组:
1 2 2 3 6 7 10 

归并排序的时间复杂度是 O(nlogn)，空间复杂度为O(n)。