排序-線性排序,如何做到百萬級數據秒級排序，時間複雜度O(n)？
- 2019 年 10 月 29 日
- 筆記
我們經常接觸的冒泡排序，快速排序，歸併排序等，這些排序時間複雜度大多是n^2或者N(logN),他們都是基於比較的排序(就是排序過程中數據兩兩做比較)，那你有知道和了解幾種線性排序的演算法嗎？他們的時間複雜度都是O(n),下面的幾個問題你會了嗎？
問題
- 1000萬訂單數據金額如何O(n)複雜度排序？
- 100萬考生成績如何O(n)複雜度秒級排序？
- 100個手機號如何從小到達O(n)複雜度排序？
常見的線性排序
桶排序
桶排序，顧名思義就是把要排序的元素放入各個桶中，然後每個桶中的元素再進行排序，這樣最後所有桶中的元素按桶的順序排列，則所有元素有序，我們假設n個元素，m個桶，那麼每個桶中放入(n/m=k)個元素,每個桶中元素的排序可以用之前我們分享過的快速排序，則桶排序的時間複雜度是m * k(logk),我們把k用n/m進行等價替換，所以時間複雜度就編程了 n* log(n/m)，當m非常接近n時，那麼桶排序的時間複雜度就是O(n)了。
1000萬訂單數據金額排序答疑：我們來看上面1000萬訂單數據金額排序的問題，假設我們只有10M記憶體，我們首先遍歷一遍文件，得出金額的最大值，假設最大值50000，也就是說1000萬訂單數據金額最小值是0，最大值是50000，那麼我們對0到50000的金額大小劃分1000個桶，把0到50的金額第一個桶，50到100的金額放入第二個桶，以此類推，然後對每個桶的數據進行排序，之後寫入磁碟文件，命名為bucket050.txt，以此類推，直到所有桶的數據都排序完畢,排序過程中，當某一個桶的數據過大，10M記憶體放不下時，可以用同樣的思想進行拆分為多個桶，用下面的圖描述一個這個過程。
桶排序的示例程式碼:
計數排序
計數排序跟上面的桶排序非常的類似，我們提到上面每個桶放入的元素是(k=n/m)，假設這個k=1，那麼相當於每個桶的元素就只有一個，試想一下，我們是不是只要遍歷原始數據，就相當於排序完成。
分析下100萬考生成績O(n)複雜度秒級排序
100萬考生，看著數據量很大，但我們透過現像看本質，這些數據的最大值是多少呢?750，是的，高考成績最大值750，最小值0，也就是說我我們只需要751個桶，我們聲明一個長度為751的數組，代表751個桶，數組的下標就是考生的成績，然後我們100萬數據遍歷，數組的值是這個成績出現的次數，當100萬數據遍歷完成後，我們遍歷我們創建的這個桶，根據數組中的值確定列印數組下標的次數，結果就是這100考生成績的排序。我們看程式碼實現。
我們看下邊的圖，就能理解上面程式碼的邏輯了
那麼為什麼要叫做計數排序呢？如果我想知道上圖中result結果中值為2元素的下標在什麼位置？該怎麼獲取呢？你有好的想法嗎
首先我們對上圖中的bucket的數組順序求和，得到如下
我們從後往前依次遍曆數組param中的元素，當遍歷到1時，我我們從求和後的bucket數組中獲取下標為1的元素2，也就說到現在為止，包含自己在內的小於等於1的元素只有2個，也就是說1是數組result中的第二個元素，這時小於等於1的元素就只剩1個了，當我們遍歷完數組param，得到的結果就是排列有序的了。
基數排序
基數排序屬於分配時排序，又稱桶子法，也用到了桶的概念，將待排序的元素局部進行排序分配至桶中，依次循環，直到排序完成。
上面的問題中有100個11位手機號進行從小到達排序為了方便，我這裡舉例使用3個手機號，手機號碼如下，我們從後往前依次遍歷手機號的每一位，手機號由從數字組成，最小0，最大9，我們一個桶，桶的大小是10。
第一次遍歷，三個手機號末尾是1，5，2；放入我們的桶中，那麼手機號的順序就變化為
第二次遍歷，三個手機號的倒數第二位是7，5，7；放入我們的桶中，手機號順序變化為
以此類推，如下圖比較方方式，每一次比較都會對手機號的排序做一個調整，最終手機號所有位數都比較完成，排序也就完成，但這裡有個需要注意的點，看上面我們第二次遍歷時，有兩個手機號末尾都是7，這是我們需要用到穩定排序，目的為了防止第一次排好序的最後以為發生了錯亂，就是保證7後面的最後一位1，5也是有序的。
我們用到程式碼來實現基數排序的演算法
應用場景
我們由三個問題引出了三種線性排序，這三種線性排序都有自己的特定應用場景，並不是說任何時候都能使用這三種線性排序，我們一塊總結一下這三種排序的應用場景。
桶排序：是一種外部排序，適用於數據量比較均勻，數據範圍不是很大的排序數據。
計數排序：適用於待排序的數據最大值不是很大情況的下，比如最大值是100000，就不可以了，這樣浪費空間太嚴重，然後排序數據都是正整數，如果不是，就要想辦法轉換成正整數。
基數排序：適用於那種有高低位的數據，且數據的長度都一樣，如果不一樣，看看是否能夠補全長度，再者，數據每一位的大小都不宜太大，因為數據也是放入桶中的，太大會過多浪費空間。
三種排序你都明白了嗎？歡迎留言區討論
