歸并排序的思路

歸并排序是通過“歸并”操作完成排序的，將兩個或者多個有序子表歸并成一個子表。歸并排序是“分治法”的一個非常典型的應(yīng)用，同事它也是遞歸算法的一個好的實例。它將問題分成一些小的問題然后遞歸求解，而治就是把分階段的答案拼起來。

二路歸并排序

• 基本思想
  二路歸并排序就是將兩個有序子表歸并成一個有序表。首先我們得有一個算法用于歸并：兩個有序表放在同一數(shù)組的相鄰位置上，arr[left]到arr[center-1]為第一個有序表，arr[center]到arr[right]是第二個有序表。每次從兩端中取出一個進(jìn)行比較，小的先放在一個temp數(shù)組，最后將比較剩下的直接放到temp中去，最后將temp又復(fù)制回arr。這是“治”。
  下面說“分”，只需要遞歸地將前半部分和后半部分的數(shù)據(jù)各自歸并排序即可。

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

  
  
  1.jpeg

• 算法分析
  每一趟歸并的時間復(fù)雜度為O(n)，共需要進(jìn)行?log2n?趟。對應(yīng)的算法的時間復(fù)雜度為O(nlog2n)。歸并排序的空間復(fù)雜度O(n)。另外，歸并排序中歸并的算法并不會將相同關(guān)鍵字的元素改變相對次序，所以歸并排序是穩(wě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     臨時數(shù)組
     * @param leftPos  左邊開始下標(biāo)
     * @param rightPos 右邊開始下標(biāo)
     * @param rightEnd 右邊結(jié)束下標(biāo)
     */
    private static void merge(int[] arr, int[] temp, int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1; // 左邊結(jié)束下標(biāo)
        int tempPos = leftPos; // 從左邊開始算
        int numEle = rightEnd - leftPos + 1; // 元素個數(shù)
        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復(fù)制到arr
        for (int i = 0; i < numEle; i++) {
            arr[rightEnd] = temp[rightEnd];
            rightEnd--;
        }
    }
}