博文位址
| 我的GitHub | 我的部落格 | 我的微信 | 我的郵箱 |
|---|---|---|---|
| baiqiantao | bqt20094 | [email protected] |
目錄
- 13 | 線性排序：如何根據年齡給100萬使用者資料排序？
- 總結
- 桶排序 Bucket sort
- 時間複雜度分析
- 桶排序對要排序資料的要求
- 桶排序比較适合用在外部排序中
- 計數排序 Counting sort
- 計數排序動圖
- 計數排序過程分析
- 基數排序 Radix sort
- 排序過程
- 基數排序對要排序資料的要求
- 14 | 排序優化：如何實作一個通用的、高性能的排序函數？
- 如何選擇合适的排序算法？
- 如何優化快速排序？
- 分析 C 語言中的排序函數 qsort()
今天講的是三種時間複雜度是
O(n)
的排序算法：桶排序、計數排序、基數排序。
因為這些排序算法的時間複雜度是線性的，是以我們把這類排序算法叫作
線性排序
（Linear sort）。
之是以能做到線性的時間複雜度，主要原因是，這三個算法是
非基于比較
的排序算法，都不涉及元素之間的比較操作。
這幾種排序算法了解起來都不難，時間、空間複雜度分析起來也很簡單，但是
對要排序的資料要求很苛刻
，我們學習的重點是掌握這些排序算法的
适用場景
。
- 桶排序時間複雜度是
O(n+k)
O(n+k)
O(n*k)
- 桶排序空間複雜度是
O(n)
O(k)
O(n+k)
- 都是穩定的排序算法
核心思想是将要排序的資料分到幾個
有序的桶
裡，
每個桶裡的資料再單獨進行排序
。桶内排完序之後，再把每個桶裡的資料按照順序依次取出，組成的序列就是有序的了。
- 如果要排序的資料有 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，這個時候該怎麼辦呢？
- 我們可以先掃描一遍檔案，看訂單金額所處的資料範圍。假設經過掃描之後我們得到，訂單金額最小是 1 元，最大是 10 萬元。
- 我們将所有訂單根據金額劃分到 100 個桶裡，第一個桶我們存儲金額在 1 元到 1000 元之内的訂單，第二桶存儲金額在 1001 元到 2000 元之内的訂單，以此類推。每一個桶對應一個檔案，并且按照金額範圍的大小順序編号命名
（00，01，02...99）
- 理想的情況下，如果訂單金額在 1 到 10 萬之間均勻分布，那訂單會被均勻劃分到 100 個檔案中，每個小檔案中存儲大約 100MB 的訂單資料，我們就可以将這 100 個小檔案依次放到記憶體中，用快排來排序。
- 等所有檔案都排好序之後，我們隻需要按照檔案編号，從小到大依次讀取每個小檔案中的訂單資料，并将其寫入到一個檔案中，那這個檔案中存儲的就是按照金額從小到大排序的訂單資料了。
如果訂單金額分布不均勻，可以對資料較多的區間再次使用桶排序 劃分為更小的區間
計數排序其實是桶排序的一種特殊情況。
當要排序的 n 個資料所處的範圍并不大的時候，比如最大值是 k，我們就可以把資料劃分成 k 個桶。每個桶内的資料值都是相同的，省掉了桶内排序的時間。
比如，聯考考生成績排名。
這個動圖并不準确，其更像是桶排序的過程，因為看起來他是先把待排的元素一個個的放到了桶裡，這樣的空間複雜度隻能是，就沒法優化為O(n)
O(k)
假設有 8 個考生，其成績放在一個數組
A[8]
中：
2,5,3,0,2,3,0,3
。考生的成績從 0 到 5 分，我們使用大小為 6 的數組
C[6]
表示桶，其中下标為
分數
、值為
對應的考生個數
- 首先我們需要周遊一遍考生分數，然後就可以得到
C[6]
[2,0,2,3,0,1]
- 從中可以看出，分數為 3 分的考生有 3 個，小于 3 分的考生有 4 個
- 是以，成績為 3 分的考生在排序之後的有序數組
R[8]
那我們如何快速計算出每個分數的考生在有序數組中對應的存儲位置呢？
- 我們首先對
C[6]
C[k]
C[6] = [2,2,4,7,7,8]
- 我們
從後到前
2,5,3,0,2,3,0,3
- 比如，當掃描到 3 時，我們可以從數組 C 中取出下标為 3 的值 7，也就是說，到目前為止，包括自己在内，分數小于等于 3 的考生有 7 個，也就是說 3 是數組 R 中的第 7 個元素（也就是數組 R 中下标為 6 的位置）。當 3 放入到數組 R 中後，小于等于 3 的元素就隻剩下了 6 個了，是以相應的
C[3]
- 以此類推，當我們掃描到第 2 個分數為 3 的考生的時候，就會把它放入數組 R 中的第 6 個元素的位置（也就是下标為 5 的位置）。
- 當我們掃描完整個數組 A 後，數組 R 内的資料就是按照分數從小到大有序排列的了。
- 比如，當掃描到 3 時，我們可以從數組 C 中取出下标為 3 的值 7，也就是說，到目前為止，包括自己在内，分數小于等于 3 的考生有 7 個，也就是說 3 是數組 R 中的第 7 個元素（也就是數組 R 中下标為 6 的位置）。當 3 放入到數組 R 中後，小于等于 3 的元素就隻剩下了 6 個了，是以相應的
從數組 A 中取數，也是可以從頭開始取，但是就不是穩定排序算法了(因為最先取到的元素會被放到後面)
- 數排序隻能用在
資料範圍不大
- 而且，計數排序隻能給
非負整數
，而計數排序空間複雜度是O(n)
O(k)
假設我們有 10 萬個手機号碼，希望将這 10 萬個手機号碼從小到大排序，你有什麼比較快速的排序方法呢？
這個問題裡有這樣的規律：假設要比較兩個手機号碼 a，b 的大小，如果在前面幾位中，a 手機号碼已經比 b 手機号碼大了，那後面的幾位就不用看了。
先按照最後一位來排序手機号碼，然後再按照倒數第二位重新排序，以此類推，最後按照第一位重新排序。經過 11 次排序之後，手機号碼就都有序了。
注意，這裡按照每位來排序的排序算法一定要是 穩定的
- 根據每一位來排序，我們可以用剛講過的桶排序或者計數排序，它們的時間複雜度可以做到
O(n)
- 如果要排序的資料有 k 位，那我們就需要 k 次桶排序或者計數排序，總的時間複雜度是
O(k*n)
- 當 k 不大的時候，比如手機号碼排序的例子，k 最大就是 11，是以基數排序的時間複雜度就近似于
O(n)
- 需要
可以分割
- 位之間
有遞進的關系
- 每一位的
資料範圍不能太大
O(n)
實際上，有時候要排序的資料并不都是等長的，比如排序牛津字典中的 20 萬個英文單詞。這時，我們可以把所有的單詞
補齊
到相同長度(比如在後面補
)，這樣就可以繼續用基數排序了。
- 線性排序算法的時間複雜度雖然比較低，但适用場景比較特殊，是以不适合作為通用的排序函數。
- 如果對小規模資料進行排序，可以選擇時間複雜度是
O(n^2)
- 如果對大規模資料進行排序，時間複雜度是
O(nlogn)
為了兼顧任意規模資料的排序，一般都會首選時間複雜度是
O(nlogn)
的排序算法來實作排序函數。
- 歸并排序可以做到平均情況、最壞情況下的時間複雜度都是
O(nlogn)
O(n)
- 快速排序空間複雜度是
O(logn)
O(n^2)
時間複雜度退化為
O(n^2)
的主要原因是因為我們
分區點
選得不夠合理。
為了提高快速排序算法的性能，我們要盡可能地讓每次分區都比較平均。最理想的分區點是：被分區點分開的兩個分區中，資料的數量差不多。
兩個比較常用、比較簡單的分區算法：
- 三數取中法：從區間的首、尾、中間，分别取出一個數，然後取這 3 個數的中間值作為分區點
- 随機法：每次從要排序的區間中，随機選擇一個元素作為分區點
雖說
qsort()
從名字上看，很像是基于快速排序算法實作的，實際上它并不僅僅用了快排這一種算法。
- 要排序的資料量比較小的時候，
qsort()
歸并排序
- 對于小資料量的排序，歸并排序需要額外記憶體空間的問題不大，用空間換時間
- 要排序的資料量比較大的時候，
qsort()
快速排序
-
qsort()
三數取中法
-
qsort()
模拟遞歸
堆棧溢出
-
- 在快速排序的過程中，當要排序的區間中元素的個數小于等于 4 時，
qsort()
插入排序
- 因為在小規模資料面前，
O(n^2)
O(nlogn)
- 在
qsort()
- 因為在小規模資料面前，
2021-8-13
本文來自部落格園，作者：白乾濤，轉載請注明原文連結：https://www.cnblogs.com/baiqiantao/p/15139455.html