一威彰、線性排序算法介紹
- 線性排序算法包括桶排序、計(jì)數(shù)排序穴肘、基數(shù)排序歇盼。
- 線性排序算法的時(shí)間復(fù)雜度為O(n)。
- 此3種排序算法都不涉及元素之間的比較操作评抚，是非基于比較的排序算法豹缀。
- 對排序數(shù)據(jù)的要求很苛刻伯复，重點(diǎn)掌握此3種排序算法的適用場景。
二邢笙、桶排序（Bucket sort）
- 算法原理：
- 將要排序的數(shù)據(jù)分到幾個(gè)有序的桶里啸如，每個(gè)桶里的數(shù)據(jù)再單獨(dú)進(jìn)行快速排序。
- 內(nèi)排完序之后氮惯，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出叮雳，組成的序列就是有序的了。
- 使用條件
- 要排序的數(shù)據(jù)需要很容易就能劃分成m個(gè)桶妇汗，并且桶與桶之間有著天然的大小順序债鸡。
- 數(shù)據(jù)在各個(gè)桶之間分布是均勻的。
- 適用場景
- 桶排序比較適合用在外部排序中铛纬。
- 外部排序就是數(shù)據(jù)存儲在外部磁盤且數(shù)據(jù)量大厌均，但內(nèi)存有限無法將整個(gè)數(shù)據(jù)全部加載到內(nèi)存中。
- 應(yīng)用案例
- 需求描述：
有10GB的訂單數(shù)據(jù)告唆，需按訂單金額（假設(shè)金額都是正整數(shù)）進(jìn)行排序
但內(nèi)存有限棺弊，僅幾百M(fèi)B - 解決思路：
掃描一遍文件，看訂單金額所處數(shù)據(jù)范圍擒悬，比如1元-10萬元模她，那么就分100個(gè)桶。
第一個(gè)桶存儲金額1-1000元之內(nèi)的訂單懂牧，第二個(gè)桶存1001-2000元之內(nèi)的訂單侈净，依次類推。
每個(gè)桶對應(yīng)一個(gè)文件僧凤，并按照金額范圍的大小順序編號命名（00畜侦，01，02躯保，…旋膳，99）。
將100個(gè)小文件依次放入內(nèi)存并用快排排序途事。所有文件排好序后验懊，只需按照文件編號從小到大依次讀取每個(gè)小文件并寫到大文件中即可。 - 注意點(diǎn)：若單個(gè)文件無法全部載入內(nèi)存尸变，則針對該文件繼續(xù)按照前面的思路進(jìn)行處理即可义图。
三、計(jì)數(shù)排序（Counting sort）
- 算法原理
- 計(jì)數(shù)其實(shí)就是桶排序的一種特殊情況召烂。
- 當(dāng)要排序的n個(gè)數(shù)據(jù)所處范圍并不大時(shí)碱工，比如最大值為k，則分成k個(gè)桶
- 每個(gè)桶內(nèi)的數(shù)據(jù)值都是相同的，就省掉了桶內(nèi)排序的時(shí)間痛垛。
代碼實(shí)現(xiàn)
案例分析：使用條件
- 只能用在數(shù)據(jù)范圍不大的場景中，若數(shù)據(jù)范圍k比要排序的數(shù)據(jù)n大很多桶蛔，就不適合用計(jì)數(shù)排序匙头；
- 計(jì)數(shù)排序只能給非負(fù)整數(shù)排序，其他類型需要在不改變相對大小情況下仔雷，轉(zhuǎn)換為非負(fù)整數(shù)蹂析；
- 比如如果考試成績精確到小數(shù)后一位，就需要將所有分?jǐn)?shù)乘以10碟婆，轉(zhuǎn)換為整數(shù)电抚。
四、基數(shù)排序（Radix sort）
- 算法原理（以排序10萬個(gè)手機(jī)號為例來說明）
- 比較兩個(gè)手機(jī)號碼a竖共，b的大小蝙叛，如果在前面幾位中a已經(jīng)比b大了，那后面幾位就不用看了公给。
- 借助穩(wěn)定排序算法的思想借帘，可以先按照最后一位來排序手機(jī)號碼，然后再按照倒數(shù)第二位來重新排序淌铐，以此類推肺然，最后按照第一個(gè)位重新排序。
- 經(jīng)過11次排序后腿准，手機(jī)號碼就變?yōu)橛行虻牧恕?/li>
- 每次排序有序數(shù)據(jù)范圍較小际起，可以使用桶排序或計(jì)數(shù)排序來完成。
- 使用條件
- 要求數(shù)據(jù)可以分割獨(dú)立的“位”來比較吐葱；
- 位之間由遞進(jìn)關(guān)系街望，如果a數(shù)據(jù)的高位比b數(shù)據(jù)大，那么剩下的地位就不用比較了弟跑；
- 每一位的數(shù)據(jù)范圍不能太大它匕，要可以用線性排序，否則基數(shù)排序的時(shí)間復(fù)雜度無法做到O(n)窖认。
五豫柬、思考
- 桶排序、計(jì)數(shù)排序扑浸、基數(shù)排序的原理以及使用條件烧给、應(yīng)用場景
- 如何根據(jù)年齡給100萬用戶數(shù)據(jù)排序？
- 我們有 10GB 的訂單數(shù)據(jù)喝噪，我們希望按訂單金額（假設(shè)金額都是正整數(shù)）進(jìn)行排序础嫡，但是我們的內(nèi)存有限，只有幾百 MB，沒辦法一次性把 10GB 的數(shù)據(jù)都加載到內(nèi)存中榴鼎。這個(gè)時(shí)候該怎么辦呢伯诬？
- 如果你所在的省有 50 萬考生，如何通過成績快速排序得出名次呢
- 排序10萬個(gè)手機(jī)號
- 對D巫财，a盗似，F(xiàn)，B平项，c赫舒，A，z這幾個(gè)字符串進(jìn)行排序闽瓢，要求將其中所有小寫字母都排在大寫字母前面接癌，但是小寫字母內(nèi)部和大寫字母內(nèi)部不要求有序。比如經(jīng)過排序后為a扣讼，c缺猛，z，D椭符，F(xiàn)枯夜，B，A艰山，這個(gè)如何實(shí)現(xiàn)呢湖雹？如果字符串中處理大小寫，還有數(shù)字曙搬，將數(shù)字放在最前面摔吏，又該如何解決呢？
