排序指的是將一組對(duì)象按照特定的邏輯順序重新排列的過(guò)程，排序的應(yīng)用十分廣泛，可以說(shuō)是無(wú)處不在，它在商業(yè)數(shù)據(jù)處理和現(xiàn)代科學(xué)計(jì)算中發(fā)揮著舉足輕重的作用漆魔，目前已知的應(yīng)用最廣泛的排序算法—快速排序，更是被譽(yù)為了 20 世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一却音。

排序算法有很多改抡，有比較常見(jiàn)的有比如插入排序、歸并排序系瓢、快速排序阿纤，就是我接下來(lái)會(huì)講解的這幾種；也有一些非常冷門(mén)的排序算法八拱，有一些可能你連名字都沒(méi)聽(tīng)過(guò)，例如雞尾酒排序涯塔、侏儒排序肌稻、圖書(shū)館排序、耐心排序匕荸、臭皮匠排序等等……

這篇文章的篇幅較長(zhǎng)爹谭，涉及到大量圖例、證明榛搔、代碼示例诺凡，一次性全部看完可能有點(diǎn)困難，可以分幾次多看幾遍践惑，自己思考一下腹泌，結(jié)合一些經(jīng)典書(shū)籍資料等等，相信看完之后你對(duì)排序算法的認(rèn)識(shí)會(huì)有很大的提升尔觉。

在開(kāi)始講解之前凉袱，先定義一個(gè)游戲規(guī)則，為了復(fù)用部分代碼侦铜，我寫(xiě)了一個(gè)排序的抽象類(lèi)专甩，當(dāng)然你可以轉(zhuǎn)換成任何你熟悉的編程語(yǔ)言，如下：

public abstract class AbstractSort {

    public abstract void sort(Object[] nums);

    /**
     * 比較兩個(gè)數(shù)的大小
     */
    @SuppressWarnings({"unchecked", "rawtypes"})
    public boolean compare(Object v, Object w){
        return ((Comparable)v).compareTo(w) < 0;
    }

    /**
     * 交換兩個(gè)數(shù)組元素
     */
    public void swap(Object[] nums, int i, int j){
        Object temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 輸出數(shù)組內(nèi)容
     */
    public void showArray(Object[] nums){
        for (Object num : nums) {
            System.out.print(num + " ");
        }
    }
}

這個(gè)類(lèi)里面的方法也很簡(jiǎn)單钉稍，一個(gè) sort 抽象方法涤躲，后續(xù)的排序?qū)崿F(xiàn)類(lèi)都會(huì)實(shí)現(xiàn)這個(gè)方法，來(lái)填充具體的排序邏輯贡未；排序的操作基本上都會(huì)依賴(lài)比較和交換种樱，因此寫(xiě)了一個(gè) compare 比較方法蒙袍，比較兩個(gè)數(shù)字的大小，還有一個(gè) swap 方法交換兩個(gè)數(shù)組的元素缸托；最后是一個(gè) showArray 方法左敌，打印出數(shù)組內(nèi)容查看排序的結(jié)果是否符合預(yù)期。

然后再介紹兩個(gè)基本的概念俐镐，在文章里接下來(lái)的分析中我會(huì)經(jīng)常提到：

復(fù)雜度

按照慣例矫限，對(duì)算法的分析需要關(guān)注其復(fù)雜度，包括時(shí)間復(fù)雜度和空間復(fù)雜度佩抹，排序算法當(dāng)然也不例外叼风。對(duì)于不占用額外的存儲(chǔ)空間，空間復(fù)雜度是 O(1) 的排序棍苹，有一個(gè)專(zhuān)用的名詞來(lái)稱(chēng)呼无宿，叫做原地排序。

穩(wěn)定性

穩(wěn)定的排序指的是在排序前后枢里，相等的值的先后順序不會(huì)發(fā)生改變孽鸡，反之即是不穩(wěn)定的排序。舉個(gè)例子栏豺，一組數(shù)據(jù) 3 4 4 2 1 5彬碱，排序之后是 1 2 3 4 4 5，數(shù)組中有兩個(gè) 4奥洼，如果排序之后巷疼，兩個(gè) 4 的先后順序沒(méi)有改變，則稱(chēng)排序算法是穩(wěn)定的灵奖。穩(wěn)定的排序算法在某些特定的場(chǎng)景中會(huì)非常有用嚼沿。

一、基礎(chǔ)排序

1. 冒泡排序

很容易想到的一種排序思路是瓷患，每次都遍歷數(shù)組骡尽，查看相鄰的兩個(gè)數(shù)字的大小并交換位置，這樣每次都能夠?qū)⑤^大的那個(gè)元素移動(dòng)至數(shù)組的另一端擅编。每一次遍歷爆阶，較大的元素都會(huì)像氣泡一樣慢慢的“浮動(dòng)”至數(shù)組另一端，這便是這個(gè)算法被叫做冒泡排序的原因沙咏。

下面這張動(dòng)圖展示了冒泡排序的整個(gè)過(guò)程：

image

冒泡排序很容易理解辨图，復(fù)雜度也很好分析，在最好的情況下肢藐，如果數(shù)組本來(lái)就是有序的故河，那么只需要遍歷一次數(shù)組即可，時(shí)間復(fù)雜度是 O(n)吆豹，在最壞的情況下鱼的，每排列一個(gè)數(shù)據(jù)理盆，都需要遍歷整個(gè)數(shù)據(jù)集，因此時(shí)間復(fù)雜度是 O(n²)凑阶，平均情況下也接近 O(n²)猿规。排序過(guò)程不會(huì)使用到額外的存儲(chǔ)空間，因此空間復(fù)雜度是 O(1)宙橱，是原地排序姨俩。

冒泡排序是穩(wěn)定的嗎？從上面的圖中可以看到师郑，每次比較都是交換的兩個(gè)數(shù)值不相等的數(shù)據(jù)环葵，而相等的數(shù)據(jù)要么不滿足條件不移動(dòng)，要么滿足條件則全部移動(dòng)宝冕，這保證了相等數(shù)據(jù)的前后順序不發(fā)生改變张遭，因此冒泡排序是穩(wěn)定的。

下面是一個(gè)簡(jiǎn)單的代碼實(shí)現(xiàn)供參考：

public class BubbleSort extends AbstractSort {

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        boolean swap = true;
        for (int i = 0; swap && i < n; i++) {
            swap = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (compare(nums[j + 1], nums[j])){
                    swap(nums, j, j + 1);
                    swap = true;
                }
            }
        }
    }
}

需要注意的是地梨，代碼中使用到了一個(gè)輔助變量 swap菊卷，它的作用是標(biāo)識(shí)數(shù)據(jù)是否已經(jīng)沒(méi)有交換了，如果沒(méi)有則說(shuō)明數(shù)據(jù)已經(jīng)有序了宝剖，直接跳出循環(huán)洁闰，這樣可以避免多余的冒泡操作。例如數(shù)據(jù) 1 2 3 4 5 6诈闺，第一遍歷之后渴庆，發(fā)現(xiàn)已經(jīng)是有序的了铃芦，就沒(méi)有必要再進(jìn)行后續(xù)的遍歷雅镊。

2. 選擇排序

選擇排序也很容易理解，對(duì)于一個(gè)要排序的數(shù)組刃滓，我們每次都從數(shù)組中尋找最小值仁烹，并把它和第一個(gè)元素交換，然后在剩下的數(shù)據(jù)中繼續(xù)尋找最小值咧虎，然后將其與數(shù)組第二個(gè)元素交換卓缰，如此循環(huán)往復(fù)，直到整個(gè)數(shù)組有序砰诵。

下面這張動(dòng)圖可以幫助你理解選擇排序的整個(gè)過(guò)程：

image

無(wú)論在最好還是平均情況下征唬，選擇排序的時(shí)間復(fù)雜度都是 O(n²)，因?yàn)榫退闶且判蛞粋€(gè)已經(jīng)有序的數(shù)組茁彭，選擇排序的邏輯還是要遍歷數(shù)組尋找最小值总寒。空間復(fù)雜度則和冒泡排序一樣理肺，是 O(1)摄闸。

需要注意的是善镰，選擇排序是不穩(wěn)定的，這是由它的交換特性決定的年枕，我舉個(gè)例子就容易明白了炫欺，例如數(shù)據(jù) 3 3 2 0 1 5，第一次遍歷熏兄，我們找到了最小值 0品洛，并把它和第一個(gè)數(shù)據(jù) 3 交換位置，那么這兩個(gè) 3 的前后順序就被改變了霍弹，因此選擇排序不能保證穩(wěn)定性毫别。

下面是一個(gè)簡(jiǎn)單的代碼示例供參考：

public class SelectionSort extends AbstractSort {

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int min = i + 1;
            for (int j = i; j < n; j++) {
                if (compare(nums[j], nums[min])){
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }

}

3. 插入排序

插入排序的基本思路是：依次遍歷每一個(gè)數(shù)字，并將其和前面已排序的數(shù)據(jù)進(jìn)行對(duì)比典格，將其插入到合適的位置岛宦。生活中也有很多這樣的例子，假如我們手中有一副撲克牌耍缴，當(dāng)新來(lái)了一張撲克牌之后砾肺，我們便會(huì)依次查找，將新來(lái)的撲克牌放到合適的位置防嗡。

插入排序的過(guò)程如下圖：

image

插入排序的時(shí)間復(fù)雜度和冒泡排序類(lèi)似变汪，這里不再贅述了，平均情況下的時(shí)間復(fù)雜度是 O(n²)蚁趁，空間復(fù)雜度是 O(1)裙盾，是原地排序。并且插入排序也是穩(wěn)定的他嫡，從上圖也很容易明白番官，在每個(gè)數(shù)據(jù)的遍歷交換過(guò)程中，相同數(shù)據(jù)的前后順序肯定不會(huì)被改變钢属。

下面是一個(gè)簡(jiǎn)單的代碼示例供參考：

public class InsertionSort extends AbstractSort {
    
    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int j = i + 1;
            Object k = nums[j];
            while (j > 0 && compare(k, nums[j - 1])){
                nums[j] = nums[--j];
            }
            nums[j] = k;
        }
    }
}

4. 希爾排序

希爾排序其實(shí)是插入排序的一個(gè)優(yōu)化版本徘熔，如果你搞懂了插入排序，那么弄懂希爾排序就非常容易了淆党】崾Γ回想一下，插入排序的特點(diǎn)是：每次比較的時(shí)候交換相鄰元素染乌，因此數(shù)據(jù)每次只能移動(dòng)一位山孔。如果這樣的話，對(duì)于一些大規(guī)模亂序的數(shù)據(jù)荷憋，例如最大值剛好在頭部台颠，那么將其移動(dòng)至尾部，需要移動(dòng)大概 n - 1 次台谊。

而希爾排序則將數(shù)據(jù)分成了 n 個(gè)組蓉媳，對(duì)每個(gè)組內(nèi)的數(shù)據(jù)分別進(jìn)行插入排序譬挚，這樣就能夠?qū)⑤^大的數(shù)據(jù)一次性移動(dòng)很多位，為后續(xù)的比較交換提供了便利酪呻。文字描述起來(lái)可能比較的晦澀抽象减宣，可以結(jié)合下面的圖來(lái)看一下：

image

我們先定義一個(gè)增量 k，k 一般為數(shù)組長(zhǎng)度的 1 / 2 玩荠，上圖中要排序的原始數(shù)據(jù)的個(gè)數(shù)是 8 漆腌，因此 k = 8 / 2 = 4，所以第一次可以將數(shù)組分為 4 組阶冈，分別是 (9, 5), (2, 1), (4, 0), (3, 6)闷尿，即上圖中用直線連接起來(lái)的數(shù)據(jù)，然后將每個(gè)組內(nèi)的數(shù)據(jù)分別進(jìn)行插入排序女坑，那么第一次排序之后的結(jié)果為：5 1 0 3 9 2 4 6填具。

可以看到最開(kāi)始 9 在數(shù)組最前面，但是經(jīng)過(guò)第一次排序之后匆骗，9 已經(jīng)向后移動(dòng)了 4 位劳景，相較于插入排序，這樣就減少了移動(dòng)的次數(shù)碉就，希爾排序的性能提升就主要體現(xiàn)在這里盟广。

然后繼續(xù)進(jìn)行分組，這時(shí) k 縮小一半變?yōu)?2瓮钥，因此我們將數(shù)組分為兩組筋量，然后在組內(nèi)再進(jìn)行插入排序，如下圖：

image

此時(shí)分為了兩組碉熄，分別是(5, 0, 9, 4), (1, 3, 2, 6)桨武，進(jìn)行排序之后的結(jié)果是：0 1 4 2 5 3 9 6，可以看到此時(shí)數(shù)組已經(jīng)基本上是有序的了具被。

然后 k 再次縮小為 1玻募，我們將數(shù)組分為 1 組只损，其實(shí)就是原始的數(shù)據(jù)了一姿，然后再進(jìn)行一次插入排序，由于其實(shí)數(shù)據(jù)已經(jīng)是基本上有序的了跃惫，因此只需要微調(diào)即可叮叹，一般不會(huì)進(jìn)行大量的數(shù)據(jù)移動(dòng)：

image

整個(gè)排序的過(guò)程當(dāng)中，增量 k 是一步一步縮小的爆存，正因此蛉顽，希爾排序其實(shí)也叫做縮小增量排序。

下面是一個(gè)簡(jiǎn)單的希爾排序的代碼示例：

public class ShellSort extends AbstractSort {

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        int k = n / 2;
        while (k >= 1){
            for (int i = 0; i < n - k; i++) {
                int j = i + k;
                Object v = nums[j];
                while (j > k - 1 && compare(v, nums[j - k])){
                    nums[j] = nums[j - k];
                    j = j - k;
                }
                nums[j] = v;
            }
            k = k / 2;
        }
    }
}

希爾排序的時(shí)間復(fù)雜度比較難分析先较，可以大致概括為 O(nlog²n)携冤，但實(shí)際上它和定義的增量悼粮、數(shù)據(jù)本身的排列特性等相關(guān)，有很多相關(guān)論文都進(jìn)行了分析曾棕，但都無(wú)法得到具體選擇哪個(gè)增量是最好的扣猫。已知的最好的增量是 Sedgewick 提出的 (1, 5, 19, 41, 109,……)，感興趣的可以看下 wikipedia 上關(guān)于步長(zhǎng)序列的描述：維基百科—希爾排序

希爾排序的空間復(fù)雜度很好理解翘地，是 O(1)申尤，并且希爾排序是不穩(wěn)定的，因?yàn)樗瓦x擇排序類(lèi)似衙耕，都是跳著進(jìn)行數(shù)據(jù)的交換昧穿，這樣就會(huì)破壞穩(wěn)定性。

當(dāng)數(shù)據(jù)量較小的時(shí)候橙喘，希爾排序是一個(gè)不錯(cuò)的選擇时鸵，但是它并沒(méi)有被廣泛的應(yīng)用，因?yàn)樵跀?shù)據(jù)量較大的時(shí)候厅瞎，我們更傾向于使用復(fù)雜度更優(yōu)的 O(nlogn) 的排序算法寥枝。

5. 總結(jié)

前面說(shuō)到的這幾種基礎(chǔ)排序算法，在實(shí)際當(dāng)中的使用并不是很多磁奖，因?yàn)樗鼈兊臅r(shí)間復(fù)雜度較高囊拜，應(yīng)用在大規(guī)模數(shù)據(jù)中的話，效率將會(huì)非常低下比搭，因此它們只適合小規(guī)模的數(shù)據(jù)排序冠跷。例如 Java 中的雙軸快速排序，在數(shù)據(jù)量小于 47 時(shí)便使用了插入排序身诺。

你也許會(huì)納悶蜜托，為什么插入排序、冒泡排序霉赡、選擇排序的平均時(shí)間復(fù)雜度都是 O(n²)橄务，但是在大多數(shù)情況下，針對(duì)數(shù)據(jù)量較少的情況穴亏，一般都會(huì)采用插入排序呢蜂挪？

簡(jiǎn)單分析一下，選擇排序就不用說(shuō)了嗓化，因?yàn)樗男阅懿](méi)有絕對(duì)優(yōu)勢(shì)棠涮，即便是在數(shù)組已經(jīng)有序的情況下，它的時(shí)間復(fù)雜度仍然是 O(n²)刺覆，并且它還不是穩(wěn)定的严肪，因此選擇排序一般并不會(huì)考慮使用。

接下來(lái)再看看冒泡排序和插入排序，這兩者雖然時(shí)間復(fù)雜度是一樣的驳糯，但是在實(shí)際的排序過(guò)程中篇梭，冒泡排序的數(shù)據(jù)交換次數(shù)更多，你可以從上面的代碼示例中看到酝枢，冒泡排序的一次交換涉及到三次操作很洋，而插入排序只需要一次數(shù)據(jù)賦值，這樣的話便使插入排序要稍微快一些隧枫。

你可以構(gòu)造一組隨機(jī)數(shù)據(jù)來(lái)測(cè)試這兩種排序算法喉磁，例如我在本機(jī)測(cè)試了一組 5 萬(wàn)個(gè)數(shù)據(jù)，冒泡排序的耗時(shí)是 8 秒多一點(diǎn)官脓，而插入排序只使用了不到 3 秒协怒。

//冒泡排序，swap 函數(shù)涉及到三次賦值操作
for (int j = 0; j < n - i - 1; j++) {
   if (compare(nums[j + 1], nums[j])){
     swap(nums, j, j + 1);
     swap = true;
   }
}

//插入排序卑笨，交換時(shí)只需要一次數(shù)據(jù)賦值
while (j > 0 && compare(k, nums[j - 1])){
   nums[j] = nums[j - 1];
   j--;
}

最后再來(lái)看看希爾排序孕暇，希爾排序發(fā)明于 1959 年，它是最早的時(shí)間復(fù)雜度突破 O(n²) 的排序算法之一赤兴，但是它的應(yīng)用并不是很廣泛妖滔，原因在于它遇到了更強(qiáng)勁的“對(duì)手”，相較于歸并排序桶良，它并不是穩(wěn)定的座舍，而相較于快速排序，它的性能又沒(méi)有任何優(yōu)勢(shì)可言陨帆，因此歸并排序和快速排序更受青睞曲秉。

二、歸并排序

在介紹歸并排序之前疲牵，先簡(jiǎn)單說(shuō)下分治思想承二。分治，顧名思義就是分而治之纲爸，它是一種解決問(wèn)題的思路亥鸠，將原始問(wèn)題分解為多個(gè)相同或相似的子問(wèn)題，然后將子問(wèn)題解決识啦，并將子問(wèn)題的求得的解進(jìn)行合并负蚊，這樣原問(wèn)題就能夠得到解決了。分治思想是很多復(fù)雜算法的基礎(chǔ)袁滥，例如歸并排序盖桥、快速排序灾螃、二分查找等等题翻。

言歸正傳，再來(lái)看歸并排序，它的概念理解起來(lái)非常簡(jiǎn)單嵌赠，如果我們要對(duì)一組數(shù)據(jù)進(jìn)行排序塑荒，我們可以將這個(gè)數(shù)組分為兩個(gè)子數(shù)組，子數(shù)組再進(jìn)行分組姜挺，這樣子數(shù)組排序之后齿税，將結(jié)果合并起來(lái)，就能夠得到原始數(shù)據(jù)排序的結(jié)果炊豪，相信你已經(jīng)發(fā)現(xiàn)了凌箕，這就是典型的利用分治思想解決問(wèn)題的思路。

下面這張圖展示了將一個(gè)問(wèn)題分解為多個(gè)子問(wèn)題的過(guò)程：

image

子問(wèn)題得到解決之后词渤，需要將結(jié)果合并牵舱，合并的過(guò)程如下圖：

image

下面的動(dòng)圖比較直觀的展示了歸并排序的整個(gè)過(guò)程，可以對(duì)照起來(lái)理解一下：

[圖片上傳失敗...(image-6f7bf9-1591414759850)]

如果使用一個(gè)簡(jiǎn)單的公式來(lái)表示歸并排序的話缺虐，那么可以寫(xiě)成這樣：

 merge_sort(data, p, r) = merge(merge_sort(data, p, q), merge_sort(data, q + 1, r));

我來(lái)簡(jiǎn)單解釋一下這個(gè)公式芜壁，我們將排序的數(shù)組叫做 data，p 和 r 分別表示其起始和終止下標(biāo)高氮，因?yàn)橐M(jìn)行分組慧妄，因此取 p 和 r 的中間值 q，然后對(duì) p 到 q 和 q + 1 到 r 的數(shù)據(jù)分別再進(jìn)行排序剪芍。

排序之后的結(jié)果需要用一個(gè)合并的函數(shù)來(lái)將結(jié)果合并塞淹，這個(gè)函數(shù)可以叫做 merge，merge 函數(shù)的功能很簡(jiǎn)單罪裹，對(duì)于兩個(gè)已排序的數(shù)據(jù)區(qū)間窖铡，假設(shè)下標(biāo)是 p ~ r，我們可以新建一個(gè)臨時(shí)數(shù)組坊谁，然后依次比較兩個(gè)已排序的數(shù)據(jù)區(qū)間的值费彼，并將其一 一復(fù)制到臨時(shí)數(shù)組中，你可以結(jié)合下圖來(lái)理解一下：

image

理解了這些之后口芍，再來(lái)看歸并排序的代碼實(shí)現(xiàn)就會(huì)非常簡(jiǎn)單了箍铲，下面是一個(gè)代碼示例：

public class MergeSort extends AbstractSort {

    private Object[] temp;

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        temp = new Object[n];
        sortHelper(nums, 0, n - 1);
    }

    private void sortHelper(Object[] data, int p, int r){
        if (p >= r){
            return;
        }

        int q = p + (r - p) / 2;
        sortHelper(data, p, q);
        sortHelper(data, q + 1, r);
        merge(data, p, q, r);
    }

    private void merge(Object[] data, int p, int q, int r){
        int i = p, j = q + 1;
        System.arraycopy(data, p, temp, p, r - p + 1);

        for (int k = p; k <= r; k++) {
            if (i > q) data[k] = temp[j++];
            else if (j > r) data[k] = temp[i++];
            else if (compare(temp[j], temp[i])) data[k] = temp[j++];
            else data[k] = temp[i++];
        }
    }
}

2.1 算法分析

歸并排序的時(shí)間復(fù)雜度，一般可以使用兩種方式來(lái)進(jìn)行推導(dǎo)鬓椭，假如將要排序的數(shù)組的長(zhǎng)度記為 n颠猴，排序一個(gè)長(zhǎng)度為 n 的數(shù)組的時(shí)間記為 T(n)，由于歸并排序需要將原問(wèn)題分解成子問(wèn)題小染，因此 T(n) 又可以寫(xiě)成 T(n) = 2 * T(n/2) + n翘瓮，其中 n 表示合并兩個(gè)子數(shù)組所需要的時(shí)間。

然后繼續(xù)進(jìn)行分解裤翩，這個(gè)公式可以表示成這樣：

T(n) = 2 * T(n/2) + n
     = 2 * ( 2 * T(n/4) + n/2) + n                = 4 * T(n/4) + 2n
     = 2 * ( 2 * (2 * T(n/8) + n/4) + n/2) + n    = 8 * T(n/8) + 3n
     … … … 
     = 2^k * T(n/2^k) + k*n

可以看到资盅，時(shí)間計(jì)算公式可以記為：T(n) = 2^k * T(n/2^k) + k * n，當(dāng) n / 2^k = 1 的時(shí)候，可以得到 k = logn呵扛，然后再將 k 代入到公式中每庆，可以得到 T(n) = Cn + nlogn （C 為常數(shù)），使用大 O 表示法今穿，那么歸并排序的時(shí)間復(fù)雜度可以大致記為 O(nlogn)缤灵。

當(dāng)然這種分析方式較為復(fù)雜抽象，還有一種更加簡(jiǎn)單直觀的方式蓝晒，我們可以將歸并排序的過(guò)程使用樹(shù)的方式腮出，形象的展示出來(lái)，大致就是這樣的：

image

可以看到芝薇，歸并排序的時(shí)間復(fù)雜度可以使用樹(shù)結(jié)構(gòu)分級(jí)展示利诺，每一層涉及到的操作是分組和合并，所消耗的時(shí)間都是一樣的 n剩燥，因此算法的總體時(shí)間復(fù)雜度就是 n * 樹(shù)的高度慢逾，可以很明顯的看出，這是一顆滿二叉樹(shù)灭红，滿二叉樹(shù)的高度一般是 logn侣滩，因此歸并排序的時(shí)間復(fù)雜度就是 O(nlogn)。

歸并排序的空間復(fù)雜度比較簡(jiǎn)單变擒，從代碼中可以看到君珠，當(dāng)進(jìn)行子數(shù)組合并的時(shí)候，需要一個(gè)臨時(shí)數(shù)組 temp娇斑，數(shù)組的長(zhǎng)度等于要排序的數(shù)組長(zhǎng)度策添，因此空間復(fù)雜度可以表示為 O(n)。

其實(shí)歸并排序并沒(méi)有像快速排序那樣應(yīng)用廣泛毫缆，其中很重要的原因便是它并不是原地排序算法唯竹，這是它的一個(gè)致命弱點(diǎn)。

最后思索一下歸并排序是穩(wěn)定的嗎苦丁？這個(gè)問(wèn)題比較好理解浸颓，數(shù)組的拆分并不會(huì)涉及到數(shù)據(jù)交換，只有合并才會(huì)旺拉，因此歸并排序是否穩(wěn)定主要取決于 merge 的過(guò)程产上。

假設(shè)我們需要合并 1 3 3 5 和 2 3 4 6，可以看到在合并的過(guò)程當(dāng)中蛾狗，我們的判斷條件是單一的晋涣，如果第一個(gè)數(shù)字被放到的了臨時(shí)數(shù)組中，那么后續(xù)相同的數(shù)字也會(huì)依次被放到臨時(shí)數(shù)組中沉桌，前后順序不會(huì)被改變谢鹊，因此歸并排序是穩(wěn)定的算吩。

2.2 自底向上

上面講到的歸并排序是最常見(jiàn)的一種類(lèi)型，它的特點(diǎn)是自頂向下進(jìn)行數(shù)據(jù)拆分撇贺，你可以從最開(kāi)始的分解圖清晰的看出來(lái)赌莺，其實(shí)還有另外一種歸并排序冰抢，它的順序恰恰相反松嘶，是自底向上的，只不過(guò)這種方式理解起來(lái)并不如上面的直觀挎扰，你可以簡(jiǎn)單做個(gè)了解翠订。

其思路是這樣的：首先進(jìn)行兩兩歸并（你可以將數(shù)組想象成多個(gè)只有一個(gè)元素的子數(shù)組），然后是四四歸并（將長(zhǎng)度為 2 的子數(shù)組合并為長(zhǎng)度為 4 的子數(shù)組）遵倦，然后是八八歸并尽超，一直進(jìn)行下去。

下面是一個(gè)簡(jiǎn)單的代碼示例：

public class MergeSortBottomUp extends AbstractSort {

    private Object[] temp;

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        int n = nums.length;
        temp = new Object[n];
        for (int i = 1; i < n; i = 2 * i) {
            for (int j = 0; j < n - i; j += (2 * i)){
                merge(nums, j, j + i - 1, Math.min(j + 2 * i - 1, n - 1));
            }
        }
    }

    private void merge(Object[] data, int p, int q, int r){
        if (compare(data[q], data[q + 1])){
            return;
        }
        int i = p, j = q + 1;
        System.arraycopy(data, p, temp, p, r - p + 1);

        for (int k = p; k <= r; k++) {
            if (i > q) data[k] = temp[j++];
            else if (j > r) data[k] = temp[i++];
            else if (compare(temp[j], temp[i])) data[k] = temp[j++];
            else data[k] = temp[i++];
        }
    }
}

三梧躺、快速排序

快速排序通常叫做“快排”似谁，它應(yīng)該是應(yīng)用最廣泛的一個(gè)排序算法了，很多編程語(yǔ)言?xún)?nèi)置的排序工具掠哥，都或多或少使用到了快速排序巩踏，因?yàn)榭焖倥判虻臅r(shí)間復(fù)雜度可以達(dá)到 O(nlogn)，并且是原地排序续搀，前面介紹的幾種排序算法都無(wú)法將這兩個(gè)優(yōu)點(diǎn)結(jié)合起來(lái)塞琼。

快排和歸并排序類(lèi)似，都采用了分治思想禁舷，但是它的解決思路卻和歸并排序不太一樣彪杉。如果要排序一個(gè)數(shù)組，我們可以從數(shù)組中選擇一個(gè)數(shù)據(jù)牵咙，做為分區(qū)點(diǎn)（pivot）派近，然后將小于分區(qū)點(diǎn)的放到分區(qū)點(diǎn)的左側(cè)，大于分區(qū)點(diǎn)的放到其右側(cè)洁桌，然后對(duì)于分區(qū)點(diǎn)左右兩邊的數(shù)據(jù)构哺，繼續(xù)采用這種分區(qū)的方式，直到數(shù)組完全有序战坤。

概念讀起來(lái)可能有點(diǎn)抽象曙强，這里我畫(huà)了一張圖來(lái)幫助你理解整個(gè)排序的過(guò)程：

image

上圖展示了第一次分區(qū)的過(guò)程，假設(shè)要排序的數(shù)組的下標(biāo)是 p ~ r途茫，我們?nèi)?shù)組的最后一個(gè)元素 5 做為分區(qū)點(diǎn)碟嘴，然后比 5 小的數(shù)字 0 3 1 2 移動(dòng)到 5 的左邊，比 5 大的數(shù)字 9 6 8 7 移動(dòng)到 5 的右邊囊卜。

然后以數(shù)字 5 為分界點(diǎn)娜扇，其左邊的數(shù)字（下標(biāo)為 p ~ q - 1）错沃，以及右邊的數(shù)字（下標(biāo)為 q + 1 ~ r），分別再進(jìn)行同樣的分區(qū)操作雀瓢，一直分下去枢析，直到數(shù)組完全有序，如下圖：

image

下面的動(dòng)圖展示了快速排序的完整過(guò)程（注意動(dòng)圖中是選擇第一個(gè)元素做為分區(qū)點(diǎn)的）：

[圖片上傳失敗...(image-9867bb-1591414759850)]

如果使用一個(gè)簡(jiǎn)單的公式來(lái)表示快速排序刃麸，可以寫(xiě)成這樣：

int q = partition(data, p, r);
quick_sort(data, p, r) = quick_sort(data, p, q - 1) + quick_sort(data, q + 1, r);

這里有一個(gè) partition 分區(qū)函數(shù)醒叁，它的作用是選擇一個(gè)分區(qū)點(diǎn)，并且將小于分區(qū)點(diǎn)的數(shù)據(jù)放到其左邊泊业，大于分區(qū)點(diǎn)的放到其右邊把沼，然后返回分區(qū)點(diǎn)的下標(biāo)。其實(shí)這個(gè) partition 分區(qū)函數(shù)是快速排序?qū)崿F(xiàn)的關(guān)鍵吁伺，那究竟怎么實(shí)現(xiàn)這個(gè)函數(shù)呢饮睬？很容易想到的一種方式是：直接遍歷一次原數(shù)組，依次取出小于和大于分區(qū)點(diǎn)的數(shù)據(jù)篮奄，將其各自存放到臨時(shí)數(shù)組中捆愁，然后再依次拷貝回原數(shù)組中，過(guò)程如下圖：

image

相信你也看出來(lái)了窟却，這樣做雖然簡(jiǎn)單昼丑，但是存在一個(gè)缺陷，那就是每次分區(qū)都會(huì)使用額外的存儲(chǔ)空間间校，這會(huì)導(dǎo)致快速排序的空間復(fù)雜度為 O(n)矾克，那么就不是原地排序了。所以快速排序使用了另一種方式來(lái)實(shí)現(xiàn)分區(qū)憔足，并且沒(méi)有借助額外的存儲(chǔ)空間胁附，它是怎么實(shí)現(xiàn)的呢？我還是畫(huà)了一張圖來(lái)幫助你理解：

image

這個(gè)分區(qū)的過(guò)程可能不太好理解滓彰，你可以多看幾遍上面的圖控妻，我們聲明了兩個(gè)指針 i 和 j，從數(shù)組的最開(kāi)始處向后移動(dòng)揭绑，這里的移動(dòng)規(guī)則有兩個(gè)：一是如果 j 所在元素大于分區(qū)點(diǎn)弓候，那么 j 向后移動(dòng)一位，i 不變他匪；二是如果 j 所在元素小于分區(qū)點(diǎn)菇存，那么交換 i 和 j 所在元素，然后 i 和 將 j 同時(shí)向后移動(dòng)一位邦蜜。

終止的條件是 j 移動(dòng)至數(shù)組末尾依鸥，然后交換分區(qū)點(diǎn)和 i 所在的元素，i 就是分區(qū)點(diǎn)的下標(biāo)悼沈。

理解了這個(gè)過(guò)程之后贱迟，再來(lái)看快速排序的代碼實(shí)現(xiàn)姐扮，就會(huì)非常的簡(jiǎn)單了，下面是一個(gè)示例：

public class QuickSort extends AbstractSort {

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        sortHelper(nums, 0, nums.length - 1);
    }

    private void sortHelper(Object[] data, int p, int r){
        if (p >= r){
            return;
        }

        int q = partition(data, p, r);
        sortHelper(data, p, q - 1);
        sortHelper(data, q + 1, r);
    }

    private int partition(Object[] data, int p, int r){
        Object pivot = data[r];
        int i = p, j = p;
        while (j < r){
            if (compare(data[j], pivot)) {
                swap(data, i, j);
                i++;
            }
            j++;
        }
        swap(data, r, i);
        return i;
    }
}

3.1 算法分析

快速排序的時(shí)間復(fù)雜度的表示方法其實(shí)和歸并排序類(lèi)似衣吠，在最好的情況下茶敏，每次分區(qū)都能夠均勻的將數(shù)組一分為二，那么時(shí)間復(fù)雜度可表示為 T(n) = 2 * T(n/2) + n缚俏，由上面的歸并排序公式分析可以得出惊搏，最后的時(shí)間復(fù)雜度可以表示為 O(nlogn)，盡管每次分區(qū)并不總會(huì)是最好情況袍榆，但是平均情況下胀屿，其時(shí)間復(fù)雜度還是在 O(nlogn) 左右的塘揣。

仔細(xì)分析一下包雀，其實(shí)快速排序的簡(jiǎn)潔快速主要體現(xiàn)在：每次分區(qū)的時(shí)候，數(shù)組中的元素其實(shí)都在和一個(gè)定值比較并判斷是否交換亲铡，掃描一遍數(shù)組之后才写，便不會(huì)再有數(shù)據(jù)交換了，而歸并排序則是在交換比較元素之后奖蔓，會(huì)重新把數(shù)組拷貝回原數(shù)組赞草，所以可以得出結(jié)論，在多數(shù)情況下吆鹤，快速排序其實(shí)比歸并排序更快厨疙，盡管它們的時(shí)間復(fù)雜度都可以表示為 O(nlogn)。

快速排序另一個(gè)重要的特性是原地排序疑务，因?yàn)榉謪^(qū)的過(guò)程中并沒(méi)有使用到額外的存儲(chǔ)空間沾凄，空間復(fù)雜度是 O(1)，但很遺憾的是知允，快速排序是不穩(wěn)定的撒蟀，因?yàn)樵诜謪^(qū)的過(guò)程當(dāng)中，數(shù)據(jù)會(huì)跳著進(jìn)行交換温鸽，你可以結(jié)合我上面的圖理解一下保屯。

3.2 算法優(yōu)化

快速排序作為一種在編程語(yǔ)言中應(yīng)用很多的算法，很多程序語(yǔ)言設(shè)計(jì)專(zhuān)家都對(duì)其進(jìn)行了大量的優(yōu)化涤垫，接下來(lái)我們可以了解幾種比較常用的優(yōu)化策略姑尺。

使用插入排序

在數(shù)據(jù)量較少的情況下，可以使用插入排序蝠猬，很多編程語(yǔ)言?xún)?nèi)置的排序算法都使用到了這個(gè)優(yōu)化辦法切蟋。

分區(qū)點(diǎn)選擇

在上面的講解中，我直接是以數(shù)組最后一個(gè)元素做為快速排序的分區(qū)點(diǎn)吱雏，這樣做雖然簡(jiǎn)單敦姻，但是可能存在效率低下的情況瘾境，例如要排序的數(shù)據(jù)本來(lái)就是或接近有序的，那么每次分區(qū)數(shù)據(jù)的分布都極不均勻镰惦，時(shí)間復(fù)雜度就會(huì)退化迷守。

快速排序最理想的情況是，每次分區(qū)都能夠均勻的將數(shù)據(jù)一分為二旺入，為了達(dá)到或者接近這種情況兑凿，分區(qū)點(diǎn)的選擇其實(shí)可以更講究一點(diǎn)，常用的方法有：隨機(jī)法茵瘾，我們可以隨機(jī)的選擇數(shù)組中一個(gè)數(shù)字做為分區(qū)點(diǎn)礼华；三數(shù)取中，每次都隨機(jī)的從數(shù)組中取出三個(gè)數(shù)拗秘，然后取三個(gè)數(shù)中間的那一個(gè)做為分區(qū)點(diǎn)圣絮。

三向切分

如果數(shù)組中存在大量重復(fù)的元素，那么重復(fù)的元素其實(shí)并不用排序了雕旨，但是上面的分區(qū)方法還是會(huì)把重復(fù)的元素切分為更小的數(shù)組扮匠。針對(duì)這種情況，可以使用三向切分的辦法凡涩，即把數(shù)據(jù)切分為三份棒搜，分別是小于分區(qū)點(diǎn)、等于分區(qū)點(diǎn)活箕、大于分區(qū)點(diǎn)的元素力麸，而等于分區(qū)點(diǎn)的元素則不用繼續(xù)切分。

下面是三向切分的一個(gè)代碼示例，你可以結(jié)合代碼來(lái)理解一下：

public class QuickSort3Way extends AbstractSort{

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        sortHelper(nums, 0, nums.length - 1);
    }

    @SuppressWarnings({"unchecked", "rawtypes"})
    private void sortHelper(Object[] data, int p, int r){
        if (p >= r){
            return;
        }

        int lt = p, i = p + 1, gt = r;
        Comparable pivot = (Comparable) data[p];
        while (i <= gt){
            int cmp = pivot.compareTo(data[i]);
            if (cmp > 0){
                swap(data, lt++, i++);
            } else if (cmp < 0){
                swap(data, i, gt--);
            } else{
                i++;
            }
        }
        sortHelper(data, p, lt - 1);
        sortHelper(data, gt + 1, r);
    }
}

四、堆排序

要理解堆排序策幼，必須得先明白什么是二叉堆视乐。二叉堆（以下簡(jiǎn)稱(chēng)堆）是一種很優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)，它是一種特殊的二叉樹(shù)，滿足二叉樹(shù)的兩個(gè)特性便可以叫做堆：

• 是一個(gè)完全二叉樹(shù)
• 堆中任意一個(gè)節(jié)點(diǎn)的值都必須大于等于（或者小于等于）其子樹(shù)中的所有節(jié)點(diǎn)值

對(duì)于節(jié)點(diǎn)大于等于子樹(shù)中節(jié)點(diǎn)值的堆，叫做大頂堆，反之則叫做小頂堆游盲，以下是幾個(gè)堆的例子：

image

從定義和上圖中可以看到，堆的一個(gè)特點(diǎn)便是蛮粮，堆頂元素就是堆中最大（或最幸娑小）的元素。堆其實(shí)可以使用數(shù)組來(lái)存儲(chǔ)然想，堆頂元素就是數(shù)組的第一個(gè)元素莺奔，并且對(duì)于任意下標(biāo)為 i 的節(jié)點(diǎn)，其左子節(jié)點(diǎn)是 2 * i + 1变泄，右子節(jié)點(diǎn)是 2 * i + 2令哟，有了這個(gè)對(duì)應(yīng)關(guān)系恼琼，堆在數(shù)組中的存儲(chǔ)就是這樣的：

image

理解了什么是堆之后，接下來(lái)進(jìn)入正題屏富，看看如何基于堆實(shí)現(xiàn)排序晴竞。堆排序的步驟一般有兩個(gè)，分別是構(gòu)造堆和排序狠半，下面依次介紹噩死。

4.1 構(gòu)造堆

構(gòu)造堆指的是將無(wú)序的數(shù)組構(gòu)造成大頂堆，使其符合大頂堆的特征神年，舉一個(gè)例子已维，對(duì)于一個(gè)完全無(wú)序的數(shù)組，其原始的排列順序就像下圖這樣：

image

要使其變成大頂堆已日，我們可以這樣做：從第一個(gè)非葉子節(jié)點(diǎn)（葉子節(jié)點(diǎn)指的是樹(shù)中沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)）開(kāi)始垛耳，依次將其和子節(jié)點(diǎn)的值進(jìn)行比較，根據(jù)大頂堆的特性捂敌，如果節(jié)點(diǎn)的值小于子節(jié)點(diǎn)的值艾扮，則將其和較大的子節(jié)點(diǎn)的值進(jìn)行交換既琴，然后再依次向下比較占婉，直到葉子節(jié)點(diǎn)。

例如上圖中的數(shù)據(jù)甫恩，第一個(gè)非葉子節(jié)點(diǎn)是 3逆济，所以就從 3 開(kāi)始進(jìn)行比較，整個(gè)過(guò)程如下圖：

image

4.2 排序

構(gòu)造堆完成之后磺箕，接下來(lái)便是排序了奖慌，前面已經(jīng)提到過(guò)，大頂堆有一個(gè)重要的特性是其堆頂元素是堆中的最大元素松靡，因此我們可以每次取堆頂?shù)脑丶蛏瑢⑵浞诺綌?shù)組的末尾，然后將堆重新組織雕欺，繼續(xù)取堆頂元素岛马，這樣將堆中的元素依次取出之后，整個(gè)數(shù)組便是有序的了屠列，你可以參考下圖理解整個(gè)過(guò)程：

image

你也可以結(jié)合代碼來(lái)看一下啦逆，下面是一個(gè)示例：

public class HeapSort extends AbstractSort{

    @Override
    public void sort(Object[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }

        buildHeap(nums, nums.length);
        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums, 0, i);
            heapify(nums, 0, i);
        }
    }

    private void buildHeap(Object[] data, int n){
        for (int i = (n - 1) / 2; i >= 0; i--) {
            heapify(data, i, n);
        }
    }

    private void heapify(Object[] data, int i, int n){
        while (true){
            int max = i;
            if (2 * i + 1 <= n - 1 && compare(data[max], data[2 * i + 1])) {
                max = 2 * i + 1;
            }
            if (2 * i + 2 <= n - 1 && compare(data[max], data[2 * i + 2])) {
                max = 2 * i + 2;
            }
            if (i == max) break;
            swap(data, max, i);
            i = max;
        }
    }
}

4.3 算法分析

堆排序的時(shí)間復(fù)雜度比較好分析，堆是一個(gè)完全二叉樹(shù)笛洛，完全二叉樹(shù)和滿二叉樹(shù)的高度都是 logn夏志，每次重新構(gòu)建堆的時(shí)間消耗是 logn，排序至少需要遍歷數(shù)組每個(gè)元素苛让，時(shí)間消耗是 n沟蔑，因此堆排序的總體時(shí)間復(fù)雜度便是 O(nlogn)湿诊。排序的過(guò)程中沒(méi)有使用到額外的存儲(chǔ)空間，空間復(fù)雜度是 O(1)瘦材，是原地排序枫吧。

堆排序并不是穩(wěn)定的，你可以結(jié)合上面的圖理解一下宇色，數(shù)據(jù)在交換的過(guò)程當(dāng)中是像選擇排序一樣跳著交換的九杂，因此相同數(shù)據(jù)的前后順序可能發(fā)生變化。

相信你已經(jīng)注意到了宣蠕，堆排序和快速排序一樣例隆，其時(shí)間復(fù)雜度是 O(nlogn)，并且它非常穩(wěn)定（這里的穩(wěn)定指的是算法的性能抢蚀，而不是上面說(shuō)到的算法的穩(wěn)定特性）镀层，在各種數(shù)據(jù)規(guī)模、數(shù)據(jù)排列特征下皿曲，它都能夠保持 O(nlogn) 的運(yùn)行時(shí)間唱逢，并且它還是原地排序。

但其實(shí)堆排序還是沒(méi)有快速排序應(yīng)用廣泛屋休，其中一個(gè)很重要的原因是堆排序無(wú)法利用 CPU 緩存坞古，為什么這么說(shuō)呢？

從上面堆排序的過(guò)程中劫樟，我們可以發(fā)現(xiàn)痪枫，其實(shí)堆排序在進(jìn)行數(shù)據(jù)的構(gòu)建堆操作時(shí)，一般不會(huì)順序的讀取數(shù)據(jù)叠艳，因?yàn)榍懊嫣岬降哪莻€(gè)公式奶陈，對(duì)于任意節(jié)點(diǎn)i，其左子節(jié)點(diǎn)是 2 * i + 1附较，右子節(jié)點(diǎn)是 2 * i + 2吃粒。例如在數(shù)組下標(biāo)為 3 處的節(jié)點(diǎn)，進(jìn)行建堆時(shí)拒课，會(huì)訪問(wèn)它的左右子節(jié)點(diǎn)徐勃，分別是 7 和 8，這對(duì) CPU 緩存來(lái)說(shuō)是不友好的捕发。

后記

我本想將 Java 中內(nèi)置的排序算法放到文章最后進(jìn)行分析疏旨，但是 Java 里面的 DualPivotQuickSort 和 TimeSort 實(shí)在是有點(diǎn)復(fù)雜，并且加上這個(gè)的話文章的篇幅將會(huì)更長(zhǎng)扎酷，所以以后可以針對(duì)這個(gè)單獨(dú)寫(xiě)一篇文章檐涝，這次就暫時(shí)不介紹了。