摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩(wěn)定的排序算法。選擇排序思路選擇排序算法的實現(xiàn)思路有點類似插入排序，也分已排序區(qū)間和未排序區(qū)間。

算法為王。

想學好前端，先練好內(nèi)功，只有內(nèi)功深厚者，前端之路才會走得更遠。

筆者寫的 JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 系列用的語言是 JavaScript ，旨在入門數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復習。

之所以把冒泡排序、選擇排序、插入排序放在一起比較，是因為它們的平均時間復雜度都為 O(n²)。

請大家?guī)е鴨栴}：為什么插入排序比冒泡排序更受歡迎 ？來閱讀下文。

復雜度分析是整個算法學習的精髓。

時間復雜度: 一個算法執(zhí)行所耗費的時間。

空間復雜度: 運行完一個程序所需內(nèi)存的大小。

時間和空間復雜度的詳解，請看 JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 時間和空間復雜度。

學習排序算法，我們除了學習它的算法原理、代碼實現(xiàn)之外，更重要的是要學會如何評價、分析一個排序算法。

分析一個排序算法，要從 執(zhí)行效率、內(nèi)存消耗、穩(wěn)定性 三方面入手。

1. 最好情況、最壞情況、平均情況時間復雜度

我們在分析排序算法的時間復雜度時，要分別給出最好情況、最壞情況、平均情況下的時間復雜度。
除此之外，你還要說出最好、最壞時間復雜度對應的要排序的原始數(shù)據(jù)是什么樣的。

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

我們知道，時間復雜度反應的是數(shù)據(jù)規(guī)模 n 很大的時候的一個增長趨勢，所以它表示的時候會忽略系數(shù)、常數(shù)、低階。

但是實際的軟件開發(fā)中，我們排序的可能是 10 個、100 個、1000 個這樣規(guī)模很小的數(shù)據(jù)，所以，在對同一階時間復雜度的排序算法性能對比的時候，我們就要把系數(shù)、常數(shù)、低階也考慮進來。

3. 比較次數(shù)和交換（或移動）次數(shù)

這一節(jié)和下一節(jié)講的都是基于比較的排序算法。基于比較的排序算法的執(zhí)行過程，會涉及兩種操作，一種是元素比較大小，另一種是元素交換或移動。

所以，如果我們在分析排序算法的執(zhí)行效率的時候，應該把比較次數(shù)和交換（或移動）次數(shù)也考慮進去。

也就是看空間復雜度。

還需要知道如下術語：

內(nèi)排序：所有排序操作都在內(nèi)存中完成；

外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進行；

原地排序：原地排序算法，就是特指空間復雜度是 O(1) 的排序算法。

其中，冒泡排序就是原地排序算法。

穩(wěn)定：如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。

比如： a 原本在 b 前面，而 a = b，排序之后，a 仍然在 b 的前面；

不穩(wěn)定：如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序改變。

比如：a 原本在 b 的前面，而 a = b，排序之后， a 在 b 的后面；

思想

冒泡排序只會操作相鄰的兩個數(shù)據(jù)。

每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關系要求。如果不滿足就讓它倆互換。

一次冒泡會讓至少一個元素移動到它應該在的位置，重復 n 次，就完成了 n 個數(shù)據(jù)的排序工作。

特點

優(yōu)點：排序算法的基礎，簡單實用易于理解。

缺點：比較次數(shù)多，效率較低。

實現(xiàn)

// 冒泡排序（未優(yōu)化）
const bubbleSort = arr => {
    console.time("改進前冒泡排序耗時");
    const length = arr.length;
    if (length <= 1) return;
    // i < length - 1 是因為外層只需要 length-1 次就排好了，第 length 次比較是多余的。
    for (let i = 0; i < length - 1; i++) {
        // j < length - i - 1 是因為內(nèi)層的 length-i-1 到 length-1 的位置已經(jīng)排好了，不需要再比較一次。
        for (let j = 0; j < length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    console.log("改進前 arr :", arr);
    console.timeEnd("改進前冒泡排序耗時");
};

優(yōu)化：當某次冒泡操作已經(jīng)沒有數(shù)據(jù)交換時，說明已經(jīng)達到完全有序，不用再繼續(xù)執(zhí)行后續(xù)的冒泡操作。

// 冒泡排序（已優(yōu)化）
const bubbleSort2 = arr => {
    console.time("改進后冒泡排序耗時");
    const length = arr.length;
    if (length <= 1) return;
    // i < length - 1 是因為外層只需要 length-1 次就排好了，第 length 次比較是多余的。
    for (let i = 0; i < length - 1; i++) {
        let hasChange = false; // 提前退出冒泡循環(huán)的標志位
        // j < length - i - 1 是因為內(nèi)層的 length-i-1 到 length-1 的位置已經(jīng)排好了，不需要再比較一次。
        for (let j = 0; j < length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                hasChange = true; // 表示有數(shù)據(jù)交換
            }
        }

        if (!hasChange) break; // 如果 false 說明所有元素已經(jīng)到位，沒有數(shù)據(jù)交換，提前退出
    }
    console.log("改進后 arr :", arr);
    console.timeEnd("改進后冒泡排序耗時");
};

測試

// 測試
const arr = [7, 8, 4, 5, 6, 3, 2, 1];
bubbleSort(arr);
// 改進前 arr : [1, 2, 3, 4, 5, 6, 7, 8]
// 改進前冒泡排序耗時: 0.43798828125ms

const arr2 = [7, 8, 4, 5, 6, 3, 2, 1];
bubbleSort2(arr2);
// 改進后 arr : [1, 2, 3, 4, 5, 6, 7, 8]
// 改進后冒泡排序耗時: 0.318115234375ms

分析

第一，冒泡排序是原地排序算法嗎 ？

冒泡的過程只涉及相鄰數(shù)據(jù)的交換操作，只需要常量級的臨時空間，所以它的空間復雜度為 O(1)，是一個原地排序算法。

第二，冒泡排序是穩(wěn)定的排序算法嗎 ？

在冒泡排序中，只有交換才可以改變兩個元素的前后順序。
為了保證冒泡排序算法的穩(wěn)定性，當有相鄰的兩個元素大小相等的時候，我們不做交換，相同大小的數(shù)據(jù)在排序前后不會改變順序。
所以冒泡排序是穩(wěn)定的排序算法。

第三，冒泡排序的時間復雜度是多少 ？

最佳情況：T(n) = O(n)，當數(shù)據(jù)已經(jīng)是正序時。
最差情況：T(n) = O(n²)，當數(shù)據(jù)是反序時。
平均情況：T(n) = O(n²)。

動畫

插入排序又為分為 直接插入排序 和優(yōu)化后的 拆半插入排序 與 希爾排序，我們通常說的插入排序是指直接插入排序。

一、直接插入

思想

一般人打撲克牌，整理牌的時候，都是按牌的大小（從小到大或者從大到小）整理牌的，那每摸一張新牌，就掃描自己的牌，把新牌插入到相應的位置。

插入排序的工作原理：通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。

步驟

從第一個元素開始，該元素可以認為已經(jīng)被排序；

取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；

如果該元素（已排序）大于新元素，將該元素移到下一位置；

重復步驟 3，直到找到已排序的元素小于或者等于新元素的位置；

將新元素插入到該位置后；

重復步驟 2~5。

實現(xiàn)

// 插入排序
const insertionSort = array => {
    const len = array.length;
    if (len <= 1) return

    let preIndex, current;
    for (let i = 1; i < len; i++) {
        preIndex = i - 1; //待比較元素的下標
        current = array[i]; //當前元素
        while (preIndex >= 0 && array[preIndex] > current) {
            //前置條件之一: 待比較元素比當前元素大
            array[preIndex + 1] = array[preIndex]; //將待比較元素后移一位
            preIndex--; //游標前移一位
        }
        if (preIndex + 1 != i) {
            //避免同一個元素賦值給自身
            array[preIndex + 1] = current; //將當前元素插入預留空位
            console.log("array :", array);
        }
    }
    return array;
};

測試

// 測試
const array = [5, 4, 3, 2, 1];
console.log("原始 array :", array);
insertionSort(array);
// 原始 array:   ?[5, 4, 3, 2, 1]
// array: ?         [4, 5, 3, 2, 1]
// array: ?         [3, 4, 5, 2, 1]
// array:         ?[2, 3, 4, 5, 1]
// array: ?         [1, 2, 3, 4, 5]

分析

第一，插入排序是原地排序算法嗎 ？

插入排序算法的運行并不需要額外的存儲空間，所以空間復雜度是 O(1)，所以，這是一個原地排序算法。

第二，插入排序是穩(wěn)定的排序算法嗎 ？

在插入排序中，對于值相同的元素，我們可以選擇將后面出現(xiàn)的元素，插入到前面出現(xiàn)元素的后面，這樣就可以保持原有的前后順序不變，所以插入排序是穩(wěn)定的排序算法。

第三，插入排序的時間復雜度是多少 ？

最佳情況：T(n) = O(n)，當數(shù)據(jù)已經(jīng)是正序時。
最差情況：T(n) = O(n²)，當數(shù)據(jù)是反序時。
平均情況：T(n) = O(n²)。

動畫

二、拆半插入

插入排序也有一種優(yōu)化算法，叫做拆半插入。

思想

折半插入排序是直接插入排序的升級版，鑒于插入排序第一部分為已排好序的數(shù)組, 我們不必按順序依次尋找插入點, 只需比較它們的中間值與待插入元素的大小即可。

步驟

取 0 ~ i-1 的中間點 ( m = (i-1)>>1 )，array[i] 與 array[m] 進行比較，若 array[i] < array[m]，則說明待插入的元素 array[i] 應該處于數(shù)組的 0 ~ m 索引之間；反之，則說明它應該處于數(shù)組的 m ~ i-1 索引之間。

重復步驟 1，每次縮小一半的查找范圍，直至找到插入的位置。

將數(shù)組中插入位置之后的元素全部后移一位。

在指定位置插入第 i 個元素。

注：x>>1 是位運算中的右移運算，表示右移一位，等同于 x 除以 2 再取整，即 x>>1 == Math.floor(x/2) 。

// 折半插入排序
const binaryInsertionSort = array => {
    const len = array.length;
    if (len <= 1) return;

    let current, i, j, low, high, m;
    for (i = 1; i < len; i++) {
        low = 0;
        high = i - 1;
        current = array[i];

        while (low <= high) {
            //步驟 1 & 2 : 折半查找
            m = (low + high) >> 1; // 注: x>>1 是位運算中的右移運算, 表示右移一位, 等同于 x 除以 2 再取整, 即 x>>1 == Math.floor(x/2) .
            if (array[i] >= array[m]) {
                //值相同時, 切換到高半?yún)^(qū)，保證穩(wěn)定性
                low = m + 1; //插入點在高半?yún)^(qū)
            } else {
                high = m - 1; //插入點在低半?yún)^(qū)
            }
        }
        for (j = i; j > low; j--) {
            //步驟 3: 插入位置之后的元素全部后移一位
            array[j] = array[j - 1];
            console.log("array2 :", JSON.parse(JSON.stringify(array)));
        }
        array[low] = current; //步驟 4: 插入該元素
    }
    console.log("array2 :", JSON.parse(JSON.stringify(array)));
    return array;
};

測試

const array2 = [5, 4, 3, 2, 1];
console.log("原始 array2:", array2);
binaryInsertionSort(array2);
// 原始 array2:  [5, 4, 3, 2, 1]
// array2 : ??  [5, 5, 3, 2, 1]
// array2 : ??  [4, 5, 5, 2, 1]
// array2 : ??  [4, 4, 5, 2, 1]
// array2 : ??  [3, 4, 5, 5, 1]
// array2 : ??  [3, 4, 4, 5, 1]
// array2 : ??  [3, 3, 4, 5, 1]
// array2 : ??  [2, 3, 4, 5, 5]
// array2 : ??  [2, 3, 4, 4, 5]
// array2 : ??  [2, 3, 3, 4, 5]
// array2 : ??  [2, 2, 3, 4, 5]
// array2 : ??  [1, 2, 3, 4, 5]

注意：和直接插入排序類似，折半插入排序每次交換的是相鄰的且值為不同的元素，它并不會改變值相同的元素之間的順序，因此它是穩(wěn)定的。

三、希爾排序

希爾排序是一個平均時間復雜度為 O(nlogn) 的算法，會在下一個章節(jié)和 歸并排序、快速排序、堆排序 一起講，本文就不展開了。

思路

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

步驟

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。

重復第二步，直到所有元素均排序完畢。

實現(xiàn)

const selectionSort = array => {
    const len = array.length;
    let minIndex, temp;
    for (let i = 0; i < len - 1; i++) {
        minIndex = i;
        for (let j = i + 1; j < len; j++) {
            if (array[j] < array[minIndex]) {
                // 尋找最小的數(shù)
                minIndex = j; // 將最小數(shù)的索引保存
            }
        }
        temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
        console.log("array: ", array);
    }
    return array;
};

測試

// 測試
const array = [5, 4, 3, 2, 1];
console.log("原始array:", array);
selectionSort(array);
// 原始 array: ?[5, 4, 3, 2, 1]
// array: ?         [1, 4, 3, 2, 5]
// array: ?         [1, 2, 3, 4, 5]
// array:         ?[1, 2, 3, 4, 5]
// array: ?         [1, 2, 3, 4, 5]

分析

第一，選擇排序是原地排序算法嗎 ？

選擇排序空間復雜度為 O(1)，是一種原地排序算法。

第二，選擇排序是穩(wěn)定的排序算法嗎 ？

選擇排序每次都要找剩余未排序元素中的最小值，并和前面的元素交換位置，這樣破壞了穩(wěn)定性。所以，選擇排序是一種不穩(wěn)定的排序算法。

第三，選擇排序的時間復雜度是多少 ？

無論是正序還是逆序，選擇排序都會遍歷 n² / 2 次來排序，所以，最佳、最差和平均的復雜度是一樣的。
最佳情況：T(n) = O(n²)。
最差情況：T(n) = O(n²)。
平均情況：T(n) = O(n²)。

動畫

為什么插入排序比冒泡排序更受歡迎 ？

冒泡排序和插入排序的時間復雜度都是 O(n²)，都是原地排序算法，為什么插入排序要比冒泡排序更受歡迎呢 ？

這里關乎到 逆序度、滿有序度、有序度。

有序度：是數(shù)組中具有有序關系的元素對的個數(shù)。

有序元素對用數(shù)學表達式表示就是這樣：

有序元素對：a[i] <= a[j], 如果 i < j。

滿有序度：把完全有序的數(shù)組的有序度叫作 滿有序度。

逆序度：正好跟有序度相反（默認從小到大為有序）。

逆序元素對：a[i] > a[j], 如果 i < j。

同理，對于一個倒序排列的數(shù)組，比如 6，5，4，3，2，1，有序度是 0；
對于一個完全有序的數(shù)組，比如 1，2，3，4，5，6，有序度就是 n*(n-1)/2 ，也就是滿有序度為 15。

原因

冒泡排序不管怎么優(yōu)化，元素交換的次數(shù)是一個固定值，是原始數(shù)據(jù)的逆序度。

插入排序是同樣的，不管怎么優(yōu)化，元素移動的次數(shù)也等于原始數(shù)據(jù)的逆序度。

但是，冒泡排序的數(shù)據(jù)交換要比插入排序的數(shù)據(jù)移動要復雜，冒泡排序需要 3 個賦值操作，而插入排序只需要 1 個，數(shù)據(jù)量一旦大了，這差別就非常明顯了。

復雜性對比

| 名稱 | 最好 | 平均 | 最壞 | 內(nèi)存 | 穩(wěn)定性 | 備注 |
| :------: | :------: | :------: | :------: | :------: | :------: | :------: |
| 冒泡 | n | n² | n² | 1 | Yes | ... |
| 插入 | n | n² | n² | 1 | Yes | ... |
| 選擇 | n² | n² | n² | 1 | No | ... |

算法可視化工具

這里推薦一個算法可視化工具。

算法可視化工具 algorithm-visualizer 是一個交互式的在線平臺，可以從代碼中可視化算法，還可以看到代碼執(zhí)行的過程。

效果如下圖。

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 的系列文章，堅持 3 - 7 天左右更新一篇，暫定計劃如下表。

| 標題 | 鏈接 |
| :------ | :------ |
| 時間和空間復雜度 | https://github.com/biaochenxu... |
| 線性表（數(shù)組、鏈表、棧、隊列） | https://github.com/biaochenxu... |
| 實現(xiàn)一個前端路由，如何實現(xiàn)瀏覽器的前進與后退 ？| https://github.com/biaochenxu... |
| 棧內(nèi)存與堆內(nèi)存 、淺拷貝與深拷貝 | https://github.com/biaochenxu... |
| 遞歸 | https://github.com/biaochenxu... |
| 非線性表（樹、堆） | https://github.com/biaochenxu... |
| 冒泡排序、選擇排序、插入排序 | https://github.com/biaochenxu... |
| 歸并排序、快速排序、希爾排序、堆排序 | 精彩待續(xù) |
| 計數(shù)排序、桶排序、基數(shù)排序 | 精彩待續(xù) |
| 十大經(jīng)典排序匯總 | 精彩待續(xù) |
| 強烈推薦 GitHub 上值得前端學習的數(shù)據(jù)結(jié)構(gòu)與算法項目 | https://github.com/biaochenxu... |

如果有錯誤或者不嚴謹?shù)牡胤剑垊毡亟o予指正，十分感謝。

喜歡就點個贊吧。

文中所有的代碼及測試事例都已經(jīng)放到我的 GitHub 上了。

參考文章：

數(shù)據(jù)結(jié)構(gòu)與算法之美

十大經(jīng)典排序算法總結(jié)（JavaScript描述）

JS中可能用得到的全部的排序算法