一纱兑、線性排序算法介紹

• 線性排序算法包括桶排序逼友、計(jì)數(shù)排序精肃、基數(shù)排序。
• 線性排序算法的時(shí)間復(fù)雜度為O(n)帜乞。
• 此3種排序算法都不涉及元素之間的比較操作司抱，是非基于比較的排序算法。
• 對(duì)排序數(shù)據(jù)的要求很苛刻挖函，重點(diǎn)掌握此3種排序算法的適用場(chǎng)景状植。

二浊竟、桶排序（Bucket sort）

1.算法原理：

• 將要排序的### 數(shù)據(jù)分到幾個(gè)有序的桶里，每個(gè)桶里的數(shù)據(jù)再單獨(dú)進(jìn)行快速排序津畸。

• 桶內(nèi)排完序之后振定，再把每個(gè)桶里的數(shù)據(jù)按照順序依次取出，組成的序列就是有序的了肉拓。

  
  
  桶排序

2.使用條件

• 要排序的數(shù)據(jù)需要很容易就能劃分成m個(gè)桶后频，并且桶與桶之間有著天然的大小順序。
• 數(shù)據(jù)在各個(gè)桶之間分布是均勻的暖途。

3.適用場(chǎng)景

• 桶排序比較適合用在外部排序中卑惜。
• 外部排序就是數(shù)據(jù)存儲(chǔ)在外部磁盤(pán)且數(shù)據(jù)量大，但內(nèi)存有限無(wú)法將整個(gè)數(shù)據(jù)全部加載到內(nèi)存中驻售。

4.應(yīng)用案例

• 需求描述：
  有10GB的訂單數(shù)據(jù)露久，需按訂單金額（假設(shè)金額都是正整數(shù)）進(jìn)行排序
  但內(nèi)存有限，僅幾百M(fèi)B
• 解決思路：
  掃描一遍文件欺栗，看訂單金額所處數(shù)據(jù)范圍毫痕，比如1元-10萬(wàn)元，那么就分100個(gè)桶迟几。
  第一個(gè)桶存儲(chǔ)金額1-1000元之內(nèi)的訂單消请，第二個(gè)桶存1001-2000元之內(nèi)的訂單，依次類(lèi)推类腮。
  每個(gè)桶對(duì)應(yīng)一個(gè)文件臊泰，并按照金額范圍的大小順序編號(hào)命名（00，01蚜枢，02缸逃，…，99）厂抽。
  將100個(gè)小文件依次放入內(nèi)存并用快排排序察滑。
  所有文件排好序后，只需按照文件編號(hào)從小到大依次讀取每個(gè)小文件并寫(xiě)到大文件中即可修肠。
• 注意點(diǎn)：若單個(gè)文件無(wú)法全部載入內(nèi)存贺辰，則針對(duì)該文件繼續(xù)按照前面的思路進(jìn)行處理即可。

三嵌施、計(jì)數(shù)排序（Counting sort）

1.算法原理

• 計(jì)數(shù)其實(shí)就是桶排序的一種特殊情況饲化。
• 當(dāng)要排序的n個(gè)數(shù)據(jù)所處范圍并不大時(shí)，比如最大值為k吗伤，則分成k個(gè)桶
• 每個(gè)桶內(nèi)的數(shù)據(jù)值都是相同的吃靠，就省掉了桶內(nèi)排序的時(shí)間。

2.代碼實(shí)現(xiàn)

// 計(jì)數(shù)排序足淆，a 是數(shù)組巢块，n 是數(shù)組大小礁阁。假設(shè)數(shù)組中存儲(chǔ)的都是非負(fù)整數(shù)。
public void countingSort(int[] a, int n) {
  if (n <= 1) return;

  // 查找數(shù)組中數(shù)據(jù)的范圍
  int max = a[0];
  for (int i = 1; i < n; ++i) {
    if (max < a[i]) {
      max = a[i];
    }
  }

  int[] c = new int[max + 1]; // 申請(qǐng)一個(gè)計(jì)數(shù)數(shù)組 c族奢，下標(biāo)大小 [0,max]
  for (int i = 0; i <= max; ++i) {
    c[i] = 0;
  }

  // 計(jì)算每個(gè)元素的個(gè)數(shù)姥闭，放入 c 中
  for (int i = 0; i < n; ++i) {
    c[a[i]]++;
  }

  // 依次累加
  for (int i = 1; i <= max; ++i) {
    c[i] = c[i-1] + c[i];
  }

  // 臨時(shí)數(shù)組 r，存儲(chǔ)排序之后的結(jié)果
  int[] r = new int[n];
  // 計(jì)算排序的關(guān)鍵步驟越走，有點(diǎn)難理解
  for (int i = n - 1; i >= 0; --i) {
    int index = c[a[i]]-1;
    r[index] = a[i];
    c[a[i]]--;
  }

  // 將結(jié)果拷貝給 a 數(shù)組
  for (int i = 0; i < n; ++i) {
    a[i] = r[i];
  }
}

案例分析：
假設(shè)只有8個(gè)考生分?jǐn)?shù)在0-5分之間棚品，成績(jī)存于數(shù)組A[8] = [2，5廊敌，3铜跑，0，2骡澈，3锅纺，0，3]肋殴。
使用大小為6的數(shù)組C[6]表示桶伞广，下標(biāo)對(duì)應(yīng)分?jǐn)?shù)，即0疼电，1，2减拭，3蔽豺，4，5拧粪。
C[6]存儲(chǔ)的是考生人數(shù)修陡，只需遍歷一邊考生分?jǐn)?shù)，就可以得到C[6] = [2可霎，0魄鸦，2，3癣朗，0拾因，1]。
對(duì)C[6]數(shù)組順序求和則C[6]=[2旷余，2绢记，4，7正卧，7蠢熄，8]，c[k]存儲(chǔ)的是小于等于分?jǐn)?shù)k的考生個(gè)數(shù)炉旷。
數(shù)組R[8] = [0签孔，0叉讥，2，2饥追，3图仓，3，3判耕，5]存儲(chǔ)考生名次透绩。那么如何得到R[8]的呢？
從后到前依次掃描數(shù)組A壁熄，比如掃描到3時(shí)帚豪，可以從數(shù)組C中取出下標(biāo)為3的值7，也就是說(shuō)草丧，到目前為止狸臣，包括自己在內(nèi)，分?jǐn)?shù)小于等于3的考生有7個(gè)昌执，也就是說(shuō)3是數(shù)組R的第7個(gè)元素（也就是數(shù)組R中下標(biāo)為6的位置）烛亦。當(dāng)3放入數(shù)組R后，小于等于3的元素就剩下6個(gè)了懂拾，相應(yīng)的C[3]要減1變成6煤禽。
以此類(lèi)推，當(dāng)掃描到第二個(gè)分?jǐn)?shù)為3的考生時(shí)岖赋，就會(huì)把它放入數(shù)組R中第6個(gè)元素的位置（也就是下標(biāo)為5的位置）檬果。當(dāng)掃描完數(shù)組A后，數(shù)組R內(nèi)的數(shù)據(jù)就是按照分?jǐn)?shù)從小到大排列的了唐断。

3.使用條件

• 只能用在數(shù)據(jù)范圍不大的場(chǎng)景中选脊，若數(shù)據(jù)范圍k比要排序的數(shù)據(jù)n大很多，就不適合用計(jì)數(shù)排序脸甘；
• 計(jì)數(shù)排序只能給非負(fù)整數(shù)排序恳啥，其他類(lèi)型需要在不改變相對(duì)大小情況下，轉(zhuǎn)換為非負(fù)整數(shù)丹诀；
• 比如如果考試成績(jī)精確到小數(shù)后一位钝的，就需要將所有分?jǐn)?shù)乘以10，轉(zhuǎn)換為整數(shù)铆遭。

四扁藕、基數(shù)排序（Radix sort）

1.算法原理（以排序10萬(wàn)個(gè)手機(jī)號(hào)為例來(lái)說(shuō)明）

• 比較兩個(gè)手機(jī)號(hào)碼a，b的大小疚脐，如果在前面幾位中a已經(jīng)比b大了亿柑，那后面幾位就不用看了。
• 借助穩(wěn)定排序算法的思想棍弄，可以先按照最后一位來(lái)排序手機(jī)號(hào)碼望薄，然后再按照倒數(shù)第二位來(lái)重新排序疟游，以此類(lèi)推，最后按照第一個(gè)位重新排序痕支。
• 經(jīng)過(guò)11次排序后颁虐，手機(jī)號(hào)碼就變?yōu)橛行虻牧恕?/li>
• 每次排序有序數(shù)據(jù)范圍較小，可以使用桶排序或計(jì)數(shù)排序來(lái)完成卧须。

2.使用條件

• 要求數(shù)據(jù)可以分割獨(dú)立的“位”來(lái)比較另绩；
• 位之間由遞進(jìn)關(guān)系，如果a數(shù)據(jù)的高位比b數(shù)據(jù)大花嘶，那么剩下的地位就不用比較了笋籽；
• 每一位的數(shù)據(jù)范圍不能太大，要可以用線性排序椭员，否則基數(shù)排序的時(shí)間復(fù)雜度無(wú)法做到O(n)车海。

五、思考

• 1.如何根據(jù)年齡給100萬(wàn)用戶數(shù)據(jù)排序隘击？
  • 答：利用桶排序侍芝。
• 2.對(duì)D，a埋同，F(xiàn)州叠，B，c凶赁，A咧栗，z這幾個(gè)字符串進(jìn)行排序，要求將其中所有小寫(xiě)字母都排在大寫(xiě)字母前面哟冬，但是小寫(xiě)字母內(nèi)部和大寫(xiě)字母內(nèi)部不要求有序。比如
  經(jīng)過(guò)排序后為a忆绰，c浩峡，z，D错敢，F(xiàn)翰灾，B，A稚茅，這個(gè)如何實(shí)現(xiàn)呢纸淮？如果字符串中處理大小寫(xiě)，還有數(shù)字亚享，將數(shù)字放在最前面咽块，又該如何解決呢？
• 答：用兩個(gè)指針a欺税、b：a指針從頭開(kāi)始往后遍歷侈沪，遇到大寫(xiě)字母就停下揭璃，b從后往前遍歷，遇到小寫(xiě)字母就停下亭罪，交換a瘦馍、b指針對(duì)應(yīng)的元素；重復(fù)如上過(guò)程应役，直到a情组、b指針相交。
  對(duì)于小寫(xiě)字母放前面箩祥，數(shù)字放中間院崇，大寫(xiě)字母放后面，可以先將數(shù)據(jù)分為小寫(xiě)字母和非小寫(xiě)字母兩大類(lèi)滥比，進(jìn)行如上交換后再在非小寫(xiě)字母區(qū)間內(nèi)分為數(shù)字和大寫(xiě)字母做同樣處理