基本思想

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

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

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

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

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

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

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

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

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

對(duì)于桶排序來(lái)說(shuō)，分配過(guò)程的時(shí)間是O(n)；收集過(guò)程的時(shí)間為O(m)（采用鏈表來(lái)存儲(chǔ)輸入的待排序記錄）或O(m+n)。因此，桶排序的時(shí)間為O(m+n)。若桶個(gè)數(shù)m的數(shù)量級(jí)為O(n)，則桶排序的時(shí)間是線性的，即O(n)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

排序完畢。

java實(shí)現(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)鍵字的個(gè)數(shù)，我們使用個(gè)位、十位、百位...當(dāng)做關(guān)鍵字，所以關(guān)鍵字的個(gè)數(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個(gè)桶 
          buckets.add(new ArrayList<Integer>()); //桶由ArrayList<Integer>構(gòu)成 
       } 
       
       for(int i=0;i<keysNum;i++){ //由最次關(guān)鍵字開(kāi)始，依次按照關(guān)鍵字進(jìn)行分配 
           
          for(int j=0;j<array.length;j++){ //掃描所有數(shù)組元素，將元素分配到對(duì)應(yīng)的桶中 
              //取出該元素對(duì)應(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ù)制回?cái)?shù)組 
          int counter = 0; //元素計(jì)數(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); //將桶中的第一個(gè)元素復(fù)制到數(shù)組，并移除 
              } 
          } 
          System.out.print("第"+(i+1)+"輪排序："); 
          display(); 
       } 
       
   } 

打印結(jié)果如下：

算法分析

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

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

總結(jié)

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