電子發(fā)燒友App
前言
基數(shù)排序（radix sort）又稱桶排序（bucket sort），相對(duì)于常見的比較排序，基數(shù)排序是一種分配式排序，即通過(guò)將所有數(shù)字分配到應(yīng)在的位置最后再覆蓋到原數(shù)組完成排序的過(guò)程。今天我們要說(shuō)的基數(shù)排序就要利用到排序穩(wěn)定性這一點(diǎn)。
思考過(guò)程 我們回想一下我們小時(shí)候是怎么學(xué)習(xí)比較數(shù)字大小的？我們是先比位數(shù)，如果一個(gè)位數(shù)比另一個(gè)位數(shù)多，那這個(gè)數(shù)肯定更大。如果位數(shù)同樣多，就按位數(shù)遞減依次往下進(jìn)行比較，哪個(gè)數(shù)在這一位上更大那就停止比較，得出這個(gè)在這個(gè)位上數(shù)更大的數(shù)字整體更大的結(jié)論。當(dāng)然我們也可以從最小的位開始比較，這其實(shí)就對(duì)應(yīng)了基數(shù)排序里的MSD（most significant digital）和LSD（least significant digital）兩種排序方式。
想清楚了這一點(diǎn)之后，我們就要考慮如何存儲(chǔ)每一位排序結(jié)果的問(wèn)題了，首先既然作為分配式排序，聯(lián)想計(jì)數(shù)排序，每一位排序時(shí)存儲(chǔ)該次排序結(jié)果的數(shù)據(jù)結(jié)構(gòu)應(yīng)該至少是一個(gè)長(zhǎng)度為10的數(shù)組（對(duì)應(yīng)十進(jìn)制該位0-9的數(shù)字）。同時(shí)可能存在以下情況：原數(shù)組中所有元素在該位上的數(shù)字都相同，那一維數(shù)組就沒(méi)法滿足我們的需要了，我們需要一個(gè)10*n（n為數(shù)組長(zhǎng)度）的二維數(shù)組來(lái)存儲(chǔ)每次位排序結(jié)果。熟悉計(jì)數(shù)排序結(jié)果的讀者可能會(huì)好奇：為什么不能像計(jì)數(shù)排序一樣，在每個(gè)位置只存儲(chǔ)出現(xiàn)該數(shù)字的次數(shù)，而不存儲(chǔ)具體的值，這樣不就可以用一維數(shù)組了？這個(gè)我們不妨先思考一下，在對(duì)基數(shù)排序分析完之后再來(lái)看這個(gè)問(wèn)題。
現(xiàn)在我們可以存儲(chǔ)每次位排序的結(jié)果了，為了在下一位排序前用到這一位排序的結(jié)果，我們要將桶里排序的結(jié)果還原到原數(shù)組中去，然后繼續(xù)對(duì)更改后的原數(shù)組執(zhí)行前一步的位排序操作，如此循環(huán)，最后的結(jié)果就是數(shù)組內(nèi)元素先按最高位排序，最高位相同的依次按下一位排序，依次遞推。得到排序的結(jié)果數(shù)組。
算法過(guò)程初始化：構(gòu)造一個(gè)10*n的二維數(shù)組，一個(gè)長(zhǎng)度為n的數(shù)組用于存儲(chǔ)每次位排序時(shí)每個(gè)桶子里有多少個(gè)元素。
循環(huán)操作：從低位開始（我們采用LSD的方式），將所有元素對(duì)應(yīng)該位的數(shù)字存到相應(yīng)的桶子里去（對(duì)應(yīng)二維數(shù)組的那一列）。然后將所有桶子里的元素按照桶子標(biāo)號(hào)從小到大取出，對(duì)于同一個(gè)桶子里的元素，先放進(jìn)去的先取出，后放進(jìn)去的后取出（保證排序穩(wěn)定性）。這樣原數(shù)組就按該位排序完畢了，繼續(xù)下一位操作，直到最高位排序完成。
下面給出一個(gè)實(shí)例幫助理解：
我們現(xiàn)有一個(gè)數(shù)組：73， 22， 93， 43， 55， 14， 28， 65， 39， 81
下面是排序過(guò)程（二維數(shù)組里每一列對(duì)應(yīng)一個(gè)桶，因?yàn)橥翱臻g沒(méi)用完，因此沒(méi)有將二維數(shù)組畫全）：
1.按個(gè)位排序
?
按第一位排序后數(shù)組結(jié)果：
81，22，73，93，43，14，55，65，28，39
可以看到數(shù)組已經(jīng)按個(gè)位排序了。
2根據(jù)個(gè)位排序結(jié)果按百位排序
?
取出排序結(jié)果：
14，22，28，39，43，55，65，73，81，93
可以看到在個(gè)位排序的基礎(chǔ)上，百位也排序完成（對(duì)于百位相同的數(shù)子，如22，28，因?yàn)閭€(gè)位已經(jīng)排序，而取出時(shí)也保持了排序的穩(wěn)定性，所以這兩個(gè)數(shù)的位置前后是根據(jù)他們個(gè)位排序結(jié)果決定的）。因?yàn)樵瓟?shù)組元素最高只有百位，原數(shù)組也完成了排序過(guò)程。
總結(jié)
我們現(xiàn)在來(lái)看看之前遺留的兩個(gè)問(wèn)題：為什么不能用一維數(shù)組，一定要用二維數(shù)組這樣的類似桶的結(jié)構(gòu)來(lái)存儲(chǔ)中間位排序結(jié)果？其實(shí)之所以要寫這個(gè)問(wèn)題，是因?yàn)槲矣X(jué)得這個(gè)問(wèn)題是理解基數(shù)排序的關(guān)鍵?；鶖?shù)排序本身原理很簡(jiǎn)單，但是實(shí)現(xiàn)中有兩個(gè)問(wèn)題需要考慮：1.怎么保留前一位的排序結(jié)果，這個(gè)問(wèn)題用之前提到的排序穩(wěn)定性可以解決。2.怎么關(guān)聯(lián)該位排序結(jié)果和原數(shù)組元素，二維數(shù)組正是為了解決這個(gè)問(wèn)題使用的辦法。在計(jì)數(shù)排序里，雖然保留了所有相等的元素的相對(duì)位置，但是這些相等的元素在計(jì)數(shù)排序里實(shí)際是沒(méi)有差別的，因此我們可以只保存數(shù)組里有多少個(gè)這樣的元素即可。而基數(shù)排序里不同，有些元素雖然在某一位上相同，但是他們其他位上很可能不同，如果只保存該位上有多少個(gè)5或者多少個(gè)6，那關(guān)于元素其他位的信息就都丟棄了，這樣也就沒(méi)法對(duì)這些元素更高位進(jìn)行排序了。
弄清基數(shù)排序的過(guò)程后，我們來(lái)看看這個(gè)算法的時(shí)間復(fù)雜度是多少？每次循環(huán)遍歷數(shù)組將元素放在指定位置Θ（n），在從桶中取出數(shù)據(jù)Θ（n），循環(huán)d次（d是位數(shù)），時(shí)間復(fù)雜度就是Θ（r*n）
最后附上基數(shù)排序的java實(shí)現(xiàn)：
package sort;
public class RadixSort {
private static void radixSort（int［］ array，int d）
{
int n=1;//代表位數(shù)對(duì)應(yīng)的數(shù)：1，10，100.。。
int k=0;//保存每一位排序后的結(jié)果用于下一位的排序輸入
int length=array.length;
int［］［］ bucket=new int［10］［length］;//排序桶用于保存每次排序后的結(jié)果，這一位上排序結(jié)果相同的數(shù)字放在同一個(gè)桶里
int［］ order=new int［length］;//用于保存每個(gè)桶里有多少個(gè)數(shù)字
while（n《d）
{
for（int num:array） //將數(shù)組array里的每個(gè)數(shù)字放在相應(yīng)的桶里
{
int digit=（num/n）%10;
bucket［digit］［order［digit］］=num;
order［digit］++;
}
for（int i=0;i《length;i++）//將前一個(gè)循環(huán)生成的桶里的數(shù)據(jù)覆蓋到原數(shù)組中用于保存這一位的排序結(jié)果
{
if（order［i］！=0）//這個(gè)桶里有數(shù)據(jù)，從上到下遍歷這個(gè)桶并將數(shù)據(jù)保存到原數(shù)組中
{
for（int j=0;j《order［i］;j++）
{
array［k］=bucket［i］［j］;
k++;
}
}
order［i］=0;//將桶里計(jì)數(shù)器置0，用于下一次位排序
}
n*=10;
k=0;//將k置0，用于下一輪保存位排序結(jié)果
}
}
public static void main（String［］ args）
{
int［］ A=new int［］{73，22， 93， 43， 55， 14， 28， 65， 39， 81};
radixSort（A， 100）;
for（int num:A）
{
System.out.println（num）;
}
}
}
下面是程序運(yùn)行結(jié)果：
14
22
28
39
43
55
65
73
81
93
工商網(wǎng)監(jiān)
評(píng)論