摘要：筆者寫(xiě)的數(shù)據(jù)結(jié)構(gòu)與算法之美系列用的語(yǔ)言是，旨在入門(mén)數(shù)據(jù)結(jié)構(gòu)與算法和方便以后復(fù)習(xí)。這應(yīng)該是目前較為簡(jiǎn)單的十大經(jīng)典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經(jīng)典排序算法冒泡排序思想冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)。

算法為王。
想學(xué)好前端，先練好內(nèi)功，內(nèi)功不行，就算招式練的再花哨，終究成不了高手；只有內(nèi)功深厚者，前端之路才會(huì)走得更遠(yuǎn)。

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

文中包含了 十大經(jīng)典排序算法 的思想、代碼實(shí)現(xiàn)、一些例子、復(fù)雜度分析、動(dòng)畫(huà)、還有算法可視化工具。

這應(yīng)該是目前較為簡(jiǎn)單的 JavaScript 十大經(jīng)典排序算法 的文章講解了吧。

復(fù)雜度分析是整個(gè)算法學(xué)習(xí)的精髓。

時(shí)間復(fù)雜度: 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間。

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

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

學(xué)習(xí)排序算法，我們除了學(xué)習(xí)它的算法原理、代碼實(shí)現(xiàn)之外，更重要的是要學(xué)會(huì)如何評(píng)價(jià)、分析一個(gè)排序算法。

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

1. 最好情況、最壞情況、平均情況時(shí)間復(fù)雜度

我們?cè)诜治雠判蛩惴ǖ臅r(shí)間復(fù)雜度時(shí)，要分別給出最好情況、最壞情況、平均情況下的時(shí)間復(fù)雜度。
除此之外，你還要說(shuō)出最好、最壞時(shí)間復(fù)雜度對(duì)應(yīng)的要排序的原始數(shù)據(jù)是什么樣的。

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

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

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

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

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

所以，如果我們?cè)诜治雠判蛩惴ǖ膱?zhí)行效率的時(shí)候，應(yīng)該把比較次數(shù)和交換（或移動(dòng)）次數(shù)也考慮進(jìn)去。

也就是看空間復(fù)雜度。

還需要知道如下術(shù)語(yǔ)：

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

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

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

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

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

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

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

思想

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

每次冒泡操作都會(huì)對(duì)相鄰的兩個(gè)元素進(jìn)行比較，看是否滿足大小關(guān)系要求。如果不滿足就讓它倆互換。

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

特點(diǎn)

優(yōu)點(diǎn)：排序算法的基礎(chǔ)，簡(jiǎn)單實(shí)用易于理解。

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

實(shí)現(xiàn)

// 冒泡排序（未優(yōu)化）
const bubbleSort = arr => {
    console.time("改進(jìn)前冒泡排序耗時(shí)");
    const length = arr.length;
    if (length <= 1) return;
    // i < length - 1 是因?yàn)橥鈱又恍枰?length-1 次就排好了，第 length 次比較是多余的。
    for (let i = 0; i < length - 1; i++) {
        // j < length - i - 1 是因?yàn)閮?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("改進(jìn)前 arr :", arr);
    console.timeEnd("改進(jìn)前冒泡排序耗時(shí)");
};

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

// 冒泡排序（已優(yōu)化）
const bubbleSort2 = arr => {
    console.time("改進(jìn)后冒泡排序耗時(shí)");
    const length = arr.length;
    if (length <= 1) return;
    // i < length - 1 是因?yàn)橥鈱又恍枰?length-1 次就排好了，第 length 次比較是多余的。
    for (let i = 0; i < length - 1; i++) {
        let hasChange = false; // 提前退出冒泡循環(huán)的標(biāo)志位
        // j < length - i - 1 是因?yàn)閮?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 說(shuō)明所有元素已經(jīng)到位，沒(méi)有數(shù)據(jù)交換，提前退出
    }
    console.log("改進(jìn)后 arr :", arr);
    console.timeEnd("改進(jìn)后冒泡排序耗時(shí)");
};

測(cè)試

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

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

分析

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

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

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

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

第三，冒泡排序的時(shí)間復(fù)雜度是多少 ？

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

動(dòng)畫(huà)

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

一、直接插入

思想

一般人打撲克牌，整理牌的時(shí)候，都是按牌的大?。◤男〉酱蠡蛘邚拇蟮叫。┱砼频?，那每摸一張新牌，就掃描自己的牌，把新牌插入到相應(yīng)的位置。

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

步驟

從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；

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

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

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

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

重復(fù)步驟 2 ~ 5。

實(shí)現(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; //待比較元素的下標(biāo)
        current = array[i]; //當(dāng)前元素
        while (preIndex >= 0 && array[preIndex] > current) {
            //前置條件之一: 待比較元素比當(dāng)前元素大
            array[preIndex + 1] = array[preIndex]; //將待比較元素后移一位
            preIndex--; //游標(biāo)前移一位
        }
        if (preIndex + 1 != i) {
            //避免同一個(gè)元素賦值給自身
            array[preIndex + 1] = current; //將當(dāng)前元素插入預(yù)留空位
            console.log("array :", array);
        }
    }
    return array;
};

測(cè)試

// 測(cè)試
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]

分析

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

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

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

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

第三，插入排序的時(shí)間復(fù)雜度是多少 ？

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

動(dòng)畫(huà)

二、拆半插入

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

思想

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

步驟

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

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

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

在指定位置插入第 i 個(gè)元素。

注：x >> 1 是位運(yùn)算中的右移運(yùn)算，表示右移一位，等同于 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 是位運(yùn)算中的右移運(yùn)算, 表示右移一位, 等同于 x 除以 2 再取整, 即 x>>1 == Math.floor(x/2) .
            if (array[i] >= array[m]) {
                //值相同時(shí), 切換到高半?yún)^(qū)，保證穩(wěn)定性
                low = m + 1; //插入點(diǎn)在高半?yún)^(qū)
            } else {
                high = m - 1; //插入點(diǎn)在低半?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;
};

測(cè)試

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]

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

三、希爾排序

希爾排序是一個(gè)平均時(shí)間復(fù)雜度為 O(n log n) 的算法，會(huì)在下一個(gè)章節(jié)和 歸并排序、快速排序、堆排序 一起講，本文就不展開(kāi)了。

思路

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

步驟

首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?。

再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。

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

實(shí)現(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;
};

測(cè)試

// 測(cè)試
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]

分析

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

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

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

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

第三，選擇排序的時(shí)間復(fù)雜度是多少 ？

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

動(dòng)畫(huà)

思想

排序一個(gè)數(shù)組，我們先把數(shù)組從中間分成前后兩部分，然后對(duì)前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了。

歸并排序采用的是分治思想。

分治，顧名思義，就是分而治之，將一個(gè)大問(wèn)題分解成小的子問(wèn)題來(lái)解決。小的子問(wèn)題解決了，大問(wèn)題也就解決了。

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

實(shí)現(xiàn)

const mergeSort = arr => {
    //采用自上而下的遞歸方法
    const len = arr.length;
    if (len < 2) {
        return arr;
    }
    // length >> 1 和 Math.floor(len / 2) 等價(jià)
    let middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle); // 拆分為兩個(gè)子數(shù)組
    return merge(mergeSort(left), mergeSort(right));
};

const merge = (left, right) => {
    const result = [];

    while (left.length && right.length) {
        // 注意: 判斷的條件是小于或等于，如果只是小于，那么排序?qū)⒉环€(wěn)定.
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length) result.push(left.shift());

    while (right.length) result.push(right.shift());

    return result;
};

測(cè)試

// 測(cè)試
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.time("歸并排序耗時(shí)");
console.log("arr :", mergeSort(arr));
console.timeEnd("歸并排序耗時(shí)");
// arr : [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
// 歸并排序耗時(shí): 0.739990234375ms

分析

第一，歸并排序是原地排序算法嗎 ？

這是因?yàn)闅w并排序的合并函數(shù)，在合并兩個(gè)有序數(shù)組為一個(gè)有序數(shù)組時(shí)，需要借助額外的存儲(chǔ)空間。
實(shí)際上，盡管每次合并操作都需要申請(qǐng)額外的內(nèi)存空間，但在合并完成之后，臨時(shí)開(kāi)辟的內(nèi)存空間就被釋放掉了。在任意時(shí)刻，CPU 只會(huì)有一個(gè)函數(shù)在執(zhí)行，也就只會(huì)有一個(gè)臨時(shí)的內(nèi)存空間在使用。臨時(shí)內(nèi)存空間最大也不會(huì)超過(guò) n 個(gè)數(shù)據(jù)的大小，所以空間復(fù)雜度是 O(n)。
所以，歸并排序不是原地排序算法。

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

merge 方法里面的 left[0] <= right[0] ，保證了值相同的元素，在合并前后的先后順序不變。歸并排序是穩(wěn)定的排序方法。

第三，歸并排序的時(shí)間復(fù)雜度是多少 ？

從效率上看，歸并排序可算是排序算法中的佼佼者。假設(shè)數(shù)組長(zhǎng)度為 n，那么拆分?jǐn)?shù)組共需 logn 步，又每步都是一個(gè)普通的合并子數(shù)組的過(guò)程，時(shí)間復(fù)雜度為 O(n)，故其綜合時(shí)間復(fù)雜度為 O(n log n)。
最佳情況：T(n) = O(n log n)。
最差情況：T(n) = O(n log n)。
平均情況：T(n) = O(n log n)。

動(dòng)畫(huà)

快速排序的特點(diǎn)就是快，而且效率高！它是處理大數(shù)據(jù)最快的排序算法之一。

思想

先找到一個(gè)基準(zhǔn)點(diǎn)（一般指數(shù)組的中部），然后數(shù)組被該基準(zhǔn)點(diǎn)分為兩部分，依次與該基準(zhǔn)點(diǎn)數(shù)據(jù)比較，如果比它小，放左邊；反之，放右邊。

左右分別用一個(gè)空數(shù)組去存儲(chǔ)比較后的數(shù)據(jù)。

最后遞歸執(zhí)行上述操作，直到數(shù)組長(zhǎng)度 <= 1;

特點(diǎn)：快速，常用。

缺點(diǎn)：需要另外聲明兩個(gè)數(shù)組，浪費(fèi)了內(nèi)存空間資源。

實(shí)現(xiàn)

方法一：

const quickSort1 = arr => {
    if (arr.length <= 1) {
        return arr;
    }
    //取基準(zhǔn)點(diǎn)
    const midIndex = Math.floor(arr.length / 2);
    //取基準(zhǔn)點(diǎn)的值，splice(index,1) 則返回的是含有被刪除的元素的數(shù)組。
    const valArr = arr.splice(midIndex, 1);
    const midIndexVal = valArr[0];
    const left = []; //存放比基準(zhǔn)點(diǎn)小的數(shù)組
    const right = []; //存放比基準(zhǔn)點(diǎn)大的數(shù)組
    //遍歷數(shù)組，進(jìn)行判斷分配
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < midIndexVal) {
            left.push(arr[i]); //比基準(zhǔn)點(diǎn)小的放在左邊數(shù)組
        } else {
            right.push(arr[i]); //比基準(zhǔn)點(diǎn)大的放在右邊數(shù)組
        }
    }
    //遞歸執(zhí)行以上操作，對(duì)左右兩個(gè)數(shù)組進(jìn)行操作，直到數(shù)組長(zhǎng)度為 <= 1
    return quickSort1(left).concat(midIndexVal, quickSort1(right));
};
const array2 = [5, 4, 3, 2, 1];
console.log("quickSort1 ", quickSort1(array2));
// quickSort1: [1, 2, 3, 4, 5]

方法二：

// 快速排序
const quickSort = (arr, left, right) => {
    let len = arr.length,
        partitionIndex;
    left = typeof left != "number" ? 0 : left;
    right = typeof right != "number" ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
};

const partition = (arr, left, right) => {
    //分區(qū)操作
    let pivot = left, //設(shè)定基準(zhǔn)值（pivot）
        index = pivot + 1;
    for (let i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
};

const swap = (arr, i, j) => {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

測(cè)試

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

分析

第一，快速排序是原地排序算法嗎 ？

因?yàn)?partition() 函數(shù)進(jìn)行分區(qū)時(shí)，不需要很多額外的內(nèi)存空間，所以快排是原地排序算法。

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

和選擇排序相似，快速排序每次交換的元素都有可能不是相鄰的，因此它有可能打破原來(lái)值為相同的元素之間的順序。因此，快速排序并不穩(wěn)定。

第三，快速排序的時(shí)間復(fù)雜度是多少 ？

極端的例子：如果數(shù)組中的數(shù)據(jù)原來(lái)已經(jīng)是有序的了，比如 1，3，5，6，8。如果我們每次選擇最后一個(gè)元素作為 pivot，那每次分區(qū)得到的兩個(gè)區(qū)間都是不均等的。我們需要進(jìn)行大約 n 次分區(qū)操作，才能完成快排的整個(gè)過(guò)程。每次分區(qū)我們平均要掃描大約 n / 2 個(gè)元素，這種情況下，快排的時(shí)間復(fù)雜度就從 O(nlogn) 退化成了 O(n²)。
最佳情況：T(n) = O(n log n)。
最差情況：T(n) = O(n²)。
平均情況：T(n) = O(n log n)。

動(dòng)畫(huà)

解答開(kāi)篇問(wèn)題

快排和歸并用的都是分治思想，遞推公式和遞歸代碼也非常相似，那它們的區(qū)別在哪里呢 ？

可以發(fā)現(xiàn)：

歸并排序的處理過(guò)程是由下而上的，先處理子問(wèn)題，然后再合并。

而快排正好相反，它的處理過(guò)程是由上而下的，先分區(qū)，然后再處理子問(wèn)題。

歸并排序雖然是穩(wěn)定的、時(shí)間復(fù)雜度為 O(nlogn) 的排序算法，但是它是非原地排序算法。

歸并之所以是非原地排序算法，主要原因是合并函數(shù)無(wú)法在原地執(zhí)行。

快速排序通過(guò)設(shè)計(jì)巧妙的原地分區(qū)函數(shù)，可以實(shí)現(xiàn)原地排序，解決了歸并排序占用太多內(nèi)存的問(wèn)題。

思想

先將整個(gè)待排序的記錄序列分割成為若干子序列。

分別進(jìn)行直接插入排序。

待整個(gè)序列中的記錄基本有序時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

過(guò)程

1.舉個(gè)易于理解的例子：[35, 33, 42, 10, 14, 19, 27, 44]，我們采取間隔 4。創(chuàng)建一個(gè)位于 4 個(gè)位置間隔的所有值的虛擬子列表。下面這些值是 { 35, 14 }，{ 33, 19 }，{ 42, 27 } 和 { 10, 44 }。

2.我們比較每個(gè)子列表中的值，并在原始數(shù)組中交換它們（如果需要）。完成此步驟后，新數(shù)組應(yīng)如下所示。

3.然后，我們采用 2 的間隔，這個(gè)間隙產(chǎn)生兩個(gè)子列表：{ 14, 27, 35, 42 }， { 19, 10, 33, 44 }。

4.我們比較并交換原始數(shù)組中的值（如果需要）。完成此步驟后，數(shù)組變成：[14, 10, 27, 19, 35, 33, 42, 44]，圖如下所示，10 與 19 的位置互換一下。

5.最后，我們使用值間隔 1 對(duì)數(shù)組的其余部分進(jìn)行排序，Shell sort 使用插入排序?qū)?shù)組進(jìn)行排序。

實(shí)現(xiàn)

const shellSort = arr => {
    let len = arr.length,
        temp,
        gap = 1;
    console.time("希爾排序耗時(shí)");
    while (gap < len / 3) {
        //動(dòng)態(tài)定義間隔序列
        gap = gap * 3 + 1;
    }
    for (gap; gap > 0; gap = Math.floor(gap / 3)) {
        for (let i = gap; i < len; i++) {
            temp = arr[i];
            let j = i - gap;
            for (; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
            console.log("arr  :", arr);
        }
    }
    console.timeEnd("希爾排序耗時(shí)");
    return arr;
};

測(cè)試

// 測(cè)試
const array = [35, 33, 42, 10, 14, 19, 27, 44];
console.log("原始array:", array);
const newArr = shellSort(array);
console.log("newArr:", newArr);
// 原始 array: ??[35, 33, 42, 10, 14, 19, 27, 44]
// arr      : ??[14, 33, 42, 10, 35, 19, 27, 44]
// arr      : ??[14, 19, 42, 10, 35, 33, 27, 44]
// arr      : ??[14, 19, 27, 10, 35, 33, 42, 44]
// arr      : ??[14, 19, 27, 10, 35, 33, 42, 44]
// arr      : ??[14, 19, 27, 10, 35, 33, 42, 44]
// arr      : ??[14, 19, 27, 10, 35, 33, 42, 44]
// arr      : ??[10, 14, 19, 27, 35, 33, 42, 44]
// arr      : ??[10, 14, 19, 27, 35, 33, 42, 44]
// arr      : ??[10, 14, 19, 27, 33, 35, 42, 44]
// arr      : ??[10, 14, 19, 27, 33, 35, 42, 44]
// arr      : ??[10, 14, 19, 27, 33, 35, 42, 44]
// 希爾排序耗時(shí): 3.592041015625ms
// newArr: ?   [10, 14, 19, 27, 33, 35, 42, 44]

分析

第一，希爾排序是原地排序算法嗎 ？

希爾排序過(guò)程中，只涉及相鄰數(shù)據(jù)的交換操作，只需要常量級(jí)的臨時(shí)空間，空間復(fù)雜度為 O(1) 。所以，希爾排序是原地排序算法。

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

我們知道，單次直接插入排序是穩(wěn)定的，它不會(huì)改變相同元素之間的相對(duì)順序，但在多次不同的插入排序過(guò)程中，相同的元素可能在各自的插入排序中移動(dòng)，可能導(dǎo)致相同元素相對(duì)順序發(fā)生變化。
因此，希爾排序不穩(wěn)定。

第三，希爾排序的時(shí)間復(fù)雜度是多少 ？

最佳情況：T(n) = O(n log n)。
最差情況：T(n) = O(n log² n)。
平均情況：T(n) = O(n log² n)。

動(dòng)畫(huà)

堆的定義

堆其實(shí)是一種特殊的樹(shù)。只要滿足這兩點(diǎn)，它就是一個(gè)堆。

堆是一個(gè)完全二叉樹(shù)。

完全二叉樹(shù)：除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿的，最后一層的節(jié)點(diǎn)都靠左排列。

堆中每一個(gè)節(jié)點(diǎn)的值都必須大于等于（或小于等于）其子樹(shù)中每個(gè)節(jié)點(diǎn)的值。

也可以說(shuō)：堆中每個(gè)節(jié)點(diǎn)的值都大于等于（或者小于等于）其左右子節(jié)點(diǎn)的值。這兩種表述是等價(jià)的。

對(duì)于每個(gè)節(jié)點(diǎn)的值都大于等于子樹(shù)中每個(gè)節(jié)點(diǎn)值的堆，我們叫作大頂堆。
對(duì)于每個(gè)節(jié)點(diǎn)的值都小于等于子樹(shù)中每個(gè)節(jié)點(diǎn)值的堆，我們叫作小頂堆。

其中圖 1 和 圖 2 是大頂堆，圖 3 是小頂堆，圖 4 不是堆。除此之外，從圖中還可以看出來(lái)，對(duì)于同一組數(shù)據(jù)，我們可以構(gòu)建多種不同形態(tài)的堆。

思想

將初始待排序關(guān)鍵字序列 (R1, R2 .... Rn) 構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū)；

將堆頂元素 R[1] 與最后一個(gè)元素 R[n] 交換，此時(shí)得到新的無(wú)序區(qū) (R1, R2, ..... Rn-1) 和新的有序區(qū) (Rn) ，且滿足 R[1, 2 ... n-1] <= R[n]。

由于交換后新的堆頂 R[1] 可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū) (R1, R2 ...... Rn-1) 調(diào)整為新堆，然后再次將 R[1] 與無(wú)序區(qū)最后一個(gè)元素交換，得到新的無(wú)序區(qū) (R1, R2 .... Rn-2) 和新的有序區(qū) (Rn-1, Rn)。不斷重復(fù)此過(guò)程，直到有序區(qū)的元素個(gè)數(shù)為 n - 1，則整個(gè)排序過(guò)程完成。

實(shí)現(xiàn)

// 堆排序
const heapSort = array => {
    console.time("堆排序耗時(shí)");
    // 初始化大頂堆，從第一個(gè)非葉子結(jié)點(diǎn)開(kāi)始
    for (let i = Math.floor(array.length / 2 - 1); i >= 0; i--) {
        heapify(array, i, array.length);
    }
    // 排序，每一次 for 循環(huán)找出一個(gè)當(dāng)前最大值，數(shù)組長(zhǎng)度減一
    for (let i = Math.floor(array.length - 1); i > 0; i--) {
        // 根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)交換
        swap(array, 0, i);
        // 從根節(jié)點(diǎn)開(kāi)始調(diào)整，并且最后一個(gè)結(jié)點(diǎn)已經(jīng)為當(dāng)前最大值，不需要再參與比較，所以第三個(gè)參數(shù)為 i，即比較到最后一個(gè)結(jié)點(diǎn)前一個(gè)即可
        heapify(array, 0, i);
    }
    console.timeEnd("堆排序耗時(shí)");
    return array;
};

// 交換兩個(gè)節(jié)點(diǎn)
const swap = (array, i, j) => {
    let temp = array[i];
    array[i] = array[j];
    array[j] = temp;
};

// 將 i 結(jié)點(diǎn)以下的堆整理為大頂堆，注意這一步實(shí)現(xiàn)的基礎(chǔ)實(shí)際上是：
// 假設(shè)結(jié)點(diǎn) i 以下的子堆已經(jīng)是一個(gè)大頂堆，heapify 函數(shù)實(shí)現(xiàn)的
// 功能是實(shí)際上是：找到 結(jié)點(diǎn) i 在包括結(jié)點(diǎn) i 的堆中的正確位置。
// 后面將寫(xiě)一個(gè) for 循環(huán)，從第一個(gè)非葉子結(jié)點(diǎn)開(kāi)始，對(duì)每一個(gè)非葉子結(jié)點(diǎn)
// 都執(zhí)行 heapify 操作，所以就滿足了結(jié)點(diǎn) i 以下的子堆已經(jīng)是一大頂堆
const heapify = (array, i, length) => {
    let temp = array[i]; // 當(dāng)前父節(jié)點(diǎn)
    // j < length 的目的是對(duì)結(jié)點(diǎn) i 以下的結(jié)點(diǎn)全部做順序調(diào)整
    for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
        temp = array[i]; // 將 array[i] 取出，整個(gè)過(guò)程相當(dāng)于找到 array[i] 應(yīng)處于的位置
        if (j + 1 < length && array[j] < array[j + 1]) {
            j++; // 找到兩個(gè)孩子中較大的一個(gè)，再與父節(jié)點(diǎn)比較
        }
        if (temp < array[j]) {
            swap(array, i, j); // 如果父節(jié)點(diǎn)小于子節(jié)點(diǎn):交換；否則跳出
            i = j; // 交換后，temp 的下標(biāo)變?yōu)?j
        } else {
            break;
        }
    }
};

測(cè)試

const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
console.log("原始array:", array);
const newArr = heapSort(array);
console.log("newArr:", newArr);
// 原始 array: ?[4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
// 堆排序耗時(shí): 0.15087890625ms
// newArr: ?   [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]

分析

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

整個(gè)堆排序的過(guò)程，都只需要極個(gè)別臨時(shí)存儲(chǔ)空間，所以堆排序是原地排序算法。

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

因?yàn)樵谂判虻倪^(guò)程，存在將堆的最后一個(gè)節(jié)點(diǎn)跟堆頂節(jié)點(diǎn)互換的操作，所以就有可能改變值相同數(shù)據(jù)的原始相對(duì)順序。
所以，堆排序是不穩(wěn)定的排序算法。

第三，堆排序的時(shí)間復(fù)雜度是多少 ？

堆排序包括建堆和排序兩個(gè)操作，建堆過(guò)程的時(shí)間復(fù)雜度是 O(n)，排序過(guò)程的時(shí)間復(fù)雜度是 O(nlogn)，所以，堆排序整體的時(shí)間復(fù)雜度是 O(nlogn)。
最佳情況：T(n) = O(n log n)。
最差情況：T(n) = O(n log n)。
平均情況：T(n) = O(n log n)。

動(dòng)畫(huà)

桶排序是計(jì)數(shù)排序的升級(jí)版，也采用了分治思想。

思想

將要排序的數(shù)據(jù)分到有限數(shù)量的幾個(gè)有序的桶里。

每個(gè)桶里的數(shù)據(jù)再多帶帶進(jìn)行排序（一般用插入排序或者快速排序）。

桶內(nèi)排完序之后，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出，組成的序列就是有序的了。

比如：

桶排序利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。

為了使桶排序更加高效，我們需要做到這兩點(diǎn)：

在額外空間充足的情況下，盡量增大桶的數(shù)量。

使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)均勻的分配到 K 個(gè)桶中。

桶排序的核心：就在于怎么把元素平均分配到每個(gè)桶里，合理的分配將大大提高排序的效率。

實(shí)現(xiàn)

// 桶排序
const bucketSort = (array, bucketSize) => {
  if (array.length === 0) {
    return array;
  }

  console.time("桶排序耗時(shí)");
  let i = 0;
  let minValue = array[0];
  let maxValue = array[0];
  for (i = 1; i < array.length; i++) {
    if (array[i] < minValue) {
      minValue = array[i]; //輸入數(shù)據(jù)的最小值
    } else if (array[i] > maxValue) {
      maxValue = array[i]; //輸入數(shù)據(jù)的最大值
    }
  }

  //桶的初始化
  const DEFAULT_BUCKET_SIZE = 5; //設(shè)置桶的默認(rèn)數(shù)量為 5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }

  //利用映射函數(shù)將數(shù)據(jù)分配到各個(gè)桶中
  for (i = 0; i < array.length; i++) {
    buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]);
  }

  array.length = 0;
  for (i = 0; i < buckets.length; i++) {
    quickSort(buckets[i]); //對(duì)每個(gè)桶進(jìn)行排序，這里使用了快速排序
    for (var j = 0; j < buckets[i].length; j++) {
      array.push(buckets[i][j]);
    }
  }
  console.timeEnd("桶排序耗時(shí)");

  return array;
};

// 快速排序
const quickSort = (arr, left, right) => {
    let len = arr.length,
        partitionIndex;
    left = typeof left != "number" ? 0 : left;
    right = typeof right != "number" ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
};

const partition = (arr, left, right) => {
    //分區(qū)操作
    let pivot = left, //設(shè)定基準(zhǔn)值（pivot）
        index = pivot + 1;
    for (let i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
};

const swap = (arr, i, j) => {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

測(cè)試

const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
console.log("原始array:", array);
const newArr = bucketSort(array);
console.log("newArr:", newArr);
// 原始 array: ?[4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
// 堆排序耗時(shí):   0.133056640625ms
// newArr: ?     [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]

分析

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

因?yàn)橥芭判虻目臻g復(fù)雜度，也即內(nèi)存消耗為 O(n)，所以不是原地排序算法。

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

取決于每個(gè)桶的排序方式，比如：快排就不穩(wěn)定，歸并就穩(wěn)定。

第三，桶排序的時(shí)間復(fù)雜度是多少 ？

因?yàn)橥皟?nèi)部的排序可以有多種方法，是會(huì)對(duì)桶排序的時(shí)間復(fù)雜度產(chǎn)生很重大的影響。所以，桶排序的時(shí)間復(fù)雜度可以是多種情況的。
總的來(lái)說(shuō)
最佳情況：當(dāng)輸入的數(shù)據(jù)可以均勻的分配到每一個(gè)桶中。
最差情況：當(dāng)輸入的數(shù)據(jù)被分配到了同一個(gè)桶中。
以下是桶的內(nèi)部排序為快速排序的情況：
如果要排序的數(shù)據(jù)有 n 個(gè)，我們把它們均勻地劃分到 m 個(gè)桶內(nèi)，每個(gè)桶里就有 k =n / m 個(gè)元素。每個(gè)桶內(nèi)部使用快速排序，時(shí)間復(fù)雜度為 O(k * logk)。
m 個(gè)桶排序的時(shí)間復(fù)雜度就是 O(m k logk)，因?yàn)?k = n / m，所以整個(gè)桶排序的時(shí)間復(fù)雜度就是 O(n*log(n/m))。
當(dāng)桶的個(gè)數(shù) m 接近數(shù)據(jù)個(gè)數(shù) n 時(shí)，log(n/m) 就是一個(gè)非常小的常量，這個(gè)時(shí)候桶排序的時(shí)間復(fù)雜度接近 O(n)。
最佳情況：T(n) = O(n)。當(dāng)輸入的數(shù)據(jù)可以均勻的分配到每一個(gè)桶中。
最差情況：T(n) = O(nlogn)。當(dāng)輸入的數(shù)據(jù)被分配到了同一個(gè)桶中。
平均情況：T(n) = O(n)。

桶排序最好情況下使用線性時(shí)間 O(n)，桶排序的時(shí)間復(fù)雜度，取決與對(duì)各個(gè)桶之間數(shù)據(jù)進(jìn)行排序的時(shí)間復(fù)雜度，因?yàn)槠渌糠值臅r(shí)間復(fù)雜度都為 O(n)。
很顯然，桶劃分的越小，各個(gè)桶之間的數(shù)據(jù)越少，排序所用的時(shí)間也會(huì)越少。但相應(yīng)的空間消耗就會(huì)增大。

適用場(chǎng)景

桶排序比較適合用在外部排序中。

外部排序就是數(shù)據(jù)存儲(chǔ)在外部磁盤(pán)且數(shù)據(jù)量大，但內(nèi)存有限，無(wú)法將整個(gè)數(shù)據(jù)全部加載到內(nèi)存中。

動(dòng)畫(huà)

思想

找出待排序的數(shù)組中最大和最小的元素。

統(tǒng)計(jì)數(shù)組中每個(gè)值為 i 的元素出現(xiàn)的次數(shù)，存入新數(shù)組 countArr 的第 i 項(xiàng)。

對(duì)所有的計(jì)數(shù)累加（從 countArr 中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）。

反向填充目標(biāo)數(shù)組：將每個(gè)元素 i 放在新數(shù)組的第 countArr[i] 項(xiàng)，每放一個(gè)元素就將 countArr[i] 減去 1 。

關(guān)鍵在于理解最后反向填充時(shí)的操作。

使用條件

只能用在數(shù)據(jù)范圍不大的場(chǎng)景中，若數(shù)據(jù)范圍 k 比要排序的數(shù)據(jù) n 大很多，就不適合用計(jì)數(shù)排序。

計(jì)數(shù)排序只能給非負(fù)整數(shù)排序，其他類(lèi)型需要在不改變相對(duì)大小情況下，轉(zhuǎn)換為非負(fù)整數(shù)。

比如如果考試成績(jī)精確到小數(shù)后一位，就需要將所有分?jǐn)?shù)乘以 10，轉(zhuǎn)換為整數(shù)。

實(shí)現(xiàn)

方法一：

const countingSort = array => {
    let len = array.length,
        result = [],
        countArr = [],
        min = (max = array[0]);
    console.time("計(jì)數(shù)排序耗時(shí)");
    for (let i = 0; i < len; i++) {
        // 獲取最小，最大 值
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
        countArr[array[i]] = countArr[array[i]] ? countArr[array[i]] + 1 : 1;
    }
    console.log("countArr :", countArr);
    // 從最小值 -> 最大值,將計(jì)數(shù)逐項(xiàng)相加
    for (let j = min; j < max; j++) {
        countArr[j + 1] = (countArr[j + 1] || 0) + (countArr[j] || 0);
    }
    console.log("countArr 2:", countArr);
    // countArr 中,下標(biāo)為 array 數(shù)值，數(shù)據(jù)為 array 數(shù)值出現(xiàn)次數(shù)；反向填充數(shù)據(jù)進(jìn)入 result 數(shù)據(jù)
    for (let k = len - 1; k >= 0; k--) {
        // result[位置] = array 數(shù)據(jù)
        result[countArr[array[k]] - 1] = array[k];
        // 減少 countArr 數(shù)組中保存的計(jì)數(shù)
        countArr[array[k]]--;
        // console.log("array[k]:", array[k], "countArr[array[k]] :", countArr[array[k]],)
        console.log("result:", result);
    }
    console.timeEnd("計(jì)數(shù)排序耗時(shí)");
    return result;
};

測(cè)試

const array = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log("原始 array: ", array);
const newArr = countingSort(array);
console.log("newArr: ", newArr);
// 原始 array: ?[2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]
// 計(jì)數(shù)排序耗時(shí):   5.6708984375ms
// newArr: ?     [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]

方法二：

const countingSort2 = (arr, maxValue) => {
    console.time("計(jì)數(shù)排序耗時(shí)");
    maxValue = maxValue || arr.length;
    let bucket = new Array(maxValue + 1),
        sortedIndex = 0;
    (arrLen = arr.length), (bucketLen = maxValue + 1);

    for (let i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (let j = 0; j < bucketLen; j++) {
        while (bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }
    console.timeEnd("計(jì)數(shù)排序耗時(shí)");
    return arr;
};

測(cè)試

const array2 = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log("原始 array2: ", array2);
const newArr2 = countingSort2(array2, 21);
console.log("newArr2: ", newArr2);
// 原始 array: ?[2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]
// 計(jì)數(shù)排序耗時(shí):   0.043212890625ms
// newArr: ?     [1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]

例子

可以認(rèn)為，計(jì)數(shù)排序其實(shí)是桶排序的一種特殊情況。

當(dāng)要排序的 n 個(gè)數(shù)據(jù)，所處的范圍并不大的時(shí)候，比如最大值是 k，我們就可以把數(shù)據(jù)劃分成 k 個(gè)桶。每個(gè)桶內(nèi)的數(shù)據(jù)值都是相同的，省掉了桶內(nèi)排序的時(shí)間。

我們都經(jīng)歷過(guò)高考，高考查分?jǐn)?shù)系統(tǒng)你還記得嗎？我們查分?jǐn)?shù)的時(shí)候，系統(tǒng)會(huì)顯示我們的成績(jī)以及所在省的排名。如果你所在的省有 50 萬(wàn)考生，如何通過(guò)成績(jī)快速排序得出名次呢？

考生的滿分是 900 分，最小是 0 分，這個(gè)數(shù)據(jù)的范圍很小，所以我們可以分成 901 個(gè)桶，對(duì)應(yīng)分?jǐn)?shù)從 0 分到 900 分。

根據(jù)考生的成績(jī)，我們將這 50 萬(wàn)考生劃分到這 901 個(gè)桶里。桶內(nèi)的數(shù)據(jù)都是分?jǐn)?shù)相同的考生，所以并不需要再進(jìn)行排序。

我們只需要依次掃描每個(gè)桶，將桶內(nèi)的考生依次輸出到一個(gè)數(shù)組中，就實(shí)現(xiàn)了 50 萬(wàn)考生的排序。

因?yàn)橹簧婕皰呙璞闅v操作，所以時(shí)間復(fù)雜度是 O(n)。

分析

第一，計(jì)數(shù)排序是原地排序算法嗎 ？

因?yàn)橛?jì)數(shù)排序的空間復(fù)雜度為 O(k)，k 桶的個(gè)數(shù)，所以不是原地排序算法。

第二，計(jì)數(shù)排序是穩(wěn)定的排序算法嗎 ？

計(jì)數(shù)排序不改變相同元素之間原本相對(duì)的順序，因此它是穩(wěn)定的排序算法。

第三，計(jì)數(shù)排序的時(shí)間復(fù)雜度是多少 ？

最佳情況：T(n) = O(n + k)
最差情況：T(n) = O(n + k)
平均情況：T(n) = O(n + k)
k 是待排序列最大值。

動(dòng)畫(huà)

思想

基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。

例子

假設(shè)我們有 10 萬(wàn)個(gè)手機(jī)號(hào)碼，希望將這 10 萬(wàn)個(gè)手機(jī)號(hào)碼從小到大排序，你有什么比較快速的排序方法呢 ？

這個(gè)問(wèn)題里有這樣的規(guī)律：假設(shè)要比較兩個(gè)手機(jī)號(hào)碼 a，b 的大小，如果在前面幾位中，a 手機(jī)號(hào)碼已經(jīng)比 b 手機(jī)號(hào)碼大了，那后面的幾位就不用看了。所以是基于位來(lái)比較的。

桶排序、計(jì)數(shù)排序能派上用場(chǎng)嗎 ？手機(jī)號(hào)碼有 11 位，范圍太大，顯然不適合用這兩種排序算法。針對(duì)這個(gè)排序問(wèn)題，有沒(méi)有時(shí)間復(fù)雜度是 O(n) 的算法呢 ？ 有，就是基數(shù)排序。

使用條件

要求數(shù)據(jù)可以分割獨(dú)立的位來(lái)比較；

位之間由遞進(jìn)關(guān)系，如果 a 數(shù)據(jù)的高位比 b 數(shù)據(jù)大，那么剩下的地位就不用比較了；

每一位的數(shù)據(jù)范圍不能太大，要可以用線性排序，否則基數(shù)排序的時(shí)間復(fù)雜度無(wú)法做到 O(n)。

方案

按照優(yōu)先從高位或低位來(lái)排序有兩種實(shí)現(xiàn)方案:

MSD：由高位為基底，先按 k1 排序分組，同一組中記錄, 關(guān)鍵碼 k1 相等，再對(duì)各組按 k2 排序分成子組, 之后，對(duì)后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼 kd 對(duì)各子組排序后，再將各組連接起來(lái)，便得到一個(gè)有序序列。MSD 方式適用于位數(shù)多的序列。

LSD：由低位為基底，先從 kd 開(kāi)始排序，再對(duì) kd - 1 進(jìn)行排序，依次重復(fù)，直到對(duì) k1 排序后便得到一個(gè)有序序列。LSD 方式適用于位數(shù)少的序列。

實(shí)現(xiàn)

/**
    * name: 基數(shù)排序
    * @param  array 待排序數(shù)組
    * @param  max 最大位數(shù)
    */
const radixSort = (array, max) => {
    console.time("計(jì)數(shù)排序耗時(shí)");
    const buckets = [];
    let unit = 10,
        base = 1;
    for (let i = 0; i < max; i++, base *= 10, unit *= 10) {
        for (let j = 0; j < array.length; j++) {
            let index = ~~((array[j] % unit) / base); //依次過(guò)濾出個(gè)位，十位等等數(shù)字
            if (buckets[index] == null) {
                buckets[index] = []; //初始化桶
            }
            buckets[index].push(array[j]); //往不同桶里添加數(shù)據(jù)
        }
        let pos = 0,
            value;
        for (let j = 0, length = buckets.length; j < length; j++) {
            if (buckets[j] != null) {
                while ((value = buckets[j].shift()) != null) {
                    array[pos++] = value; //將不同桶里數(shù)據(jù)挨個(gè)撈出來(lái)，為下一輪高位排序做準(zhǔn)備，由于靠近桶底的元素排名靠前，因此從桶底先撈
                }
            }
        }
    }
    console.timeEnd("計(jì)數(shù)排序耗時(shí)");
    return array;
};

測(cè)試

const array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log("原始array:", array);
const newArr = radixSort(array, 2);
console.log("newArr:", newArr);
// 原始 array: ?[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
// 堆排序耗時(shí):   0.064208984375ms
// newArr: ?     [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

分析

第一，基數(shù)排序是原地排序算法嗎 ？

因?yàn)橛?jì)數(shù)排序的空間復(fù)雜度為 O(n + k)，所以不是原地排序算法。

第二，基數(shù)排序是穩(wěn)定的排序算法嗎 ？

基數(shù)排序不改變相同元素之間的相對(duì)順序，因此它是穩(wěn)定的排序算法。

第三，基數(shù)排序的時(shí)間復(fù)雜度是多少 ？

最佳情況：T(n) = O(n * k)
最差情況：T(n) = O(n * k)
平均情況：T(n) = O(n * k)
其中，k 是待排序列最大值。

動(dòng)畫(huà)

LSD 基數(shù)排序動(dòng)圖演示：

十大經(jīng)典排序算法的 時(shí)間復(fù)雜度與空間復(fù)雜度 比較。

名詞解釋?zhuān)?/p>

n：數(shù)據(jù)規(guī)模；

k：桶的個(gè)數(shù)；

In-place: 占用常數(shù)內(nèi)存，不占用額外內(nèi)存；

Out-place: 占用額外內(nèi)存。

算法可視化工具 algorithm-visualizer
算法可視化工具 algorithm-visualizer 是一個(gè)交互式的在線平臺(tái)，可以從代碼中可視化算法，還可以看到代碼執(zhí)行的過(guò)程。旨在通過(guò)交互式可視化的執(zhí)行來(lái)揭示算法背后的機(jī)制。

效果如下圖：

算法可視化動(dòng)畫(huà)網(wǎng)站 https://visualgo.net/en

效果如下圖：

算法可視化動(dòng)畫(huà)網(wǎng)站 www.ee.ryerson.ca

效果如下圖：

illustrated-algorithms

變量和操作的可視化表示增強(qiáng)了控制流和實(shí)際源代碼。您可以快速前進(jìn)和后退執(zhí)行，以密切觀察算法的工作方式。
效果如下圖：

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 系列文章，暫時(shí)寫(xiě)了如下的 11 篇文章，后續(xù)還有想寫(xiě)的內(nèi)容，再補(bǔ)充。

所寫(xiě)的內(nèi)容只是數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)容的冰山一角，如果你還想學(xué)更多的內(nèi)容，推薦學(xué)習(xí)王爭(zhēng)老師的 數(shù)據(jù)結(jié)構(gòu)與算法之美。

從時(shí)間和空間復(fù)雜度、基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)到排序算法，文章的內(nèi)容有一定的關(guān)聯(lián)性，所以閱讀時(shí)推薦按順序來(lái)閱讀，效果更佳。

1. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 時(shí)間和空間復(fù)雜度

2. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 線性表（數(shù)組、隊(duì)列、棧、鏈表）

3. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 實(shí)現(xiàn)一個(gè)前端路由，如何實(shí)現(xiàn)瀏覽器的前進(jìn)與后退 ？

4. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 棧內(nèi)存與堆內(nèi)存 、淺拷貝與深拷貝

5. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 遞歸

6. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 非線性表（樹(shù)、堆）

7. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 冒泡排序、選擇排序、插入排序

8. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

9. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 計(jì)數(shù)排序、桶排序、基數(shù)排序

10. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 十大經(jīng)典排序算法匯總

11. JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 強(qiáng)烈推薦 GitHub 上值得前端學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)與算法項(xiàng)目

如果有錯(cuò)誤或者不嚴(yán)謹(jǐn)?shù)牡胤剑?qǐng)務(wù)必給予指正，以免誤人子弟，十分感謝。

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

筆者為了寫(xiě)好這系列的文章，花費(fèi)了大量的業(yè)余時(shí)間，邊學(xué)邊寫(xiě)，邊寫(xiě)邊修改，前后歷時(shí)差不多 2 個(gè)月，入門(mén)級(jí)的文章總算是寫(xiě)完了。

如果你覺(jué)得有用或者喜歡，就點(diǎn)收藏，順便點(diǎn)個(gè)贊吧，你的支持是我最大的鼓勵(lì) ！