摘要：今天再來看看另外三種時間復雜度都是的排序算法，分別是希爾排序歸并排序和快速排序。三數(shù)取中法求將放到數(shù)組的末尾總結這三種排序算法的平均時間復雜度都是，歸并排序和快速排序的應用更廣泛。

1. 回顧

前面說完了三種較為簡單的排序算法，分別是冒泡排序，選擇排序和插入排序，它們的平均情況時間復雜度都是 O(n²)，比較的高，適合小規(guī)模的數(shù)據(jù)排序，其中插入排序的效率稍高，所以更推薦使用插入排序。今天再來看看另外三種時間復雜度都是 O(nlogn) 的排序算法，分別是希爾排序、歸并排序和快速排序。其中后兩者的應用非常的廣泛。

2. 希爾排序

先來看看希爾排序，它是較早突破 O(n²) 的時間復雜度的算法之一，其實是對插入排序的一種優(yōu)化。前面說到的插入排序，操作非常的機械，就是按照固定順序逐步比較大小，但是遇到一些比較極端的情況，數(shù)據(jù)移動的操作就會很頻繁，比如排序數(shù)組 [3, 5, 1, 7, 9, 0] ，要將最后的 0 移動到最前面，幾乎會遍歷整個數(shù)組。

所以，希爾排序對此進行了優(yōu)化，采用一種分組策略，來縮小數(shù)據(jù)的移動，使數(shù)組整體是基本有序的，小的在前，大的在后，然后縮小增量，這樣數(shù)據(jù)的移動就會比較的少。

結合圖來理解一下：

先將數(shù)組分為 4 組，分別進行插入排序，然后再分為 2 組，再進行插入排序。最后分為一組，即數(shù)組本身，因為此時數(shù)據(jù)已經基本上是有序的了，所以只需要進行微調即可。

下面是它的代碼實現(xiàn)：

public class ShellSort {

    public static void shellSort(int[] data) {
        int length = data.length;
        if (length <= 1) return;

        //確定增量
        int gap = length / 2;
        while (gap >= 1){
            for (int i = gap; i < length; i++) {
                int value = data[i];
                int j = i - gap;
                for (; j >= 0; j -= gap){
                    if (data[j] > value) data[j + gap] = data[j];
                    else break;
                }
                data[j + gap] = value;
            }
            //更新增量
            gap = gap / 2;
        }
    }
}

希爾排序并沒有很廣泛的應用，原因是比起歸并排序，它是不穩(wěn)定的，比起快速排序，它的執(zhí)行效率稍低。

3. 歸并排序

歸并排序大致分為兩個步驟，一是拆分，二是合并。將數(shù)組拆分為許多小的數(shù)組，將小的數(shù)組排序了，然后合并為大數(shù)組。這種思想叫做分治，即將一個大的問題分解成小的問題來解決。用到分治思想的問題大多可以使用遞歸這種編程技巧。

下面是它的圖展示：

結合圖分析，假如我們要排序 data[p - r] 這個數(shù)組，可以先排序 data[p - q] 和 data[q+1 - r]，然后進行合并。用公式可以這樣表示：
merge_sort(data[p - r]) = merge(merge_sort(data[p - q]), merge_sort(data[q+1 - r]));

其中 merge 函數(shù)的作用是將兩個已排序的數(shù)組進行合并，那么 merge 函數(shù)該如何表示呢？

思路其實很簡單，新建一個臨時數(shù)組，分別從頭開始掃描兩個子數(shù)組，比較大小，將小的放入到臨時數(shù)組中，然后指針向后移，繼續(xù)比較。你可以結合歸并排序的代碼實現(xiàn)來理解：

public class MergeSort {

    public static void mergeSort(int[] data) {
        mergeInternally(data, 0, data.length - 1);
    }

    private static void mergeInternally(int[] data, int p, int r){
        if (p >= r) return;

        //計算p到r的中間值
        int q = p + ((r - p) >> 1);
        //遞歸分解
        mergeInternally(data, p, q);
        mergeInternally(data, q + 1, r);
        //合并已排序數(shù)組
        merge(data, p, q, r);
    }

    private static void merge(int[] data, int p, int q, int r){
        int i = p;
        int j = q + 1;
        int k = 0;
        //初始化一個臨時數(shù)組
        int[] temp = new int[r - p + 1];
        while (i <= q && j <= r){
            if (data[i] <= data[j]) temp[k ++] = data[i ++];
            else temp[k ++] = data[j ++];
        }
        //判斷哪個數(shù)組中有剩余的數(shù)據(jù)
        int start = i;
        int end = q;
        if (j <= r){
            start = j;
            end = r;
        }
        //將剩余的數(shù)據(jù)拷貝到temp中
        while (start <= end){
            temp[k ++] = data[start ++];
        }
        //將temp拷貝到data中
        for (int t = 0; t <= r - p; t ++) {
            data[p + t] = temp[t];
        }
    }
}

4. 快速排序

快速排序的思路和上面的歸并排序很類似，都用到了分治的思想，在數(shù)組中選取一個分區(qū)點，將大于分區(qū)點的數(shù)放在右邊，小于分區(qū)點放在左邊。然后依次遞歸完成排序。

在歸并排序中有一個 merge 合并函數(shù)，在快速排序中有一個 partition 分區(qū)函數(shù)，這個函數(shù)的主要功能是選取分區(qū)點，然后將大于分區(qū)點的數(shù)據(jù)放在右邊，小的放在左邊，返回分區(qū)點下標。實現(xiàn)這個函數(shù)的思路比較的巧妙：

對于數(shù)組 data[p - r]，我們選取最后一個數(shù)據(jù) data[r] 作為分區(qū)點，用兩個指針 i，j 都指向數(shù)組第一個元素，如果 data[j] < data[r]，交換 data[i] 和 data[j] 的位置，i 和 j 都向前移動。如果 data[j] > data[r]，則不交換，i 不動，j 向前移動，直至到達數(shù)組末尾。

對于分區(qū)點的選擇，其實直接選擇數(shù)組的最后一個元素是有問題的，在極端的情況下，數(shù)組本來就是有序的，那么每次分區(qū)都會遍歷整個數(shù)組，時間復雜度就退化為 O(n²) 了。我們的理想是，大于分區(qū)點和小于分區(qū)點的數(shù)據(jù)是均勻分布的，不會出現(xiàn)太多或太少的情況。

這里提供了另外兩種解決辦法：一是三數(shù)取中法，就是取數(shù)組中的頭、中、尾三個數(shù)，比較大小，取中間大小的數(shù)作為分區(qū)點。二是隨機法，即隨機選取一個數(shù)作為分區(qū)點。我下面的代碼實現(xiàn)便是使用的三叔取中法。

public class QuickSort {
    public static void quickSort(int[] data){
        quickSortInternally(data, 0, data.length - 1);
    }

    private static void quickSortInternally(int[] data, int p, int r){
        if (p >= r) return;
        int q = partition(data, p, r);

        quickSortInternally(data, p, q - 1);
        quickSortInternally(data, q + 1, r);
    }

    private static int partition(int[] data, int p, int r) {
        //三數(shù)取中法求pivot
        int q = p + ((r - p) >> 1);
        int mid = 0;
        if ((data[p] - data[q]) * (data[q] - data[r]) >= 0) mid = q;
        else if ((data[q] - data[p]) * (data[p] - data[r]) >= 0) mid = p;
        else mid = r;

        int pivot = data[mid];
        //將pivot放到數(shù)組的末尾
        swap(data, mid, r);

        int i = p;
        for (int j = p; j < r; j ++){
            if (data[j] < pivot){
                swap(data, i, j);
                i ++;
            }
        }
        swap(data, i, r);
        return i;
    }

    private static void swap(int[] data, int i, int j){
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

5. 總結

這三種排序算法的平均時間復雜度都是 O(nlogn) ，歸并排序和快速排序的應用更廣泛。

希爾排序和快速排序是不穩(wěn)定的，沒有借助額外的存儲空間，因此空間復雜度是 O(1) 。

歸并排序是穩(wěn)定的，使用了臨時數(shù)組，大小和排序數(shù)組大小相同，因此空間復雜度是 O(n) 。