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

1. 回顧

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

2. 希爾排序

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

所以，希爾排序?qū)Υ诉M(jìn)行了優(yōu)化，采用一種分組策略，來(lái)縮小數(shù)據(jù)的移動(dòng)，使數(shù)組整體是基本有序的，小的在前，大的在后，然后縮小增量，這樣數(shù)據(jù)的移動(dòng)就會(huì)比較的少。

結(jié)合圖來(lái)理解一下：

先將數(shù)組分為 4 組，分別進(jìn)行插入排序，然后再分為 2 組，再進(jìn)行插入排序。最后分為一組，即數(shù)組本身，因?yàn)榇藭r(shí)數(shù)據(jù)已經(jīng)基本上是有序的了，所以只需要進(jìn)行微調(diào)即可。

下面是它的代碼實(shí)現(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;
        }
    }
}

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

3. 歸并排序

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

下面是它的圖展示：

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

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

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

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;

        //計(jì)算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;
        //初始化一個(gè)臨時(shí)數(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 ++];
        }
        //判斷哪個(gè)數(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ù)組中選取一個(gè)分區(qū)點(diǎn)，將大于分區(qū)點(diǎn)的數(shù)放在右邊，小于分區(qū)點(diǎn)放在左邊。然后依次遞歸完成排序。

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

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

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

這里提供了另外兩種解決辦法：一是三數(shù)取中法，就是取數(shù)組中的頭、中、尾三個(gè)數(shù)，比較大小，取中間大小的數(shù)作為分區(qū)點(diǎn)。二是隨機(jī)法，即隨機(jī)選取一個(gè)數(shù)作為分區(qū)點(diǎn)。我下面的代碼實(shí)現(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. 總結(jié)

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

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

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