有一種很神奇的排序，基數排序(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); 希望這一分鐘，大家有收獲。

【本文為51CTO專欄作者“58沈劍”原創稿件，轉載請聯系原作者】

戳這里，看該作者更多好文