閱讀經典——《算法導論》02

不同算法中往往蘊含著通用的思想，分治法就是最常用的一種。

分治法使用遞歸的方式，將原問題分解為幾個規(guī)模較小但類似于原問題的子問題，遞歸地求解這些子問題，然后再合并這些子問題的解從而得到原問題的解。

仍然考慮排序問題，本文將要介紹的歸并排序就是使用分治法的典型案例。

思路：
把待排序數組從中間分割為兩個子數組，這兩個子數組分別排序，排完序后再把它們合并起來。該思路的關鍵在于子數組如何排序，以及如何把排完序的兩個子數組合并起來。

第一個問題，分治法的精髓就在于把大問題分解為小問題，因此子數組仍然要使用歸并排序，這是一個遞歸的過程。遞歸結束的條件是問題不能進一步分解，即數組只有一個元素。

第二個問題，排完序的兩個子數組只需要同時遍歷一遍就可以合并起來，這不是什么困難的事情。

整個算法從細分到合并的詳細過程如下圖所示。

歸并排序分解步驟

歸并排序的動畫演示如下圖：

歸并排序

算法：

/**
 * 歸并排序，排序結果仍保存于arr數組中。
 * @param arr 需要排序的數組
 */
public void mergeSort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1);
}

/**
 * 歸并排序，排序arr數組中[p..r]的子數組，排序結果仍保存于arr數組中。
 * @param arr 需要排序的數組
 * @param p 待排序數組的起始下標
 * @param r 待排序數組的終止下標
 */
public void mergeSort(int[] arr, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(arr, p, q);
        mergeSort(arr, q + 1, r);
        merge(arr, p, q, r);
    }
}

/**
 * 歸并已排序的兩個子序列。
 * @param arr 待歸并的序列
 * @param p 第一個子序列的起始下標
 * @param q 第一個子序列的結束下標
 * @param r 第二個子序列的結束下標
 */
public void merge(int[] arr, int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int[] arrL = new int[n1 + 1];
    int[] arrR = new int[n2 + 1];
    for (int i=0; i<n1; i++) {
        arrL[i] = arr[p + i];
    }
    for (int i=0; i<n2; i++) {
        arrR[i] = arr[q + 1 + i];
    }
    arrL[n1] = Integer.MAX_VALUE;
    arrR[n2] = Integer.MAX_VALUE;
    int i = 0;
    int j = 0;
    for (int k = p; k <= r; k++) {
        if (arrL[i] <= arrR[j]) {
            arr[k] = arrL[i];
            i++;
        }
        else {
            arr[k] = arrR[j];
            j++;
        }
    }
}

mergeSort是用于遞歸調用的歸并排序函數，merge是用于合并已排序序列的函數。它們的詳細用法在代碼注釋里已經寫得很清楚，此處不再贅述。

完整代碼請參考MergeSort.java。

分析：
最后分析一下該算法的時間復雜度。歸并排序采用了二等分的分治策略，因此每一級分治使問題規(guī)模減小一半，所以直到問題規(guī)模減小到1時應該經歷了lgn級分治。每一級的歸并操作需要Θ(n)的執(zhí)行時間，因此總執(zhí)行時間為Θ(nlgn)。

與上一篇文章提到的插入排序相比，歸并排序的時間復雜度已經降低了很多，在輸入規(guī)模n很大的情況下，兩者的耗時差距非常大。

關注作者或文集《算法導論》，第一時間獲取最新發(fā)布文章。

獲取文集中的全套源碼請訪問GitHub代碼倉庫Algorithm。