基本思想
基數排序(radixsort)是在桶排序的基礎上發展而來的，兩種排序都是分配排序的高級實現。分配排序(distributivesort)的基本思想：排序過程無須比較關鍵字，而是通過“分配”和“收集”過程來實現排序。它們的時間復雜度可達到線性階：o(n)。
基數排序是一種穩定的排序算法，但有一定的局限性：
1、關鍵字可分解。
2、記錄的關鍵字位數較少，如果密集更好
3、如果是數字時，最好是無符號的，否則將增加相應的映射復雜度，可先將其正負分開排序。
先來看一下桶排序(radixsort)。
桶排序也稱為箱排序(binsort)，其基本思想是：設置若干個桶，依次掃描待排序的記錄r[0]，r[1]，…，r[n-1]，把關鍵字在某個范圍內的記錄全都裝入到第k個桶里(分配)，然后按序號依次將各非空的桶首尾連接起來(收集)。
例如，要將一副混洗的52張撲克牌按點數a<2<…<j<q<k排序，需設置13個“桶”，排序時依次將每張牌按點數放入相應的桶里，然后依次將這些桶首尾相接，就得到了按點數遞增序排列的一副牌。
桶排序中，桶的個數取決于關鍵字的取值范圍。因此桶排序要求關鍵字的類型是有限類型，否則可能要無限個桶。
一般情況下每個桶中存放多少個關鍵字相同的記錄是無法預料的，故桶的類型應設計成鏈表為宜。
為保證排序是穩定的，分配過程中裝箱及收集過程中的連接必須按先進先出原則進行。
對于桶排序來說，分配過程的時間是o(n)；收集過程的時間為o(m)（采用鏈表來存儲輸入的待排序記錄）或o(m+n)。因此，桶排序的時間為o(m+n)。若桶個數m的數量級為o(n)，則桶排序的時間是線性的，即o(n)。
前面說的幾大排序算法，大部分時間復雜度都是o(n2)，也有部分排序算法時間復雜度是o(nlogn)。而桶式排序卻能實現o(n)的時間復雜度。但桶排序的缺點是：首先是空間復雜度比較高，需要的額外開銷大。排序有兩個數組的空間開銷，一個存放待排序數組，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶數組就要至少m個空間。其次待排序的元素都要在一定的范圍內等等。
基數排序是對桶排序的一種改進，這種改進是讓“桶排序”適合于更大的元素值集合的情況，而不是提高性能。
我們還是用撲克牌的例子來說明。一張牌有兩個關鍵字組成：花色(桃<心<梅<方)+面值(a<2<3<4<...<k)。假如一張牌的大小首先被花色決定，同花色的牌有數字決定的話。我們就有兩種算法來解決這個問題。
即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小于花色高的，只有在同花色情況下，大小關系才由面值的大小確定。這就是多關鍵碼排序。
為得到排序結果，我們討論兩種排序方法。
方法1：先對花色排序，將其分為4個組，即梅花組、方塊組、紅心組、黑心組。再對每個組分別按面值進行排序，最后，將4個組連接起來即可。
方法2：先按13個面值給出13個編號組(2號，3號，...，a號)，將牌按面值依次放入對應的編號組，分成13堆。再按花色給出4個編號組(梅花、方塊、紅心、黑心)，將2號組中牌取出分別放入對應花色組，再將3號組中牌取出分別放入對應花色組，……，這樣，4個花色組中均按面值有序，然后，將4個花色組依次連接起來即可。
多關鍵碼排序按照從最主位關鍵碼到最次位關鍵碼或從最次位到最主位關鍵碼的順序逐次排序，分兩種方法：
最高位優先(mostsignificantdigitfirst)法，簡稱msd法：
1）先按k1排序分組，將序列分成若干子序列，同一組序列的記錄中，關鍵碼k1相等。
2）再對各組按k2排序分成子組，之后，對后面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd對各子組排序后。
3）再將各組連接起來，便得到一個有序序列。撲克牌按花色、面值排序中介紹的方法一即是msd法。
最低位優先(leastsignificantdigitfirst)法，簡稱lsd法：
1)先從kd開始排序，再對kd-1進行排序，依次重復，直到按k1排序分組分成最小的子序列后。
2)最后將各個子序列連接起來，便可得到一個有序的序列，撲克牌按花色、面值排序中介紹的方法二即是lsd法。
對數字型或字符型的單關鍵字，可以看作由多個數位或多個字符構成的多關鍵字，此時可以采"分配-收集”的方法進行排序，這一過程稱作基數排序法，其中每個數字或字符可能的取值個數稱為基數。比如，撲克牌的花色基數為4，面值基數為13。在整理撲克牌時，既可以先按花色整理，也可以先按面值整理。按花色整理時，先按紅、黑、方、花的順序分成4摞（分配），再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配），再按此順序疊放在一起（收集），如此進行二次分配和收集即可將撲克牌排列有序。
在“分配-收集”的過程中，需要保證排序的穩定性。
基數排序的思想就是將待排數據中的每組關鍵字依次進行桶分配。比如下面的待排序列：
135、242、192、93、345、11、24、19
我們將每個數值的個位，十位，百位分成三個關鍵字，例如：
135->k1(個位)=5，k2(十位)=3，k3(百位)=1。
然后從最低位個位開始(從最次關鍵字開始)，對所有數據的k1關鍵字進行桶分配(因為，每個數字都是0-9的，因此桶大小為10)，再依次輸出桶中的數據得到下面的序列。
(11)、(242、192)、(93)、(24)、(135、345)、(19)（從最次關鍵字開始排序，忽略百位與十位，按照個位上的數字分配）
再對上面的序列接著進行針對k2的桶分配，輸出序列為：
(11、19)、(24)、(135)、(242、345)、(192、93)（參考最次關鍵字來排序第二次關鍵字，忽略百位與個位，按照十位上的數字分配）
最后針對k3的桶分配，輸出序列為：
(011、019、024、093)、(135、192)、(242)、(345)（參考第二次關鍵字來排序最高關鍵字，忽略十位與個位，按照百位上的數字分配）
排序完畢。
java實現
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
public void radixsort(){ int max = array[0]; for(int i=0;i<array.length;i++){ //找到數組中的最大值 if(array[i]>max){ max = array[i]; } } int keysnum = 0; //關鍵字的個數，我們使用個位、十位、百位...當做關鍵字，所以關鍵字的個數就是最大值的位數 while(max>0){ max /= 10; keysnum++; } list<arraylist<integer>> buckets = new arraylist<arraylist<integer>>(); for(int i=0;i<10;i++){ //每位可能的數字為0~9，所以設置10個桶 buckets.add(new arraylist<integer>()); //桶由arraylist<integer>構成 } for(int i=0;i<keysnum;i++){ //由最次關鍵字開始，依次按照關鍵字進行分配 for(int j=0;j<array.length;j++){ //掃描所有數組元素，將元素分配到對應的桶中 //取出該元素對應第i+1位上的數字，比如258，現在要取出十位上的數字，258%100=58,58/10=5 int key =array[j]%(int)math.pow(10, i+1)/(int)math.pow(10, i); buckets.get(key).add(array[j]); //將該元素放入關鍵字為key的桶中 } //分配完之后，將桶中的元素依次復制回數組 int counter = 0; //元素計數器 for(int j=0;j<10;j++){ arraylist<integer> bucket =buckets.get(j); //關鍵字為j的桶 while(bucket.size()>0){ array[counter++] = bucket.remove(0); //將桶中的第一個元素復制到數組，并移除 } } system.out.print("第"+(i+1)+"輪排序："); display(); } } |
打印結果如下：
算法分析
初看起來，基數排序的執行效率似乎好的讓人無法相信，所有要做的只是把原始數據項從數組復制到鏈表，然后再復制回去。如果有10個數據項，則有20次復制，對每一位重復一次這個過程。假設對5位的數字排序，就需要20*5=100次復制。如果有100個數據項，那么就有200*5=1000次復制。復制的次數與數據項的個數成正比，即o(n)。這是我們看到的效率最高的排序算法。
不幸的是，數據項越多，就需要更長的關鍵字，如果數據項增加10倍，那么關鍵字必須增加一位（多一輪排序）。復制的次數和數據項的個數與關鍵字長度成正比，可以認為關鍵字長度是n的對數。因此在大多數情況下，基數排序的執行效率倒退為o(n*logn)，和快速排序差不多。
總結
以上就是本文關于基數排序簡介及java語言實現的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題，如有不足之處，歡迎留言指出。
原文鏈接：http://blog.csdn.net/u012152619/article/details/47702673
