基數排序的設計與實現

1、 基數排序的設計與實現摘要:排序有多種：冒泡,插入，選擇,Shell,快速，都是大家所熟悉的,但是大多數學習者可能對基數排序還很陌生.基數排序(RadixSort):外排序的一種,是對箱排序的改進和推廣，它的基本思想是從低位到高位依次對Kj(j=d-1,d-2,，0)進行箱排序。在d趟箱排序中，所需的箱子數就是基數rd,這就是基數排序名稱的由來.關鍵詞：關鍵字基數排序0、引言排序(Sorting)是計算機程序設計中的一種重要操作，它的功能是將一個數據元素(或記錄)的任意序列，重新排序成一個按關鍵字有序的排列。由于待排序的記錄數量不同,使得排序過程中涉及的存儲器不同,可將排序方法分為兩大類:一類

2、是內部排序,指的是待排序記錄存放在計算機隨機存儲器中進行的排序過程；另一類是外部排序,指的是待排序記錄的數量很大,以致內存一次不能容納全部記錄,在排序過程同步中尚需對外存進行訪問的排序過程。內部排序的方法很多，但就其全面性能而言，很難提出一種被認為是最好的方法，每一種方法都有各自的優(yōu)缺點，適合在不同的環(huán)境(如記錄的初始排列狀態(tài)等)下使用。如果按排序過程中依據的不同原則對內部排序方法進行分類，則大致可分為插入排序、交換排序、選擇排序、歸并排序和基數排序五類；如果按內部排序過程中所需的工作量來區(qū)分，則可分為3類：(1)簡單的排序方法，其時間復雜度為O(nn)；(2)先進的排序方法，其時間復雜度為O

3、(nlogn)；(3)基數排序，其時間復雜度為O(dn)?；鶖蹬判?RadixSorting)是一種借助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。它適用于序列長度很大而關鍵字較小的序列。這個程序主要用于演示基數排序的過程。1、需求分析（1）用戶根據提示輸入10個無序數（2）回車后輸出排好序的10個數2、基數排序的基本概念單關鍵字和多關鍵字.0.1H.d-1文件中任一記錄Ri的關鍵字均由d個分量氣叫叫構成。若這d個分量中每個分量都是一個獨立的關鍵字，則文件是多關鍵字的（如撲克牌有兩個關鍵字：點數和花色）；否則文件是單關鍵字的，好（0Wjd）只不過是關鍵字中其中的一位（如字符串、十進制整數等

4、）。多關鍵字中的每個關鍵字的取值范圍一般不同。如撲克牌的花色取值只有4種，而點數則有13種。單關鍵字中的每位一般取值范圍相同。2.11實現多關鍵碼排序有兩種常用的方法（1）最高位優(yōu)先MSD（MostSignificantDigitfirst）（2）最低位優(yōu)先LSD（LeastSignificantDigitfirst）2.1.2最高位優(yōu)先法通常是一個遞歸的過程：（1）先根據最高位關鍵碼K1排序，得到若干對象組，對象組中每個對象都有相同關鍵碼K1。（2）再分別對每組中對象根據關鍵碼K2進行排序，按K2值的不同，再分成若干個更小的子組，每個子組中的對象具有相同的K1和K2值。（3）依此重復，直到對

5、關鍵碼Kd完成排序為止。（4）最后，把所有子組中的對象依次連接起來，就得到一個有序的對象序列。最低位優(yōu)先法首先依據最低位關鍵碼Kd對所有對象進行一趟排序，再依據次低位關鍵碼Kd-1對上一趟排序的結果再排序，依次重復，直到依據關鍵碼K1最后一趟排序完成，就可以得到一個有序的序列。使用這種排序方法對每一個關鍵碼進行排序時，不需要再分組，而是整個對象組都參加排序。LSD和MSD方法也可應用于對一個關鍵碼進行的排序。此時可將單關鍵碼Ki看作是一個子關鍵碼組：(K；,K；,町)基數設單關鍵字的每個分量的取值范圍均是：CWkWC(OWjd)可能的取值個數0jrd-1rd稱為基數?；鶖档倪x擇和關鍵字的分解因

6、關鍵宇的類型而異：若關鍵字是十進制整數，則按個、十等位進行分解，基數rd=10,C=0,C=9,09d為最長整數的位數；(2)若關鍵字是小寫的英文字符串，則rd=26,C=a,C=z,d為字符串的o25最大長度?；鶖蹬判虻幕舅枷牖鶖蹬判虻幕舅枷胧牵簭牡臀坏礁呶灰来螌j(j=d-1,d-2,，0)進行箱排序。在d趟箱排序中，所需的箱子數就是基數rd,這就是基數排序名稱的由來。3、基數排序數據結構設計基數排序是典型的LSD排序方法，利用“分配”和“收集”兩種運算對單關鍵碼進行排序。在這種方法中，把單關鍵碼Ki看成是一個d元組：(町，K沁,町)其中的每一個分量(1WjWd)也可看成是一個關鍵碼

7、。分量，(1WjWd)有radix種取值，則稱radix為基數。例如，關鍵碼984可以看成是一個3元組(9,8,4),每一位有0,1,，9等10種取值，基數radix=10。關鍵碼data可以看成是一個4元組(d,a,t,a),每一位有a,b,，z等26種取值，radix=26。針對d元組中的每一位分量，把對象序列中的所有對象，按丘；的取值，先“分配”到rd個隊列中去。然后再按各隊列的順序，依次把對象從隊列中“收集”起來，這樣所有對象按取值人，排序完成。如果對于所有對象的關鍵碼KO,K1,，Kn-1,依次對各位的分量，讓j=d,d-1,1,分別用這種“分配”、“收集”的運算逐趟進行排序，在最后

8、一趟“分配”、“收集”完成后，所有對象就按其關鍵碼的值從小到大排好序了。各隊列采用鏈式隊列結構，分配到同一隊列的關鍵碼用鏈接指針鏈接起來。每一隊列設置兩個隊列指針：intfrontradix指示隊頭，intrearradix指向隊尾。為了有效地存儲和重排n個待排序對象，以靜態(tài)鏈表作為它們的存儲結構。在對象重排時不必移動對象，只需修改各對象的鏈接指針即可?；鶖蹬判虻摹胺峙洹迸c“收集”過程第一趟第誕分配（按最職reHre1re2.黑燈w4re|Vwh比工rearelJ第1趟收集基數排序的“分配”與“收集”過程第二趟nf.rc2re3：r?l：r打怖同冷|：z區(qū)聞9第2趙收集基數排序的“分配”與“收

9、集”過程第三趟：hi川-|rIiI屈而IITiT-Tin黑趟分配（按側珈i=1）re0r?Ulre?reSre451re6：儲R挖圧re1）第謹臊算法基數排序依次對鍵值的個為位到高位逐位循環(huán)按鍵值的當前位將鏈表拆分為10個隊列鏈表按對應09的順序將10個鏈表收集成一個鏈表4、基數排序的算法分析基數排是穩(wěn)定的排序方法,排序文件可以r數組形式給出，也可以是以單鏈表形式給出（此時為鏈式的基數排序）則可通過修改出隊和人隊函數使表示箱子的鏈隊列無須分配結點空間，而使用原鏈表的結點空間。人隊出隊操作亦無需移動記錄而僅需修改指針。雖然這樣一來節(jié)省了一定的時間和空間，但算法要復雜得多，且時空復雜度就其數量級而

10、言并未得到改觀。下面是從時間和空間復雜度上極其穩(wěn)定性的一些基本分析:若每個關鍵碼有d位，需要重復執(zhí)行d趟“分配”與“收集”。每趟對n個對象進行“分配”，對radix個隊列進行“收集”?？倳r間復雜度為O(d(n+radix)若基數radix相同，對于對象個數較多而關鍵碼位數較少的情況，使用鏈式基數排序較好?；鶖蹬判蚴欠€(wěn)定的.基數排序所需的輔助存儲空間為O(n+rd)。5基數排序需要增加n+2radix個附加鏈接指針5、編程實現及測試結果5.1C語言實現的基數排序的代碼:#include#include#include#include#defineKEYN4structeleintkey;stru

11、ctele*link;voidbases(ele*h)ele*head10,*tail10,*p,*u;intfactor=1,i,j;p=*h;for(i=0;iKEYN;i+)for(j=0;jlink;j=(p-key/factor)%10;if(headj=NULL)headj=p;elsetailj-link=p;tailj=p;tailj-link=NULL;p=u;p=NULL;for(j=0;jlink=headj;u=tailj;factor*=10;*h=p;voidmain()ele*h,*u;inta10;coutvv輸入10個數：vvendl;for(inti=0;i

12、ai;h=NULL;/*先形成一個空鏈表*/for(i=0;iv10;i+)/*任意形成一個鏈表*/u=new(ele);u-key=ai;u-link=h;h=u;coutvv排序后的10個數：vvendl;bases(&h);/*排序*/for(u=h;u;u=u-link)/*順序輸出鏈表各表元的鏈值*/coutkey;coutendl;getch();5.2程序運行結果：6、不足之處該程序雖然實現了基數排序但沒有達到與其他排序進行比較的功能，且只能實現十個數的排序，還有很多地方需要改進。7、設計體會為期一周的課程設計緊張而充實，時間雖然不長，但還是讓我學到了不少新的東西，單就我個人課程設計而言，我對基數排序的基本概念及其排序過程有了一定的了解。當然通過本次課程設計，我也發(fā)現了自己的不足之處，在知道基數排許的概念和排序過程之后，便開始了基數排序的算法分析和設計，但在數據存儲結構的選擇上卡住了，不知道是選擇隊列還是數組或者鏈