拜託，面試別再問我基數排序了！！！
排序，面試中考察基本功問的比較多，工作多年以後，對排序的細節記憶不那麼清楚的小夥伴，面試時會比較吃虧。
有一種很神奇的排序， 基數排序 (Radix Sort)， 時間複雜度為O(n) ，今天花1分鐘，通過幾幅圖，爭取讓大家搞懂細節。
畫外音：居然還有時間複雜度為O(n)的排序演算法？不但有，其實還有很多。
舉個栗子：
假設待排序的陣列arr={72, 11, 82, 32, 44, 13, 17, 95, 54, 28, 79, 56}
基數排序的 兩個關鍵要點 ：
（1） 基 ：被排序的元素的“個位”“十位”“百位”，暫且叫“基”，栗子中“基”的個數是2（個位和十位）；
畫外音：來自野史，大神可幫忙修正。
（2） 桶 ：“基”的每一位，都有一個取值範圍，栗子中“基”的取值範圍是0-9共10種，所以需要10個桶（bucket），來存放被排序的元素；
基數排序的 演算法步驟 為：
FOR (每一個基) {
//迴圈內，以某一個“基”為依據
第一步： 遍歷資料集arr，將元素放入對應的桶bucket
第二步： 遍歷桶bucket，將元素放回資料集arr
}
更具體的，對應到上面的栗子，“基”有個位和十位，所以，FOR迴圈會執行兩次。
【第一次：以“個位”為依據】
畫外音：上圖中標紅的部分，個位為“基”。
第一步：遍歷資料集arr，將元素放入對應的桶bucket；
操作完成之後，各個桶會變成上面這個樣子，即： 個位數相同的元素，會在同一個桶裡 。
第二步 ：遍歷桶bucket，將元素放回資料集arr；
畫外音：需要注意，先入桶的元素要先出桶。
操作完成之後，資料集會變成上面這個樣子，即： 整體按照個位數排序了 。
畫外音：個位數小的在前面，個位數大的在後面。
【第二次：以“十位”為依據】
畫外音：上圖中標紅的部分，十位為“基”。
第一步 ：依然遍歷資料集arr，將元素放入對應的桶bucket；
操作完成之後，各個桶會變成上面這個樣子，即： 十位數相同的元素，會在同一個桶裡 。
第二步 ：依然遍歷桶bucket，將元素放回資料集arr；
操作完成之後，資料集會變成上面這個樣子，即： 整體按照十位數也排序了 。
畫外音：十位數小的在前面，十位數大的在後面。
首次按照個位從小到大，第二次按照十位從小到大，即： 排序結束 。
神奇不神奇！！！
幾個小點：
（1） 基的選取 ，可以先從個位開始，也可以先從十位開始，結果是一樣的；
（2）基數排序，是一種 穩定的排序 ；
（3） 時間複雜度 ，可以認為是 線性 的O(n)；
希望這一分鐘，大家有收穫。
原文釋出時間為：2018-10-10
本文作者：58沈劍