這節(jié)課主要講了三種線性排序方式：桶排序场梆、計數(shù)排序、基數(shù)排序纯路。這三種排序都是最好情況下時間復(fù)雜度 O(n) 的算法辙谜，都對待排數(shù)據(jù)有特別的要求。
桶排序
桶排序感昼，顧名思義，會用到“桶”罐脊。核心思想是將要排序的數(shù)據(jù)分到幾個有序的桶里定嗓，再對每個桶里的數(shù)據(jù)進行單獨排序。最后再把每個桶里的數(shù)據(jù)按順序連接起來萍桌，組成的序列就是有序的了宵溅。
- 對數(shù)據(jù)的要求： 待排數(shù)據(jù)要能很容易劃分成 n 個桶，桶之間有天然的大小順序上炎。并且數(shù)組在各個桶之間的分布是比較均勻的恃逻。
- 時間空間復(fù)雜度： 假設(shè) n 個數(shù)據(jù)均勻地分布到 m 個桶內(nèi)雏搂，每個桶就有 k = n/m 個元素。對桶內(nèi)每個數(shù)據(jù)使用快排寇损，總時間復(fù)雜度 O(m * k * logk) = O(n * log(n/m))凸郑。當(dāng) m 接近 n 時，時間復(fù)雜度為 O(n)矛市。當(dāng)數(shù)據(jù)分布很不均勻時芙沥，時間復(fù)雜度會退化到 O(nlogn)。
- 應(yīng)用場景： 可以用于外部排序浊吏。
比如用幾百 M 內(nèi)存排序 10GB 的訂單數(shù)據(jù)（假設(shè)金額都是正整數(shù)）而昨。
我們可以先掃描一遍文件，看訂單金額所處的數(shù)據(jù)范圍找田。假設(shè)經(jīng)過掃描之后我們得到歌憨，訂單金額最小是 1 元，最大是 10 萬元墩衙。我們將所有訂單根據(jù)金額劃分到 100 個桶里务嫡，第一個桶我們存儲金額在 1 到 1000 元之間的訂單，第二桶存儲金額在 1001 元到 2000 元之間的訂單底桂，以此類推植袍。每一個桶對應(yīng)一個文件，并且按照金額大小順序命名（00，01嗤放，02…99）锈津。
在理想情況下，如果訂單金額在 1 到 10 萬之間均勻分布厅篓，那訂單會被均勻劃分到 100 個文件中，每個小文件中存儲大約 100MB 的數(shù)據(jù)捶码，我們就可以將這 100 個小文件依次放到內(nèi)存中羽氮，用快排來排序。等所有文件都排好序之后惫恼，我們只要按照文件編號档押，從小到大依次讀取每個小文件中的訂單數(shù)據(jù)，并將其寫入到一個文件中祈纯，那這個文件中存儲的就是按照金額從小打到排序的訂單數(shù)據(jù)了令宿。
不過，訂單金額很可能是分布極不均勻的腕窥，若是集中在某個區(qū)間粒没，比如 1 到 1000 元中間比較多，那我們還可以對這個區(qū)間再進行具體的劃分簇爆，比如 1 到 100 是一個區(qū)間癞松，101 到 200 是第二個區(qū)間爽撒，以此類推。如果劃分之后响蓉，某個區(qū)間的訂單仍然太多硕勿，那還可以繼續(xù)劃分，直到所有文件都可以讀入內(nèi)存為止厕妖。
計數(shù)排序
計數(shù)排序應(yīng)該是桶排序的一種比較特殊的情況首尼。這種情況要求待排序的數(shù)據(jù)集中在一個不大的范圍內(nèi)，比如最大值是 K 言秸，我們就可以把數(shù)據(jù)分成 K 個桶软能，每個桶里的數(shù)據(jù)都是相同的，省掉了桶內(nèi)排序的時間举畸。若有負數(shù)查排，還需要設(shè)置偏移量。
- 對數(shù)據(jù)的要求： 數(shù)據(jù)集中在一個較小的范圍內(nèi)抄沮。
- 時間空間復(fù)雜度： 時間復(fù)雜度是 O(n)跋核。只有只有三趟遍歷，第一趟計數(shù)叛买，第二趟映射到輔助數(shù)組砂代，第三趟拷貝回原數(shù)組÷收酰空間復(fù)雜度是 O(n)刻伊，雖然省掉了桶內(nèi)排序的時間，但是空間沒有減少椒功。
- 應(yīng)用場景： 比如對高考考生成績排序捶箱，只有幾百種情況，直接開幾百個桶就可以了动漾。
基數(shù)排序
是一種多關(guān)鍵字排序方法丁屎。從關(guān)鍵字的后部往前進行多輪 O(n) 的穩(wěn)定性排序排序。
- 對數(shù)據(jù)的要求： 待排數(shù)據(jù)的鍵值部分可以分成幾個部分旱眯。
- 時間空間復(fù)雜度： 總時間復(fù)雜度是鍵值部分個數(shù) m 的 O(n) 倍晨川，由于鍵值部分個數(shù)一般是一個很小的常量，所以删豺，總時間仍是 O(n)础爬。空間復(fù)雜度是 O(n)吼鳞。
- 應(yīng)用場景： 對手機號進行排序。鍵值部分個數(shù)是 11 個叫搁，總共進行 11 趟赔桌。其他情況若是關(guān)鍵字部分長度不一供炎，可以采用填充法。
課后思考
根據(jù)年齡給 100 萬用戶排序
使用桶排序疾党，開 120 個桶音诫，看情況要不要進行外部排序。
對包含大寫字母雪位、小寫字母竭钝、數(shù)字的一個字符串按照小寫字母在前，大寫字母在最后雹洗，數(shù)字在中間香罐，不用排序算法進行排列。
這是一個荷蘭國旗問題时肿。
使用三個指針庇茫，pre, current, last 分別指向小寫字母部分的結(jié)尾，數(shù)字部分的開頭螃成，大寫字母部分的開頭旦签，采用交換元素的方法，遍歷一遍待排字符串即可寸宏。時間復(fù)雜度 O(n)宁炫，空間復(fù)雜度 O(1)。
