归并排序（二路归并排序）

归并排序的思路

归并排序是通过“归并”操作完成排序的，将两个或者多个有序子表归并成一个子表。归并排序是“分治法”的一个非常典型的应用，同事它也是递归算法的一个好的实例。它将问题分成一些小的问题然后递归求解，而治就是把分阶段的答案拼起来。

二路归并排序

• 基本思想
  二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并：两个有序表放在同一数组的相邻位置上，arr[left]到arr[center-1]为第一个有序表，arr[center]到arr[right]是第二个有序表。每次从两端中取出一个进行比较，小的先放在一个temp数组，最后将比较剩下的直接放到temp中去，最后将temp又复制回arr。这是“治”。
  下面说“分”，只需要递归地将前半部分和后半部分的数据各自归并排序即可。

• 例子
  {3,6,1,7,9,4,5,8,2}
  二路归并排序的过程如图所示：

  
  1.jpeg

• 算法分析
  每一趟归并的时间复杂度为O(n)，共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外，归并排序中归并的算法并不会将相同关键字的元素改变相对次序，所以归并排序是稳定的。

public class MergeSort {
    public static void main(String args[]) {
        int a[] = {3, 6, 1, 7, 9, 4, 5, 8, 2};
        mergeSort(a);
        System.out.println("排序后：" + Arrays.toString(a));
    }

    private static void mergeSort(int[] arr) {
        mergeSort(arr, new int[arr.length], 0, arr.length - 1);
    }

    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(arr, temp, left, center); // 左边
            mergeSort(arr, temp, center + 1, right); // 右边
            merge(arr, temp, left, center + 1, right); // 合并两个有序
        }
    }

    /**
     * 将两个有序表归并成一个有序表
     *
     * @param arr
     * @param temp     临时数组
     * @param leftPos  左边开始下标
     * @param rightPos 右边开始下标
     * @param rightEnd 右边结束下标
     */
    private static void merge(int[] arr, int[] temp, int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1; // 左边结束下标
        int tempPos = leftPos; // 从左边开始算
        int numEle = rightEnd - leftPos + 1; // 元素个数
        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (arr[leftPos] <= arr[rightPos])
                temp[tempPos++] = arr[leftPos++];
            else
                temp[tempPos++] = arr[rightPos++];
        }
        while (leftPos <= leftEnd) {  // 左边如果有剩余
            temp[tempPos++] = arr[leftPos++];
        }
        while (rightPos <= rightEnd) { // 右边如果有剩余
            temp[tempPos++] = arr[rightPos++];
        }
        // 将temp复制到arr
        for (int i = 0; i < numEle; i++) {
            arr[rightEnd] = temp[rightEnd];
            rightEnd--;
        }
    }
}