三種時間復雜度是 O(n) 的排序算法：桶排序、計數排序、基數排序。因為這些排序算法的時間復雜度是線性的，所以我們把這類排序算法叫作線性排序（Linear sort）。之所以能做到線性的時間復雜度，主要原因是，這三個算法是非基于比較的排序算法，都不涉及元素之間的比較操作。這幾種排序算法的學習重點是掌握適用場景

桶排序（Bucket sort）

核心思想是將要排序的數據分到幾個有序的桶里，每個桶里的數據再單獨進行排序。桶內排完序之后，再把每個桶里的數據按照順序依次取出，組成的序列就是有序的了

如果要排序的數據有 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)。

桶排序對數據的要求

要排序的數據需要很容易就能劃分成 m 個桶，并且桶與桶之間有著天然的大小順序。這樣每個桶內的數據都排序完之后，桶與桶之間的數據不需要再進行排序

數據在各個桶之間的分布是比較均勻的。如果數據經過桶的劃分之后，有些桶里的數據非常多，有些非常少，很不平均，那桶內數據排序的時間復雜度就不是常量級了。在極端情況下，如果數據都被劃分到一個桶里，那就退化為 O(nlogn) 的排序算法了

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

舉例：10GB 訂單數據，按訂單金額（假設金額都是正整數）排序，內存有限只有幾百 MB，無法一次性把 10GB 的數據都加載到內存中。這個時候該怎么辦呢？

解決思路：

內存100M，因此需要需要的劃分的桶的個數=10G/100M=100個桶

掃描訂單金額的范圍假如是1-10萬，那么將10G訂單根據金額劃分到100個桶里，第一個桶范圍是1-1000，第二個桶范圍是1001-2000，以此類推；每個桶對應一個文件順序編號為00,01...99

如果訂單金額均勻分布，那么10G的數據會均勻的劃分到100個文件，每個小文件存儲大約100M的數據，然后依次對100個文件放到內存中進行快速排序；最后按照文件編號依次讀取每個小文件中的數據，并將其寫入到一個文件中就得到了從小到大訂單數據

如果訂單金額在1-10萬之間不是均勻分布，那么有的金額區間的數據特別多從而導致文件很大，無法一次性讀入內存，那么可以針對這些個文件再進行小區間劃分，直到劃分后所有的小文件可以一次性讀入內存(有點分治、遞歸的思想，將大問題不斷的分級為小問題，最后將小問題的解進行合并)。例如訂單金額在 1 元到 1000 元之間的比較多，我們就將這個區間繼續劃分為 10 個小區間....

計數排序（Counting sort）

計數排序其實是桶排序的一種特殊情況。當要排序的 n 個數據，所處的范圍并不大的時候，比如最大值是 k，我們就可以把數據劃分成 k 個桶。每個桶內的數據值都是相同的，省掉了桶內排序的時間。

問題場景：有 50 萬考生，如何通過成績快速排序得出名次呢？

考生的滿分是 900 分，最小是 0 分，這個數據的范圍很小，所以我們可以分成 901 個桶，對應分數從 0 分到 900 分。根據考生的成績，我們將這 50 萬考生劃分到這 901 個桶里。桶內的數據都是分數相同的考生，所以并不需要再進行排序。我們只需要依次掃描每個桶，將桶內的考生依次輸出到一個數組中，就實現了 50 萬考生的排序。因為只涉及掃描遍歷操作，所以時間復雜度是 O(n)。

計數排序的算法思想就是這么簡單，跟桶排序非常類似，只是桶的大小粒度不一樣。不過，為什么這個排序算法叫“計數”排序呢？“計數”的含義來自哪里呢？

假設只有 8 個考生，分數在 0 到 5 分之間。這 8 個考生的成績我們放在一個數組 A[8]中，它們分別是：2，5，3，0，2，3，0，3。考生的成績從 0 到 5 分，我們使用大小為 6 的數組 C[6]表示桶，其中下標對應分數。不過，C[6]內存儲的并不是考生，而是對應的考生個數。像我剛剛舉的那個例子，我們只需要遍歷一遍考生分數，就可以得到 C[6]的值.

分數為 3 分的考生有 3 個，小于 3 分的考生有 4 個，所以，成績為 3 分的考生在排序之后的有序數組 R[8]中，會保存下標 4，5，6 的位置。

如何快速計算出，每個分數的考生在有序數組中對應的存儲位置呢？這個處理方法非常巧妙：

對 C[6]數組順序求和，C[6]存儲的數據就變成了下面這樣子。C[k]里存儲小于等于分數 k 的考生個數。

有了前面的數據準備之后，就到計數排序中最復雜、最難理解的一部分了！從后往前掃描數組A

當掃描到 3 時，從數組 C 中取出下標為 3 的值 7，說明包括自己在內，分數小于等于 3 的考生有 7 個，也即?3 是數組 R 中的第 7 個元素（也就是數組 R 中下標為 6 的位置）。當 3 放入到數組 R 中后，小于等于 3 的元素就只剩下了 6 個了，所以相應的 C[3]要減 1，變成 6。

當我們掃描完整個數組 A 后，數組 R 內的數據就是按照分數從小到大有序排列的了。

// 計數排序，a是數組，n是數組大小。假設數組中存儲的都是非負整數。 public void countingSort(int[] a, int n) {if (n <= 1) return;// 查找數組中數據的范圍int max = a[0];for (int i = 1; i < n; ++i) {if (max < a[i]) {max = a[i];}}int[] c = new int[max + 1]; // 申請一個計數數組c，下標大小[0,max]for (int i = 0; i <= max; ++i) {c[i] = 0;}// 計算每個元素的個數，放入c中for (int i = 0; i < n; ++i) {c[a[i]]++;}// 依次累加for (int i = 1; i <= max; ++i) {c[i] = c[i-1] + c[i];}// 臨時數組r，存儲排序之后的結果int[] r = new int[n];// 計算排序的關鍵步驟，有點難理解for (int i = n - 1; i >= 0; --i) {int index = c[a[i]]-1;r[index] = a[i];c[a[i]]--;}// 將結果拷貝給a數組for (int i = 0; i < n; ++i) {a[i] = r[i];} }

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

拿考生這個例子。如果考生成績精確到小數后一位，我們就需要將所有的分數都先乘以 10，轉化成整數，然后再放到 9010 個桶內。再比如，如果要排序的數據中有負數，數據的范圍是[-1000, 1000]，那我們就需要先對每個數據都加 1000，轉化成非負整數。

基數排序（Radix sort）

問題場景：假設我們有 10 萬個手機號碼，希望將這 10 萬個手機號碼從小到大排序，你有什么比較快速的排序方法呢？手機號碼有 11 位，范圍太大，顯然不適合用這兩種排序算法。

問題里有這樣的規律：假設要比較兩個手機號碼 a，b 的大小，如果在前面幾位中，a 手機號碼已經比 b 手機號碼大了，那后面的幾位就不用看了。

實現思路：在闡述排序算法的穩定性的時候舉的訂單的例子嗎？我們這里也可以借助相同的處理思路，先按照最后一位來排序手機號碼，然后，再按照倒數第二位重新排序，以此類推，最后按照第一位重新排序。經過 11 次排序之后，手機號碼就都有序了。

以字符串排序為實例：

注意：這里按照每位來排序的排序算法要是穩定的，否則這個實現思路就是不正確的。如果是非穩定排序算法，那最后一次排序只會考慮最高位的大小順序，完全不管其他位的大小關系，那么低位的排序就完全沒有意義了

根據每一位來排序，我們可以用剛講過的桶排序或者計數排序，它們的時間復雜度可以做到 O(n)。如果要排序的數據有 k 位，那我們就需要 k 次桶排序或者計數排序，總的時間復雜度是 O(k*n)。當 k 不大的時候，比如手機號碼排序的例子，k 最大就是 11，所以基數排序的時間復雜度就近似于 O(n)。有時候排序數據并不都是等長的，比如排序牛津字典中的 20 萬個英文單詞，最短的只有 1 個字母，最長的有 45 個。不等長的數據實際上，可以把所有的單詞補齊到相同長度，位數不夠的可以在后面補“0”，因為根據ASCII 值，所有字母都大于“0”，所以補“0”不會影響到原有的大小順序。這樣就可以繼續用基數排序了。

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

解答標題

根據年齡給 100 萬用戶排序，就類似按照成績給 50 萬考生排序。我們假設年齡的范圍最小 1 歲，最大不超過 120 歲。我們可以遍歷這 100 萬用戶，根據年齡將其劃分到這 120 個桶里，然后依次順序遍歷這 120 個桶中的元素。這樣就得到了按照年齡排序的 100 萬用戶數據

?

?

總結

以上是生活随笔為你收集整理的13 | 线性排序：如何根据年龄给100万用户数据排序？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。