一看就懂的大數據排序算法：如何給100萬用戶數據排序？

@[toc]

之前寫過一篇八種排序算法的博客，不過都是基于小數據量進行的排序，沒有像這篇這樣做大數據排序。文末會放出鏈接。

桶排序（Bucket sort）

首先，我們來看桶排序。桶排序，顧名思義，會用到“桶”，核心思想是將要排序的數據分到幾個有序的桶里，每個桶里的數據再單獨進行排序。桶內排完序之后，再把每個桶里的數據按照順序依次取出，組成的序列就是有序的了。

看圖說話啊。

桶排序的時間復雜度，是O(n)，如果不出意外的話。

如果要排序的數據有 n 個，我們把它們均勻地劃分到 m 個桶內，每個桶里就有 k=n/m 個元素。每個桶內部使用快速排序，時間復雜度為 O(k * logk)。m 個桶排序的時間復雜度就是 O(m * k * logk)，因為 k=n/m，所以整個桶排序的時間復雜度就是 O(n*log(n/m))。當桶的個數 m 接近數據個數 n 時，log(n/m) 就是一個非常小的常量，這個時候桶排序的時間復雜度接近 O(n)。

那既然桶排序這么的優秀，為什么我們在平時的使用中卻偏向于其他的排序方法呢（大多數情況下偏向于時間復雜度為O(nlogn)的快排）？

桶排序的小缺點

桶排序對要排序數據的要求是非常苛刻的。

首先，要排序的數據需要很容易就能劃分成 m 個桶，并且，桶與桶之間有著天然的大小順序。

其次，數據在各個桶之間的分布是比較均勻的。如果數據經過桶的劃分之后，有些桶里的數據非常多，有些非常少，很不平均，那桶內數據排序的時間復雜度就不是常量級了。

桶排序比較適合用在外部排序中。所謂的外部排序就是數據存儲在外部磁盤中，數據量比較大，內存有限，無法將數據全部加載到內存中。

比如說我們有 10GB 的數據，我們希望對這波數據進行排序，但是我們的內存有限，只有1G，沒辦法一次性把 10GB 的數據都加載到內存中。這個時候該怎么辦呢？

我們可以先掃描一遍文件，看數據所處的數據范圍。假設經過掃描之后我們得到，數據最小為1，最大為1000。我們將所有數據劃分到 100 個桶里，第一個桶我們存儲在 1 元到 10 元之內的數據，第二桶存儲在 11 元到 20 元之內的數據，以此類推。每一個桶對應一個文件，并且按照數據范圍的大小順序編號命名（00，01，02…99）。

理想的情況下，如果數據均勻分布，那數據會被均勻劃分到 100 個文件中，每個小文件中存儲大約 100MB 的數據，我們就可以將這 100 個小文件依次放到內存中，用快排來排序。等所有文件都排好序之后，我們只需要按照文件編號，從小到大依次讀取每個小文件中的數據，并將其寫入到一個文件中。

不過呢，不均勻才是常態嘛，有可能某個區間的數據特別多，劃分之后對應的文件就會很大，沒法一次性讀入內存。這又該怎么辦呢？

針對這些劃分之后還是比較大的文件，我們可以繼續劃分。

如果劃分之后，數據還是太多，無法一次性讀入內存，那就繼續再劃分，直到所有的文件都能讀入內存為止。

計數排序（Counting sort）

計數排序其實是桶排序的一種特殊情況。

還是上面那個例子來說，區間跨度為1000，那就分它一千個桶，每一個數據位一個桶。

我們就當這波數據都是整數，所以并不需要再進行排序。我們只需要依次掃描每個桶，將桶內的數據依次輸出到一個文件中，就實現了 10G 數據的排序。因為只涉及掃描遍歷操作，所以時間復雜度是 O(n)。

計數排序的小缺點

那這不也很明顯嘛，我桶排序就開100個桶，運氣不好多開幾個，計數排序一上來就是1000個桶預訂了，其中會有多少浪費，多少空桶，誰知道呢？

計數排序只能用在數據范圍不大的場景中，如果數據范圍 k 比要排序的數據 n 大很多，就不適合用計數排序了。而且，計數排序比較適合給非負整數排序（不然剛剛為什么要假設），如果要排序的數據是其他類型的，要將其在不改變相對大小的情況下，轉化為非負整數。

基數排序（Radix sort）

我們再來看這樣一個排序問題。假設我們有 10 萬個手機號碼，希望將這 10 萬個手機號碼從小到大排序，你有什么比較快速的排序方法呢？

這十一位的數，桶一個我看看？

不好分桶吧，跨度太大了。

我們可以用這樣一種方法：

先用第一位來進行排序，然后第二位，第三位，··· ，第十一位。

根據每一位來排序，我們可以用剛講過的桶排序或者計數排序，它們的時間復雜度可以做到 O(n)。如果要排序的數據有 k 位，那我們就需要 k 次桶排序或者計數排序，總的時間復雜度是 O(k*n)。當 k 不大的時候，比如手機號碼排序的例子，k 最大就是 11，所以基數排序的時間復雜度就近似于 O(n)。

但是，耗桶。

實際上，有時候要排序的數據并不都是等長的

這時候怎么辦呢？自己想想嘛，什么都讓我說完了就沒意思了。

基數排序的“脾氣”

基數排序對要排序的數據是有要求的，需要可以分割出獨立的“位”來比較，而且位之間有遞進的關系，如果 a 數據的高位比 b 數據大，那剩下的低位就不用比較了。除此之外，每一位的數據范圍不能太大，要可以用線性排序算法來排序，否則，基數排序的時間復雜度就無法做到 O(n) 了。

大數據 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。