前言：原文作者Leo-Yang洪碳。我不生產(chǎn)代碼，我只是代碼的搬運工
基數(shù)排序(radix sort)又稱桶排序（bucket sort）叼屠，相對于常見的比較排序瞳腌，基數(shù)排序是一種分配式排序，即通過將所有數(shù)字分配到應(yīng)在的位置最后再覆蓋到原數(shù)組完成排序的過程镜雨。
首先既然作為分配式排序嫂侍，聯(lián)想計數(shù)排序，每一位排序時存儲該次排序結(jié)果的數(shù)據(jù)結(jié)構(gòu)應(yīng)該至少是一個長度為10的數(shù)組（對應(yīng)十進(jìn)制該位0-9的數(shù)字）荚坞。同時可能存在以下情況：原數(shù)組中所有元素在該位上的數(shù)字都相同挑宠，那一維數(shù)組就沒法滿足我們的需要了，我們需要一個10*n(n為數(shù)組長度)的二維數(shù)組來存儲每次位排序結(jié)果颓影。熟悉計數(shù)排序結(jié)果的讀者可能會好奇：為什么不能像計數(shù)排序一樣各淀，在每個位置只存儲出現(xiàn)該數(shù)字的次數(shù)，而不存儲具體的值诡挂，這樣不就可以用一維數(shù)組了揪阿？這個我們不妨先思考一下疗我，在對基數(shù)排序分析完之后再來看這個問題。
算法過程
初始化：構(gòu)造一個10*n的二維數(shù)組南捂，一個長度為n的數(shù)組用于存儲每次位排序時每個桶子里有多少個元素吴裤。 2.循環(huán)操作：從低位開始（我們采用LSD的方式），將所有元素對應(yīng)該位的數(shù)字存到相應(yīng)的桶子里去（對應(yīng)二維數(shù)組的那一列）溺健。然后將所有桶子里的元素按照桶子標(biāo)號從小到大取出麦牺，對于同一個桶子里的元素，先放進(jìn)去的先取出鞭缭，后放進(jìn)去的后取出（保證排序穩(wěn)定性）剖膳。這樣原數(shù)組就按該位排序完畢了，繼續(xù)下一位操作岭辣，直到最高位排序完成吱晒。 下面給出一個實例幫助理解： 我們現(xiàn)有一個數(shù)組：73, 22, 93, 43, 55, 14, 28, 65, 39, 81 下面是排序過程（二維數(shù)組里每一列對應(yīng)一個桶，因為桶空間沒用完沦童，因此沒有將二維數(shù)組畫全）：
1.按個位排序
按第一位排序后數(shù)組結(jié)果： 81,22,73,93,43,14,55,65,28,39
可以看到數(shù)組已經(jīng)按個位排序了仑濒。
?2根據(jù)個位排序結(jié)果按百位排序
取出排序結(jié)果： 14,22,28,39,43,55,65,73,81,93
可以看到在個位排序的基礎(chǔ)上，百位也排序完成（對于百位相同的數(shù)子偷遗，如22,28墩瞳，因為個位已經(jīng)排序，而取出時也保持了排序的穩(wěn)定性氏豌，所以這兩個數(shù)的位置前后是根據(jù)他們個位排序結(jié)果決定的）喉酌。因為原數(shù)組元素最高只有百位，原數(shù)組也完成了排序過程泵喘。
我們現(xiàn)在來看看之前遺留的兩個問題：為什么不能用一維數(shù)組泪电，一定要用二維數(shù)組這樣的類似桶的結(jié)構(gòu)來存儲中間位排序結(jié)果？其實之所以要寫這個問題纪铺，是因為我覺得這個問題是理解基數(shù)排序的關(guān)鍵相速。基數(shù)排序本身原理很簡單霹陡，但是實現(xiàn)中有兩個問題需要考慮：1.怎么保留前一位的排序結(jié)果和蚪，這個問題用之前提到的排序穩(wěn)定性可以解決止状。2.怎么關(guān)聯(lián)該位排序結(jié)果和原數(shù)組元素烹棉，二維數(shù)組正是為了解決這個問題使用的辦法。在計數(shù)排序里怯疤，雖然保留了所有相等的元素的相對位置浆洗，但是這些相等的元素在計數(shù)排序里實際是沒有差別的，因此我們可以只保存數(shù)組里有多少個這樣的元素即可集峦。而基數(shù)排序里不同伏社，有些元素雖然在某一位上相同抠刺，但是他們其他位上很可能不同，如果只保存該位上有多少個5或者多少個6摘昌，那關(guān)于元素其他位的信息就都丟棄了速妖，這樣也就沒法對這些元素更高位進(jìn)行排序了。 弄清基數(shù)排序的過程后聪黎，我們來看看這個算法的時間復(fù)雜度是多少罕容？每次循環(huán)遍歷數(shù)組將元素放在指定位置Θ(n)，在從桶中取出數(shù)據(jù)Θ(n)稿饰，循環(huán)d次（d是位數(shù)）锦秒，時間復(fù)雜度就是Θ(r*n)
基數(shù)排序的java實現(xiàn)：
