桶排序、計(jì)數(shù)排序、基數(shù)排序。因?yàn)檫@些排序算法的時(shí)間復(fù)雜度是線性的，所以我們把這類排序算法叫作線性排序（Linear sort）。之所以能做到線性的時(shí)間復(fù)雜度，主要原因是，這三個(gè)算法是非基于比較的排序算法，都不涉及元素之間的比較操作。
這幾種排序算法理解起來都不難，時(shí)間、空間復(fù)雜度分析起來也很簡(jiǎn)單，但是對(duì)要排序的數(shù)據(jù)要求很苛刻，所以我們今天學(xué)習(xí)重點(diǎn)的是掌握這些排序算法的適用場(chǎng)景。
桶排序（Bucket sort）
首先，我們來看桶排序。桶排序，顧名思義，會(huì)用到“桶”，核心思想是將要排序的數(shù)據(jù)分到幾個(gè)有序的桶里，每個(gè)桶里的數(shù)據(jù)再單獨(dú)進(jìn)行排序，桶內(nèi)排完序之后，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出，組成的序列就是有序的了。
桶排序的時(shí)間復(fù)雜度為什么是 O(n) 呢？我們一塊兒來分析一下。
如果要排序的數(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)。
桶排序比較適合用在外部排序中。所謂的外部排序就是數(shù)據(jù)存儲(chǔ)在外部磁盤中，數(shù)據(jù)量比較大，內(nèi)存有限，無法將數(shù)據(jù)全部加載到內(nèi)存中。
比如說我們有 10GB 的訂單數(shù)據(jù)，我們希望按訂單金額（假設(shè)金額都是正整數(shù)）進(jìn)行排序，但是我們的內(nèi)存有限，只有幾百 MB，沒辦法一次性把 10GB 的數(shù)據(jù)都加載到內(nèi)存中。這個(gè)時(shí)候該怎么辦呢？
現(xiàn)在我來講一下，如何借助桶排序的處理思想來解決這個(gè)問題。
我們可以先掃描一遍文件，看訂單金額所處的數(shù)據(jù)范圍。假設(shè)經(jīng)過掃描之后我們得到，訂單金額最小是 1 元，最大是 10 萬元。我們將所有訂單根據(jù)金額劃分到 100 個(gè)桶里，第一個(gè)桶我們存儲(chǔ)金額在 1 元到 1000 元之內(nèi)的訂單，第二桶存儲(chǔ)金額在 1001 元到 2000 元之內(nèi)的訂單，以此類推。每一個(gè)桶對(duì)應(yīng)一個(gè)文件，并且按照金額范圍的大小順序編號(hào)命名（00，01，02…99）。
理想的情況下，如果訂單金額在 1 到 10 萬之間均勻分布，那訂單會(huì)被均勻劃分到 100 個(gè)文件中，每個(gè)小文件中存儲(chǔ)大約 100MB 的訂單數(shù)據(jù)，我們就可以將這 100 個(gè)小文件依次放到內(nèi)存中，用快排來排序。等所有文件都排好序之后，我們只需要按照文件編號(hào)，從小到大依次讀取每個(gè)小文件中的訂單數(shù)據(jù)，并將其寫入到一個(gè)文件中，那這個(gè)文件中存儲(chǔ)的就是按照金額從小到大排序的訂單數(shù)據(jù)了。
不過，你可能也發(fā)現(xiàn)了，訂單按照金額在 1 元到 10 萬元之間并不一定是均勻分布的 ，所以 10GB 訂單數(shù)據(jù)是無法均勻地被劃分到 100 個(gè)文件中的。有可能某個(gè)金額區(qū)間的數(shù)據(jù)特別多，劃分之后對(duì)應(yīng)的文件就會(huì)很大，沒法一次性讀入內(nèi)存。這又該怎么辦呢？
針對(duì)這些劃分之后還是比較大的文件，我們可以繼續(xù)劃分，比如，訂單金額在 1 元到 1000 元之間的比較多，我們就將這個(gè)區(qū)間繼續(xù)劃分為 10 個(gè)小區(qū)間，1 元到 100 元，101 元到 200 元，201 元到 300 元…901 元到 1000 元。如果劃分之后，101 元到 200 元之間的訂單還是太多，無法一次性讀入內(nèi)存，那就繼續(xù)再劃分，直到所有的文件都能讀入內(nèi)存為止。
計(jì)數(shù)排序（Counting sort）
計(jì)數(shù)排序其實(shí)是桶排序的一種特殊情況。當(dāng)要排序的 n 個(gè)數(shù)據(jù)，所處的范圍并不大的時(shí)候，比如最大值是 k，我們就可以把數(shù)據(jù)劃分成 k 個(gè)桶。每個(gè)桶內(nèi)的數(shù)據(jù)值都是相同的，省掉了桶內(nèi)排序的時(shí)間。
。如果你所在的省有 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ù)排序的算法思想就是這么簡(jiǎn)單，跟桶排序非常類似，只是桶的大小粒度不一樣。不過，為什么這個(gè)排序算法叫“計(jì)數(shù)”排序呢？“計(jì)數(shù)”的含義來自哪里呢？
考生的成績(jī)從 0 到 5 分，我們使用大小為 6 的數(shù)組 C[6] 表示桶，其中下標(biāo)對(duì)應(yīng)分?jǐn)?shù)。不過，C[6] 內(nèi)存儲(chǔ)的并不是考生，而是對(duì)應(yīng)的考生個(gè)數(shù)。像我剛剛舉的那個(gè)例子，我們只需要遍歷一遍考生分?jǐn)?shù)，就可以得到 C[6] 的值。
從圖中可以看出，分?jǐn)?shù)為 3 分的考生有 3 個(gè)，小于 3 分的考生有 4 個(gè)，所以，成績(jī)?yōu)?3 分的考生在排序之后的有序數(shù)組 R[8] 中，會(huì)保存下標(biāo) 4，5，6 的位置。
那我們?nèi)绾慰焖儆?jì)算出，每個(gè)分?jǐn)?shù)的考生在有序數(shù)組中對(duì)應(yīng)的存儲(chǔ)位置呢？這個(gè)處理方法非常巧妙，很不容易想到。
思路是這樣的：我們對(duì) C[6] 數(shù)組順序求和，C[6] 存儲(chǔ)的數(shù)據(jù)就變成了下面這樣子。C[k] 里存儲(chǔ)小于等于分?jǐn)?shù) k 的考生個(gè)數(shù)。
有了前面的數(shù)據(jù)準(zhǔn)備之后，現(xiàn)在我就要講計(jì)數(shù)排序中最復(fù)雜、最難理解的一部分了，請(qǐng)集中精力跟著我的思路！
我們從后到前依次掃描數(shù)組 A。比如，當(dāng)掃描到 3 時(shí)，我們可以從數(shù)組 C 中取出下標(biāo)為 3 的值 7，也就是說，到目前為止，包括自己在內(nèi)，分?jǐn)?shù)小于等于 3 的考生有 7 個(gè)，也就是說 3 是數(shù)組 R 中的第 7 個(gè)元素（也就是數(shù)組 R 中下標(biāo)為 6 的位置）。當(dāng) 3 放入到數(shù)組 R 中后，小于等于 3 的元素就只剩下了 6 個(gè)了，所以相應(yīng)的 C[3] 要減 1，變成 6。
以此類推，當(dāng)我們掃描到第 2 個(gè)分?jǐn)?shù)為 3 的考生的時(shí)候，就會(huì)把它放入數(shù)組 R 中的第 6 個(gè)元素的位置（也就是下標(biāo)為 5 的位置）。當(dāng)我們掃描完整個(gè)數(shù)組 A 后，數(shù)組 R 內(nèi)的數(shù)據(jù)就是按照分?jǐn)?shù)從小到大有序排列的了。
基數(shù)排序（Radix sort）
我來總結(jié)一下，基數(shù)排序?qū)σ判虻臄?shù)據(jù)是有要求的，需要可以分割出獨(dú)立的“位”來比較，而且位之間有遞進(jìn)的關(guān)系，如果 a 數(shù)據(jù)的高位比 b 數(shù)據(jù)大，那剩下的低位就不用比較了。除此之外，每一位的數(shù)據(jù)范圍不能太大，要可以用線性排序算法來排序，否則，基數(shù)排序的時(shí)間復(fù)雜度就無法做到 O(n) 了。
