經(jīng)典 O(n2)比較類排序算法

關(guān)注公號(hào)「碼哥字節(jié)」修煉技術(shù)內(nèi)功心法挑豌，完整代碼可跳轉(zhuǎn) GitHub：https://github.com/UniqueDong/algorithms.git

摘要：排序算法提多了剃毒，很多甚至連名字你都沒聽過驼壶，比如猴子排序未妹、睡眠排序等贺氓。最常用的：冒泡排序谋币、選擇排序棺克、插入排序、歸并排序咒吐、快速排序野建、計(jì)數(shù)排序、基數(shù)排序恬叹、桶排序候生。根據(jù)時(shí)間復(fù)雜度，我們分三類來學(xué)習(xí)绽昼，今天要講的就是 冒泡唯鸭、插入、選擇 排序算法硅确。

十種常見的的排序算法可以分兩大類：

1. 比較類排序：通過比較來決定元素的相對(duì)次序循未，由于其時(shí)間復(fù)雜度無法突破 O(nlog_n)陷猫，因此也叫做非線性時(shí)間排序。
2. 非比較類排序：不是通過比較元素來決定元素的相對(duì)次序，可以突破比較排序的時(shí)間下限绣檬，線性時(shí)間運(yùn)行舅巷，也叫做線性時(shí)間非比較類排序。

經(jīng)典算法

學(xué)會(huì)評(píng)估一個(gè)排序算法

學(xué)習(xí)算法河咽，除了知道原理以及代碼實(shí)現(xiàn)以外钠右，還有更重要的是學(xué)會(huì)如何評(píng)價(jià)、分析一個(gè)排序算法的 執(zhí)行效率忘蟹、內(nèi)存損耗飒房、穩(wěn)定性。

執(zhí)行效率

一般通過如下方面衡量：

1.最好媚值、最壞狠毯、平均時(shí)間復(fù)雜度

為何要區(qū)分這三種時(shí)間復(fù)雜度？第一褥芒，通過復(fù)雜度可以大致判斷算法的執(zhí)行次數(shù)嚼松。第二，對(duì)于要排序的數(shù)據(jù)有的無序锰扶、有的接近有序献酗，有序度不同不同對(duì)于執(zhí)行時(shí)間是不一樣的，所以我們要只掉不同數(shù)據(jù)場(chǎng)景下算法的性能坷牛。

2. 時(shí)間復(fù)雜度的系數(shù)罕偎、常數(shù)、低階

我們知道京闰，時(shí)間復(fù)雜度反應(yīng)的是數(shù)據(jù)規(guī)模 n 很大的時(shí)候的一個(gè)增長(zhǎng)趨勢(shì)颜及，所以它表示的時(shí)候會(huì)忽略系數(shù)、常數(shù)蹂楣、低階俏站。但是實(shí)際的軟件開發(fā)中，我們排序的可能是 10 個(gè)痊土、100 個(gè)肄扎、1000 個(gè)這樣規(guī)模很小的數(shù)據(jù)，所以施戴，在對(duì)同一階時(shí)間復(fù)雜度的排序算法性能對(duì)比的時(shí)候反浓，我們就要把系數(shù)、常數(shù)赞哗、低階也考慮進(jìn)來。

3.比較次數(shù)移動(dòng)（交換）數(shù)據(jù)次數(shù)
基于比較排序的算法執(zhí)行過程都會(huì)涉及兩個(gè)操作辆雾、一個(gè)是比較肪笋，另一個(gè)就是元素交換或者數(shù)據(jù)移動(dòng)。所以我們也要把數(shù)據(jù)交換或者移動(dòng)次數(shù)考慮進(jìn)來。

內(nèi)存消耗

算法的內(nèi)存消耗通過空間復(fù)雜度來衡量藤乙，不過在這里針對(duì)排序算法的內(nèi)存算好還有一個(gè)新概念猜揪，原地排序就是特指空間復(fù)雜度為 O(1) 的算法，這次所講的算法都是原地排序算法坛梁。

算法的穩(wěn)定性

如果待排序的序列中存在值相等的元素而姐，經(jīng)過排序之后，相等元素之間原有的先后順序不變划咐。** 比如 a 原本在 b 前面拴念，而 a=b ，排序之后 a 仍然在 b 的前面褐缠。

比如我們有一組數(shù)據(jù) 2政鼠，9，3队魏，4公般，8，3胡桨，按照大小排序之后就是 2官帘，3，3昧谊，4遏佣，8，9揽浙。

這組數(shù)據(jù)里有兩個(gè) 3状婶。經(jīng)過某種排序算法排序之后，如果兩個(gè) 3 的前后順序沒有改變馅巷，那我們就把這種排序算法叫作穩(wěn)定的排序算法膛虫；如果前后順序發(fā)生變化，那對(duì)應(yīng)的排序算法就叫作不穩(wěn)定的排序算法钓猬。

冒泡排序

冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)稍刀。每次冒泡操作都會(huì)對(duì)相鄰的兩個(gè)元素進(jìn)行比較，看是否滿足大小關(guān)系要求敞曹。如果不滿足就讓它倆互換账月。一次冒泡會(huì)讓至少一個(gè)元素移動(dòng)到它應(yīng)該在的位置，重復(fù) n 次澳迫，就完成了 n 個(gè)數(shù)據(jù)的排序工作局齿。

這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

作為最簡(jiǎn)單的排序算法之一橄登，冒泡排序給我的感覺就像 Abandon 在單詞書里出現(xiàn)的感覺一樣抓歼，每次都在第一頁第一位讥此，所以最熟悉。冒泡排序還有一種優(yōu)化算法谣妻，就是立一個(gè) flag萄喳，當(dāng)在一趟序列遍歷中元素沒有發(fā)生交換，則證明該序列已經(jīng)有序蹋半。但這種改進(jìn)對(duì)于提升性能來說并沒有什么太大作用他巨。

算法步驟

1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大减江，就交換他們兩個(gè)染突。

2. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)您市。這步做完后觉痛，最后的元素會(huì)是最大的數(shù)。

3. 針對(duì)所有的元素重復(fù)以上的步驟茵休，除了最后一個(gè)薪棒。

4. 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較榕莺。

   冒泡排序

/**
 * 冒泡排序: 時(shí)間復(fù)雜度 O(n2)俐芯，最壞時(shí)間復(fù)雜度 O(n2)，最好時(shí)間復(fù)雜度 O(n)钉鸯，平均時(shí)間復(fù)雜度 O(n2)
 * 空間復(fù)雜度 O(1)吧史，穩(wěn)定排序算法
 */
public class BubbleSort implements ComparisonSort {
    @Override
    public int[] sort(int[] sourceArray) {
        // 復(fù)制數(shù)組，不改變參數(shù)內(nèi)容
        int[] result = Arrays.copyOf(sourceArray, sourceArray.length);
        if (sourceArray.length <= 1) {
            return result;
        }
        int length = result.length;
        for (int i = 0; i < length; i++) {
            // 設(shè)定標(biāo)記唠雕，當(dāng)沒有數(shù)據(jù)需要交換的時(shí)候則說明已經(jīng)有序贸营，提前退出外部循環(huán)
            boolean hasChange = false;
            for (int j = 0; j < (length - 1) - i ; j++) {
                if (result[j] > result[j + 1]) {
                    // 數(shù)據(jù)交換
                    int temp = result[j];
                    result[j] = result[j + 1];
                    result[j + 1] = temp;
                    hasChange = true;
                }
            }
            if (!hasChange) {
                // 沒有數(shù)據(jù)交換，已經(jīng)有序,提前退出
                break;
            }
        }
        return result;
    }
}

那么問題來了岩睁，我們來分析下這個(gè)算法的效率如何钞脂，教大家學(xué)會(huì)如何評(píng)估一個(gè)算法：

1.冒泡是原地排序算法么？

因?yàn)槊芭莸倪^程只有相鄰數(shù)據(jù)的交換操作捕儒，屬于常量級(jí)別的臨時(shí)空間冰啃，所以空間復(fù)雜度是 O(1)，屬于原地排序算法刘莹。

2.是穩(wěn)定排序算法阎毅？

只有交換才改變兩個(gè)元素的前后順序，當(dāng)相鄰數(shù)據(jù)相等点弯，不做交換扇调，所以相同大小的數(shù)據(jù)在排序前后都不會(huì)改變順序，屬于穩(wěn)定排序算法蒲拉。

3.時(shí)間復(fù)雜度

最好時(shí)間復(fù)雜度：當(dāng)數(shù)據(jù)已經(jīng)有序肃拜，只需要一次冒泡痴腌，所以是 O(1)雌团。（ps：都已經(jīng)是正序了燃领，還要你冒泡何用）

最壞時(shí)間復(fù)雜度： 數(shù)據(jù)是倒序的，我們需要進(jìn)行 n 次冒泡操作锦援，所以最壞情況時(shí)間復(fù)雜度為 O(n2)猛蔽。（ps：寫一個(gè) for 循環(huán)反序輸出數(shù)據(jù)不就行了，干嘛要用你冒泡排序呢灵寺，我是閑的嗎）

插入排序

我們先來看一個(gè)問題曼库。一個(gè)有序的數(shù)組，我們往里面添加一個(gè)新的數(shù)據(jù)后略板，如何繼續(xù)保持?jǐn)?shù)據(jù)有序呢毁枯？很簡(jiǎn)單，我們只要遍歷數(shù)組叮称，找到數(shù)據(jù)應(yīng)該插入的位置將其插入即可种玛。

插入排序是一種最簡(jiǎn)單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列瓤檐，對(duì)于未排序數(shù)據(jù)赂韵，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入挠蛉。

插入排序也包含兩種操作祭示，一種是元素的比較，一種是元素的移動(dòng)谴古。當(dāng)我們需要將一個(gè)數(shù)據(jù) a 插入到已排序區(qū)間時(shí)质涛，需要拿 a 與已排序區(qū)間的元素依次比較大小，找到合適的插入位置掰担。找到插入點(diǎn)之后汇陆，我們還需要將插入點(diǎn)之后的元素順序往后移動(dòng)一位，這樣才能騰出位置給元素 a 插入恩敌。

插入排序

代碼如下所示：

/**
 * 插入排序：時(shí)間復(fù)雜度 O(n2),平均時(shí)間復(fù)雜度 O(n2),最好時(shí)間復(fù)雜度 O(n)瞬测，
 * 最壞時(shí)間復(fù)雜度 O(n2),空間時(shí)間復(fù)雜度 O(1).穩(wěn)定排序算法。
 */
public class InsertionSort implements ComparisonSort {

    @Override
    public int[] sort(int[] sourceArray) {
        int[] result = Arrays.copyOf(sourceArray, sourceArray.length);
        if (sourceArray.length <= 1) {
            return result;
        }
        // 從下標(biāo)為 1 開始比較選擇合適位置插入纠炮，因?yàn)橄聵?biāo) 0 只有一個(gè)元素月趟，默認(rèn)是有序
        int length = result.length;
        for (int i = 1; i < length; i++) {
            // 待插入數(shù)據(jù)
            int insertValue = result[i];
            // 從已排序的序列最右邊元素開始比較，找到比待插入樹更小的數(shù)位置
            int j = i - 1;
            for (; j >= 0; j--){
                if (result[j] > insertValue) {
                    // 向后移動(dòng)數(shù)據(jù),騰出待插入位置
                    result[j + 1] = result[j];
                } else {
                    // 找到待插入位置恢口，跳出循環(huán)
                    break;
                }
            }
            // 插入數(shù)據(jù)孝宗，因?yàn)榍懊娑鄨?zhí)行了 j--，
            result[j + 1] = insertValue;
        }
        return result;
    }
}

依然繼續(xù)分析該算法的性能耕肩。

1.是否是原地排序算法

從實(shí)現(xiàn)過程就知道因妇，插入排序不需要額外的存儲(chǔ)空間问潭，所以空間復(fù)雜度是 O(1)，屬于原地排序婚被。

2.是否是穩(wěn)定排序算法

對(duì)于值相等的元素狡忙，我們選擇將數(shù)據(jù)插入到前面元素的侯娜，這樣就保證原有的前后順序不變址芯，屬于穩(wěn)定排序算法灾茁。

3.時(shí)間復(fù)雜度

如果要排序的數(shù)據(jù)已經(jīng)是有序的，我們并不需要搬移任何數(shù)據(jù)谷炸。如果我們從尾到頭在有序數(shù)據(jù)組里面查找插入位置北专，每次只需要比較一個(gè)數(shù)據(jù)就能確定插入的位置。所以這種情況下旬陡，最好是時(shí)間復(fù)雜度為 O(n)拓颓。注意，這里是從尾到頭遍歷已經(jīng)有序的數(shù)據(jù)描孟。

如果數(shù)組是倒序的驶睦，每次插入都相當(dāng)于在數(shù)組的第一個(gè)位置插入新的數(shù)據(jù)，所以需要移動(dòng)大量的數(shù)據(jù)画拾，所以最壞情況時(shí)間復(fù)雜度為 O(n2)喘批。

還記得我們?cè)跀?shù)組中插入一個(gè)數(shù)據(jù)的平均時(shí)間復(fù)雜度是多少嗎利术？沒錯(cuò)印蓖，是 O(n)匾鸥。所以，對(duì)于插入排序來說蜜另，每次插入操作都相當(dāng)于在數(shù)組中插入一個(gè)數(shù)據(jù)适室，循環(huán)執(zhí)行 n 次插入操作，所以平均時(shí)間復(fù)雜度為 O(n2)举瑰。

選擇排序

選擇排序是一種簡(jiǎn)單直觀的排序算法捣辆，無論什么數(shù)據(jù)進(jìn)去都是 O(n2) 的時(shí)間復(fù)雜度。所以用到它的時(shí)候此迅，數(shù)據(jù)規(guī)模越小越好汽畴。

選擇排序算法的實(shí)現(xiàn)思路有點(diǎn)類似插入排序，也分已排序區(qū)間和未排序區(qū)間耸序。但是選擇排序每次會(huì)從未排序區(qū)間中找到最小的元素忍些，將其放到已排序區(qū)間的末尾。

算法步驟

1. 首先在未排序序列中找到最锌补帧（大）元素罢坝，存放到排序序列的起始位置
2. 再從剩余未排序元素中繼續(xù)尋找最小（大）元素搅窿，然后放到已排序序列的末尾嘁酿。
3. 重復(fù)第二步隙券，直到所有元素均排序完畢。

選擇排序

代碼如下：

public class SelectionSort implements ComparisonSort {

    @Override
    public int[] sort(int[] sourceArray) {
        int length = sourceArray.length;
        int[] result = Arrays.copyOf(sourceArray, length);
        if (length <= 0) {
            return result;
        }
        // 一共需要 length - 1 輪比較
        for (int i = 0; i < length - 1; i++) {
            // 每輪需要比較的次數(shù) length - i闹司，找出最小元素下標(biāo)
            int minIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (result[j] < result[minIndex]) {
                    // 查出每次最小遠(yuǎn)元素下標(biāo)
                    minIndex = j;
                }
            }
            // 將當(dāng)前 i 位置的數(shù)據(jù)與最小值交換數(shù)據(jù)
            if (i != minIndex) {
                int temp = result[i];
                result[i] = result[minIndex];
                result[minIndex] = temp;
            }
        }
        return result;
    }
}

首先娱仔，選擇排序空間復(fù)雜度為 O(1)，是一種原地排序算法开仰。選擇排序的最好情況時(shí)間復(fù)雜度拟枚、最壞情況和平均情況時(shí)間復(fù)雜度都為 O(n2)薪铜。

那選擇排序是穩(wěn)定的排序算法嗎众弓？

答案是否定的，選擇排序是一種不穩(wěn)定的排序算法隔箍。從我前面畫的那張圖中谓娃，你可以看出來，選擇排序每次都要找剩余未排序元素中的最小值蜒滩，并和前面的元素交換位置滨达，這樣破壞了穩(wěn)定性。

比如 5俯艰，8捡遍，5，2竹握，9 這樣一組數(shù)據(jù)画株，使用選擇排序算法來排序的話，第一次找到最小元素 2啦辐，與第一個(gè) 5 交換位置谓传，那第一個(gè) 5 和中間的 5 順序就變了，所以就不穩(wěn)定了芹关。正是因此续挟，相對(duì)于冒泡排序和插入排序，選擇排序就稍微遜色了侥衬。

總結(jié)

這三種時(shí)間復(fù)雜度為 O(n2) 的排序算法中诗祸，冒泡排序、選擇排序轴总，可能就純粹停留在理論的層面了直颅，學(xué)習(xí)的目的也只是為了開拓思維，實(shí)際開發(fā)中應(yīng)用并不多肘习，但是插入排序還是挺有用的际乘。后面講排序優(yōu)化的時(shí)候，我會(huì)講到漂佩，有些編程語言中的排序函數(shù)的實(shí)現(xiàn)原理會(huì)用到插入排序算法脖含。（希爾排序就是插入排序的一種優(yōu)化）

今天講的這三種排序算法罪塔，實(shí)現(xiàn)代碼都非常簡(jiǎn)單，對(duì)于小規(guī)模數(shù)據(jù)的排序养葵，用起來非常高效征堪。但是在大規(guī)模數(shù)據(jù)排序的時(shí)候，這個(gè)時(shí)間復(fù)雜度還是稍微有點(diǎn)高关拒，所以我們更傾向于用下一節(jié)要講的時(shí)間復(fù)雜度為 O(nlogn) 的排序算法佃蚜。

算法執(zhí)行效率

課后思考

最后給大家一個(gè)問題，答案可在后臺(tái)發(fā)送 「插入」獲取答案着绊，也可以加群跟我們一起討論谐算。

問題是：插入排序和冒泡排序時(shí)間復(fù)雜度相同，都是 O(n2),實(shí)際開發(fā)中更傾向于插入排序而不是冒泡排序

碼哥字節(jié)