算法通关村第十关—归并排序(黄金)

????????归并排序

一、归并排序原理

?归并排序(MERGE-SORT)简单来说就是将大的序列先视为若干个比较小的数组，分成几个比较小的结构，然后是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分就是将问题分(divide)成一些小的问题分别求解，而治(conquer).则将分的阶段得到的各答案"合"在一起)。

?可以看到这种结构很像两棵套在一起的满二叉树。分阶段可以理解为就是递归拆分子序列的过程，递归深度为logn。就是图中上面侧的满二叉树。
?再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，就是下侧的满二叉树。比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，这个操作与合并两个有序数组的完全一样，不同的是这里是将数组的两个部分合并。
?再看一下遍历时处理元素的过程：

二、代码实现

static void mergeSort(int[] array,int start,int end,int temp[]){
    if (start > end){
        return;
    }
    mergeSort(array,start,(start+end)/2,temp);
    mergeSort(array,(start+end)/2 + 1,end,temp);
    merge(array,start,end,temp);
    static void merge(int[] array,int start,int end,int[] temp){
        int middle = (start + end)/2;
        int left = start;
        int right = middle + 1;
        int index = left;
        while(left <= middle && right <= end){
            if (array[left] < array[right]){
                temp[index++] = array[left++];
            }
            else{
                temp [index++] = array[right++];
            }
        }
        while (left <= middle){
            temp[index++] = array[left++];
        }
        while (right <= end){
            temp[index++] = array[right++];
            for (int i = start; i <= end;i++){
                array[i] = temp[i];
            }
        }

        //测试方法
        public static void main(String[]args){
            int[] array = {6,3,2,1,4,5,8,7};
            int[]temp = new int[array.length];
            mergeSort(array,0,array.length - 1,temp);
            System.out.println(Arrays.toString(array));
        }