基本思想

基數(shù)排序(RadixSort)是在桶排序的基礎(chǔ)上發(fā)展而來的，兩種排序都是分配排序的高級實現(xiàn)。分配排序(DistributiveSort)的基本思想：排序過程無須比較關(guān)鍵字，而是通過“分配”和“收集”過程來實現(xiàn)排序。它們的時間復(fù)雜度可達(dá)到線性階：O(n)。

基數(shù)排序是一種穩(wěn)定的排序算法，但有一定的局限性：

　　1、關(guān)鍵字可分解。
　　2、記錄的關(guān)鍵字位數(shù)較少，如果密集更好
　　3、如果是數(shù)字時，最好是無符號的，否則將增加相應(yīng)的映射復(fù)雜度，可先將其正負(fù)分開排序。

先來看一下桶排序(RadixSort)。

桶排序也稱為箱排序(BinSort)，其基本思想是：設(shè)置若干個桶，依次掃描待排序的記錄R[0]，R[1]，…，R[n-1]，把關(guān)鍵字在某個范圍內(nèi)的記錄全都裝入到第k個桶里(分配)，然后按序號依次將各非空的桶首尾連接起來(收集)。

例如，要將一副混洗的52張撲克牌按點數(shù)A<2<…<J<Q<K排序，需設(shè)置13個“桶”，排序時依次將每張牌按點數(shù)放入相應(yīng)的桶里，然后依次將這些桶首尾相接，就得到了按點數(shù)遞增序排列的一副牌。

桶排序中，桶的個數(shù)取決于關(guān)鍵字的取值范圍。因此桶排序要求關(guān)鍵字的類型是有限類型，否則可能要無限個桶。

一般情況下每個桶中存放多少個關(guān)鍵字相同的記錄是無法預(yù)料的，故桶的類型應(yīng)設(shè)計成鏈表為宜。

為保證排序是穩(wěn)定的，分配過程中裝箱及收集過程中的連接必須按先進(jìn)先出原則進(jìn)行。

對于桶排序來說，分配過程的時間是O(n)；收集過程的時間為O(m)（采用鏈表來存儲輸入的待排序記錄）或O(m+n)。因此，桶排序的時間為O(m+n)。若桶個數(shù)m的數(shù)量級為O(n)，則桶排序的時間是線性的，即O(n)。

前面說的幾大排序算法，大部分時間復(fù)雜度都是O(n2)，也有部分排序算法時間復(fù)雜度是O(nlogn)。而桶式排序卻能實現(xiàn)O(n)的時間復(fù)雜度。但桶排序的缺點是：首先是空間復(fù)雜度比較高，需要的額外開銷大。排序有兩個數(shù)組的空間開銷，一個存放待排序數(shù)組，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶數(shù)組就要至少m個空間。其次待排序的元素都要在一定的范圍內(nèi)等等。

基數(shù)排序是對桶排序的一種改進(jìn)，這種改進(jìn)是讓“桶排序”適合于更大的元素值集合的情況，而不是提高性能。

我們還是用撲克牌的例子來說明。一張牌有兩個關(guān)鍵字組成：花色(桃<心<梅<方)+面值(A<2<3<4<...<K)。假如一張牌的大小首先被花色決定，同花色的牌有數(shù)字決定的話。我們就有兩種算法來解決這個問題。

即兩張牌，若花色不同，不論面值怎樣，花色低的那張牌小于花色高的，只有在同花色情況下，大小關(guān)系才由面值的大小確定。這就是多關(guān)鍵碼排序。

為得到排序結(jié)果，我們討論兩種排序方法。

方法1：先對花色排序，將其分為4個組，即梅花組、方塊組、紅心組、黑心組。再對每個組分別按面值進(jìn)行排序，最后，將4個組連接起來即可。

方法2：先按13個面值給出13個編號組(2號，3號，...，A號)，將牌按面值依次放入對應(yīng)的編號組，分成13堆。再按花色給出4個編號組(梅花、方塊、紅心、黑心)，將2號組中牌取出分別放入對應(yīng)花色組，再將3號組中牌取出分別放入對應(yīng)花色組，……，這樣，4個花色組中均按面值有序，然后，將4個花色組依次連接起來即可。

多關(guān)鍵碼排序按照從最主位關(guān)鍵碼到最次位關(guān)鍵碼或從最次位到最主位關(guān)鍵碼的順序逐次排序，分兩種方法：

最高位優(yōu)先(MostSignificantDigitfirst)法，簡稱MSD法：

1）先按k1排序分組，將序列分成若干子序列，同一組序列的記錄中，關(guān)鍵碼k1相等。

2）再對各組按k2排序分成子組，之后，對后面的關(guān)鍵碼繼續(xù)這樣的排序分組，直到按最次位關(guān)鍵碼kd對各子組排序后。

3）再將各組連接起來，便得到一個有序序列。撲克牌按花色、面值排序中介紹的方法一即是MSD法。

最低位優(yōu)先(LeastSignificantDigitfirst)法，簡稱LSD法：

1)先從kd開始排序，再對kd-1進(jìn)行排序，依次重復(fù)，直到按k1排序分組分成最小的子序列后。

2)最后將各個子序列連接起來，便可得到一個有序的序列，撲克牌按花色、面值排序中介紹的方法二即是LSD法。

對數(shù)字型或字符型的單關(guān)鍵字，可以看作由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采"分配-收集”的方法進(jìn)行排序，這一過程稱作基數(shù)排序法，其中每個數(shù)字或字符可能的取值個數(shù)稱為基數(shù)。比如，撲克牌的花色基數(shù)為4，面值基數(shù)為13。在整理撲克牌時，既可以先按花色整理，也可以先按面值整理。按花色整理時，先按紅、黑、方、花的順序分成4摞（分配），再按此順序再疊放在一起（收集），然后按面值的順序分成13摞（分配），再按此順序疊放在一起（收集），如此進(jìn)行二次分配和收集即可將撲克牌排列有序。

在“分配-收集”的過程中，需要保證排序的穩(wěn)定性。

基數(shù)排序的思想就是將待排數(shù)據(jù)中的每組關(guān)鍵字依次進(jìn)行桶分配。比如下面的待排序列：

135、242、192、93、345、11、24、19

我們將每個數(shù)值的個位，十位，百位分成三個關(guān)鍵字，例如：

135->k1(個位)=5，k2(十位)=3，k3(百位)=1。

然后從最低位個位開始(從最次關(guān)鍵字開始)，對所有數(shù)據(jù)的k1關(guān)鍵字進(jìn)行桶分配(因為，每個數(shù)字都是0-9的，因此桶大小為10)，再依次輸出桶中的數(shù)據(jù)得到下面的序列。

(11)、(242、192)、(93)、(24)、(135、345)、(19)（從最次關(guān)鍵字開始排序，忽略百位與十位，按照個位上的數(shù)字分配）

再對上面的序列接著進(jìn)行針對k2的桶分配，輸出序列為：

(11、19)、(24)、(135)、(242、345)、(192、93)（參考最次關(guān)鍵字來排序第二次關(guān)鍵字，忽略百位與個位，按照十位上的數(shù)字分配）

最后針對k3的桶分配，輸出序列為：

(011、019、024、093)、(135、192)、(242)、(345)（參考第二次關(guān)鍵字來排序最高關(guān)鍵字，忽略十位與個位，按照百位上的數(shù)字分配）

排序完畢。

java實現(xiàn)

public void radixSort(){ 
       
       int max = array[0]; 
       for(int i=0;i<array.length;i++){ //找到數(shù)組中的最大值 
          if(array[i]>max){ 
              max = array[i]; 
          } 
       } 
       
       int keysNum = 0; //關(guān)鍵字的個數(shù)，我們使用個位、十位、百位...當(dāng)做關(guān)鍵字，所以關(guān)鍵字的個數(shù)就是最大值的位數(shù) 
       while(max>0){ 
          max /= 10; 
          keysNum++; 
       } 
              
       List<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>(); 
       for(int i=0;i<10;i++){ //每位可能的數(shù)字為0~9，所以設(shè)置10個桶 
          buckets.add(new ArrayList<Integer>()); //桶由ArrayList<Integer>構(gòu)成 
       } 
       
       for(int i=0;i<keysNum;i++){ //由最次關(guān)鍵字開始，依次按照關(guān)鍵字進(jìn)行分配 
           
          for(int j=0;j<array.length;j++){ //掃描所有數(shù)組元素，將元素分配到對應(yīng)的桶中 
              //取出該元素對應(yīng)第i+1位上的數(shù)字，比如258，現(xiàn)在要取出十位上的數(shù)字，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]); //將該元素放入關(guān)鍵字為key的桶中 
          } 
           
          //分配完之后，將桶中的元素依次復(fù)制回數(shù)組 
          int counter = 0; //元素計數(shù)器 
          for(int j=0;j<10;j++){ 
              ArrayList<Integer> bucket =buckets.get(j); //關(guān)鍵字為j的桶 
              while(bucket.size()>0){ 
                  array[counter++] = bucket.remove(0); //將桶中的第一個元素復(fù)制到數(shù)組，并移除 
              } 
          } 
          System.out.print("第"+(i+1)+"輪排序："); 
          display(); 
       } 
       
   } 

打印結(jié)果如下：

算法分析

初看起來，基數(shù)排序的執(zhí)行效率似乎好的讓人無法相信，所有要做的只是把原始數(shù)據(jù)項從數(shù)組復(fù)制到鏈表，然后再復(fù)制回去。如果有10個數(shù)據(jù)項，則有20次復(fù)制，對每一位重復(fù)一次這個過程。假設(shè)對5位的數(shù)字排序，就需要20*5=100次復(fù)制。如果有100個數(shù)據(jù)項，那么就有200*5=1000次復(fù)制。復(fù)制的次數(shù)與數(shù)據(jù)項的個數(shù)成正比，即O(n)。這是我們看到的效率最高的排序算法。

不幸的是，數(shù)據(jù)項越多，就需要更長的關(guān)鍵字，如果數(shù)據(jù)項增加10倍，那么關(guān)鍵字必須增加一位（多一輪排序）。復(fù)制的次數(shù)和數(shù)據(jù)項的個數(shù)與關(guān)鍵字長度成正比，可以認(rèn)為關(guān)鍵字長度是N的對數(shù)。因此在大多數(shù)情況下，基數(shù)排序的執(zhí)行效率倒退為O(N*logN)，和快速排序差不多。

總結(jié)

以上就是本文關(guān)于基數(shù)排序簡介及Java語言實現(xiàn)的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。

最新評論