归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

思路分析

归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{4,6,3,7,5,9,2,0}
初始状态：4,6,3,7,5,9,2,0
第一次归并后：{4,6},{3,7},{5,9},{0,2}
第二次归并后：{3,4,6,7}，{0,2,5,9}
第三次归并后：{0,2,3,4,5,6,7,9}

#代码实现

public class MergeSort {
    public static void main(String[] args) {
        int[] array = {4,6,3,7,5,9,2,0};
        int[] temp = new int[array.length];
        mergeSort(array,0,array.length-1,temp);
        System.out.println(Arrays.toString(array));
    }
    public static void mergeSort(int[] array,int left,int right,int[] temp){
        if (left<right){ //递归结束的条件 如果left小于right就继续分割
            int mid = (left+right)/2;
            //分割左边部分
            mergeSort(array,left,mid,temp);
            //分割右边部分
            mergeSort(array,mid+1,right,temp);
            //合并
            sum(array,left,mid,right,temp);
        }
    }
    public static void sum(int[] array,int left,int mid,int right,int[] temp){
        int l = left;
        int r = mid+1;
        int index = 0;
        while(l<=mid && r<=right){
            if (array[l] <= array[r]){
                temp[index] = array[l];
                index++;
                l++;
            }else {
                temp[index] = array[r];
                index++;
                r++;
            }
        }
        while(l<=mid){
            temp[index] = array[l];
            index++;
            l++;
        }
        while(r<=right){
            temp[index] = array[r];
            index++;
            r++;
        }
        int tempIndex = left;
        int k = 0;
        while(tempIndex<=right){
            array[tempIndex] = temp[k];
            tempIndex++;
            k++;
        }
    }
}

结果输出

[0, 2, 3, 4, 5, 6, 7, 9]
Process finished with exit code 0