線性排序
一 桶排序
核心思想是將要排序的數(shù)據(jù)分到幾個有序的桶里脾歇，每個桶里的數(shù)據(jù)再單獨進行排序。桶內(nèi)排完序之后淘捡，再把每個桶里的數(shù)據(jù)按照順序依次取出藕各，組成的序列就是有序的了。
如果要排序的數(shù)據(jù)有 n 個焦除，我們把它們均勻地劃分到 m 個桶內(nèi)激况，每個桶里就有 k=n/m 個元素。每個桶內(nèi)部使用快速排序踢京，時間復雜度為 O(k * logk)誉碴。m 個桶排序的時間復雜度就是 O(m * k * logk)，因為 k=n/m瓣距，所以整個桶排序的時間復雜度就是 O(n*log(n/m))黔帕。當桶的個數(shù) m 接近數(shù)據(jù)個數(shù) n 時，log(n/m) 就是一個非常小的常量蹈丸，這個時候桶排序的時間復雜度接近 O(n)成黄。
在極端情況下，如果數(shù)據(jù)都被劃分到一個桶里逻杖，那就退化為 O(nlogn) 的排序算法奋岁。
桶排序比較適合用在外部排序中。所謂的外部排序就是數(shù)據(jù)存儲在外部磁盤中荸百，數(shù)據(jù)量比較大闻伶，內(nèi)存有限，無法將數(shù)據(jù)全部加載到內(nèi)存中够话。
比如說我們有 10GB 的訂單數(shù)據(jù)蓝翰，我們希望按訂單金額（假設金額都是正整數(shù)）進行排序，但是我們的內(nèi)存有限女嘲，只有幾百 MB畜份，沒辦法一次性把 10GB 的數(shù)據(jù)都加載到內(nèi)存中。
我們可以先掃描一遍文件欣尼，看訂單金額所處的數(shù)據(jù)范圍爆雹。假設經(jīng)過掃描之后我們得到，訂單金額最小是 1 元愕鼓，最大是 10 萬元钙态。我們將所有訂單根據(jù)金額劃分到 100 個桶里，第一個桶我們存儲金額在 1 元到 1000 元之內(nèi)的訂單菇晃，第二桶存儲金額在 1001 元到 2000 元之內(nèi)的訂單驯绎，以此類推。每一個桶對應一個文件谋旦，并且按照金額范圍的大小順序編號命名（00剩失，01屈尼，02…99）。
訂單按照金額在 1 元到 10 萬元之間并不一定是均勻分布的 拴孤，所以 10GB 訂單數(shù)據(jù)是無法均勻地被劃分到 100 個文件中的脾歧。有可能某個金額區(qū)間的數(shù)據(jù)特別多，劃分之后對應的文件就會很大演熟，沒法一次性讀入內(nèi)存鞭执。這又該怎么辦呢？針對這些劃分之后還是比較大的文件芒粹，我們可以繼續(xù)劃分兄纺，比如，訂單金額在 1 元到 1000 元之間的比較多化漆，我們就將這個區(qū)間繼續(xù)劃分為 10 個小區(qū)間估脆，1 元到 100 元，101 元到 200 元座云，201 元到 300 元…901 元到 1000 元疙赠。如果劃分之后，101 元到 200 元之間的訂單還是太多朦拖，無法一次性讀入內(nèi)存圃阳，那就繼續(xù)再劃分，直到所有的文件都能讀入內(nèi)存為止璧帝。
二 計數(shù)排序
計數(shù)排序其實是桶排序的一種特殊情況捍岳。當要排序的 n 個數(shù)據(jù)，所處的范圍并不大的時候睬隶，比如最大值是 k祟同，我們就可以把數(shù)據(jù)劃分成 k 個桶。每個桶內(nèi)的數(shù)據(jù)值都是相同的理疙，省掉了桶內(nèi)排序的時間。
