摘要：之所以把計(jì)數(shù)排序桶排序基數(shù)排序放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為。動(dòng)畫計(jì)數(shù)排序思想找出待排序的數(shù)組中最大和最小的元素。桶排序計(jì)數(shù)排序能派上用場(chǎng)嗎手機(jī)號(hào)碼有位，范圍太大，顯然不適合用這兩種排序算法。

算法為王。

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

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

之所以把 計(jì)數(shù)排序、桶排序、基數(shù)排序 放在一起比較，是因?yàn)樗鼈兊钠骄鶗r(shí)間復(fù)雜度都為 O(n)。

因?yàn)檫@三個(gè)排序算法的時(shí)間復(fù)雜度是線性的，所以我們把這類排序算法叫作 線性排序（Linear sort）。

之所以能做到線性的時(shí)間復(fù)雜度，主要原因是，這三個(gè)算法不是基于比較的排序算法，都不涉及元素之間的比較操作。

另外，請(qǐng)大家?guī)е鴨栴}來閱讀下文，問題：如何根據(jù)年齡給 100 萬用戶排序 ？

桶排序是計(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ù)雜度可以是多種情況的。

總的來說
最佳情況：當(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ǔ)在外部磁盤且數(shù)據(jù)量大，但內(nèi)存有限，無法將整個(gè)數(shù)據(jù)全部加載到內(nèi)存中。

動(dòng)畫

思想

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

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

對(duì)所有的計(jì)數(shù)累加（從 countArr 中的第一個(gè)元素開始，每一項(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ù)排序，其他類型需要在不改變相對(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)歷過高考，高考查分?jǐn)?shù)系統(tǒng)你還記得嗎？我們查分?jǐn)?shù)的時(shí)候，系統(tǒng)會(huì)顯示我們的成績(jī)以及所在省的排名。如果你所在的省有 50 萬考生，如何通過成績(jī)快速排序得出名次呢？

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

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

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

因?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(k)
k：桶的個(gè)數(shù)。

動(dòng)畫

思想

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

由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。

例子

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

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

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

使用條件

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

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

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

方案

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

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

LSD：由低位為基底，先從 kd 開始排序，再對(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); //依次過濾出個(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è)撈出來，為下一輪高位排序做準(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)畫

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

回過頭來看看開篇的思考題：如何根據(jù)年齡給 100 萬用戶排序 ？

你可能會(huì)說，我用上一節(jié)講的歸并、快排就可以搞定??！是的，它們也可以完成功能，但是時(shí)間復(fù)雜度最低也是 O(nlogn)。

有沒有更快的排序方法呢 ？以下是參考答案。

實(shí)際上，根據(jù)年齡給 100 萬用戶排序，就類似按照成績(jī)給 50 萬考生排序。

我們假設(shè)年齡的范圍最小 1 歲，最大不超過 120 歲。

我們可以遍歷這 100 萬用戶，根據(jù)年齡將其劃分到這 120 個(gè)桶里，然后依次順序遍歷這 120 個(gè)桶中的元素。

這樣就得到了按照年齡排序的 100 萬用戶數(shù)據(jù)。

基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序

基數(shù)排序有兩種方法：

MSD 從高位開始進(jìn)行排序

LSD 從低位開始進(jìn)行排序

這三種排序算法都利用了桶的概念，但對(duì)桶的使用方法上有明顯差異：

基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶；

計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值；

桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值；

復(fù)雜性對(duì)比

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

桶排序的時(shí)間復(fù)雜度可以是多種情況的，取決于桶內(nèi)的排序。

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

效果如下圖。

旨在通過交互式可視化的執(zhí)行來揭示算法背后的機(jī)制。

算法可視化來源 https://visualgo.net/en

效果如下圖。

https://www.ee.ryerson.ca

illustrated-algorithms

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

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 的系列文章。

時(shí)間和空間復(fù)雜度

線性表（數(shù)組、鏈表、棧、隊(duì)列）

實(shí)現(xiàn)一個(gè)前端路由，如何實(shí)現(xiàn)瀏覽器的前進(jìn)與后退 ？

棧內(nèi)存與堆內(nèi)存 、淺拷貝與深拷貝

遞歸

非線性表（樹、堆）

冒泡排序、選擇排序、插入排序

歸并排序、快速排序、希爾排序、堆排序

計(jì)數(shù)排序、桶排序、基數(shù)排序

十大經(jīng)典排序匯總

強(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 上了。

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

參考文章：

菜鳥教程 - 算法系列

線性排序：如何根據(jù)年齡給100萬用戶數(shù)據(jù)排序？

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

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