归并排序

一、思路

说明:可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。

二、结论

1. 当左边的下标小于右边下标时，可以进行拆分，左边拆完拆右边
2. 当左右两边拆分到只有单个元素时，方可进行合并。
3. 合并时要知道每组的中间下标，中间下标两边的值进行比较，然后存放到temp临时数组中
4. 把有剩余数据的一边的数据依次全部填充到temp
5. 将temp数组的元素拷贝到array
6. 注意，并不是每次都拷贝所有
7. debug多跑几次，思路更清晰

三、代码

public class MergeSort {
    public static void main(String[] args) {
        int[] array = new int[]{ 8, 4, 5, 7, 1, 3, 6, 2 };
        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){
            int mid = (left + right) / 2;
            // 分左边的
            mergeSort(array, left, mid, temp);
            // 分右边的
            mergeSort(array, mid+1, right, temp);
            // 
            merge(array,left,mid, right ,temp);
        }
    }
        //合并的方法
    /**
     * 
     * @param array 排序的原始数组
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param temp 做中转的数组
     */
    public static void merge(int[] array, int left,int mid, int right, int[] temp){
//        int mid  = (left + right) / 2;
        int i = left; // 初始化i, 左边有序序列的初始索引
        int j = mid + 1; //初始化j, 右边有序序列的初始索引
        int t = left;// 指向temp数组的当前索引

        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i < mid + 1 && j <= right){
                //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
            //即将左边的当前元素，填充到 temp数组 
            //然后 t++, i++
            if (array[i] < array[j]){
                temp[t] = array[i];
                i += 1;
                t += 1;
            }else {
                temp[t] = array[j];
                j += 1;
                t += 1;
            }
        }

        //(二)
        //把有剩余数据的一边的数据依次全部填充到temp
        while (i < mid +1){//左边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] = array[i];
            i += 1;
            t += 1;
        }
        while (j <= right){
            temp[t] = array[j];
            j += 1;
            t += 1;
        }

        //(三)
        //将temp数组的元素拷贝到arr
        //注意，并不是每次都拷贝所有
        int tempLift = left;
        //第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
        //最后一次 tempLeft = 0  right = 7
        while (tempLift <= right){
            array[tempLift] = temp[tempLift];
            tempLift += 1;
        }
    }


}