F基數(shù)排序課件

第十章 內(nèi)部排序￡10.1概述￡10.2插入排序￡10.2.1直接插入排序￡10.2.2其他插入排序￡10.2.3希爾排序￡10.3快速排序￡10.4選擇排序￡10.4.1簡單選擇排序￡10.4.2樹形選擇排序￡10.4.3堆排序￡10.5歸并排序￡10.6基數(shù)排序￡10.6.1多關(guān)鍵字的排序￡10.6.2鏈式基數(shù)排序￡10.7各種內(nèi)部排序方法的比較討論1￡10.6基數(shù)排序基數(shù)排序（RadixSorting）是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進行關(guān)系的方法?；鶖?shù)排序不需要進行記錄關(guān)鍵字間的比較。2￡10.6.1多關(guān)鍵字的排序（1）定義假設(shè)有n個記錄的序列 {R1,R2,…,Rn} （10－4），則稱序列（10－4）對關(guān)鍵字有序是指：對于序列中任意兩個記錄Ri和Rj(1≤i<j≤n)都滿足

<其中K0稱為最主位關(guān)鍵字，Kd-1稱為最次位關(guān)鍵字。且每個記錄Ri中含有d個關(guān)鍵字下列有序關(guān)系： 3（2）多關(guān)鍵字排序的實現(xiàn)②最低位優(yōu)先LSD（LeastSignigicantDigitfirst）1．算法實現(xiàn)：從最次位關(guān)鍵字Kd-1起進行排序。然后再對高一位的關(guān)鍵字Kd-2進行排序，依次重復，直至對K0進行排序后便成為一個有序序列。2．特點：a.按LSD進行排序時，不必分成子序列，對每個關(guān)鍵字都是整個序列參加排序，但對Ki(0≤i≤d－2)進行排序時，只能用穩(wěn)定的排序方法。

b.按LSD進行排序時，在一定的條件下（即對前一個關(guān)鍵字Ki(0≤i≤d-2)的不同值，后一個關(guān)鍵字Ki+1均取相同值），可通過若干次“分配”和“收集”來實現(xiàn)排序。5（3）例子例如，已知撲克牌中52張牌面的次序關(guān)系為： ?2<?3<…<?A<?2<?3<…<?A<?2<?3<…<?A<?2<?3<…<?A每一張牌有兩個“關(guān)鍵字”：花色(?<?<?<?)和面值(2<3<…<A)，且“花色”的地位高于“面值”。撲克牌整理成如上所述關(guān)系時：MSD：先按不同“花色”分成有次序的4堆,每一堆的牌均具有相同的“花色”,然后分別對每一堆按“面值”大小整理有序。LSD：先按不同“面值”分成13堆,然后將這13堆牌自小至大疊在一起（“3”在“2”之上，“4”在“3”之上，……，最上面的是4張“A”），然后將這付牌整個顛倒過來再重新按不同“花色”分成4堆，最后將這4堆牌按自小至大的次序合在一起（?在最下面，?在最上面）。6LSD和MSD方法也可應用于對一個關(guān)鍵字進行的排序。此時可將單關(guān)鍵字Ki看成是一個子關(guān)鍵字組：

(Ki1,Ki2,...,Kid)如對關(guān)鍵字取值范圍為0到999的一組對象，可看成是(K1,K2,K3)的組合。MSD方法按K1,K2,K3的順序?qū)λ袑ο笈判?；LSD方法按K3,K2,K1的順序?qū)λ袑ο笈判颉?￡10.6.2鏈式基數(shù)排序（1）定義有的邏輯關(guān)鍵字可以看成由若干個關(guān)鍵字復合而成的，且每個關(guān)鍵字Kj都在相同的范圍內(nèi)，則按LSD進行排序時，只要從最低數(shù)位關(guān)鍵字起，按關(guān)鍵字的不同值將序列中記錄“分配”到PADIX個隊列中后再“收集”之，如此重復d次。按這種方法實現(xiàn)的排序稱之為基數(shù)排序。其中“基”指的是RADIX的取值范圍。鏈式基數(shù)排序：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序。例如，若關(guān)鍵字是數(shù)值，且其值都在0≤K≤999范圍內(nèi)，則可把每一個十進制數(shù)字看成一個關(guān)鍵字，即可認為K由3個關(guān)鍵字(K0,K1,K2)組成，其中K0是百位數(shù)，K1是十位數(shù)，K2是個位數(shù)，對每一個關(guān)鍵字0≤Ki≤9（i＝0,1,2），“基”為10。

8930063083184505278008109589269(c)第一趟收集之后e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]

505930063278083269589008109184(d)第二趟分配之后505008109930063269278083184589(e)第二趟收集之后10(f)第三趟分配之后e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]

008269589063109184930505083278008063083109184269278505589930(g)第三趟收集之后的有序文件圖10.13鏈式基數(shù)排序示例50500810993006326927808318458911算法10.15如下：voidDistribute(SLCell&r,inti,ArrType&f,ArrType&e){ //靜態(tài)鏈表L的r域中記錄已按(keys[0],…,keys[i－1])有序。本算法按第i //個關(guān)鍵字keys[i]建立RADIX個子表，使同一子表中記錄的keys[i]相同。 //f[0..RADIX-1]和e[0..RADIX-1]分別指向各子表中第一個和最后一個記錄。 for(j=0;j<Radix;++j) //各子表初始化為空表 f[j]=0; for(p=r[0].next;p;p=r[p].next){ j=ord(r[p].keys[i]); //ord將記錄中第i個關(guān)鍵字映射到[0..RADIX-1] if(!f[j]) f[j]=p; else r[e[j]].next=p; e[j]=p; //將p所指的結(jié)點插入第j個子表中 }//for}//Distribute②算法實現(xiàn)算法10.15為鏈式基數(shù)排序中一趟分配的算法，算法10.16為一趟收集的算法，算法10.17為鏈式基數(shù)排序的算法。13voidCollect(SLCell&r,inti,ArrType&f,ArrType&e){ //本算法按keys[i]自小至大地將f[0..RADIX－1]所指各子表依次鏈接成一個鏈表， //一個鏈表，e[0..RADIX-1]為各子表的尾指針。 for(j=0;!f[j];j=succ(j)); //找第一個非空子表，succ為求后繼函數(shù) r[0].next=f[j]; //r[0].next指向第一個非空子表中第一個結(jié)點 t=e[j]; while(j<RADIX){ for(j=succ(j);j<RADIX－1&&!f[j];j=succ(j)); //找下一個非空子表 if(f[j]){ //鏈接兩個非空子表 r[t].next=f[j]; t=e[j]; } r[t].next=0; //t指向最后一個非空子表中的最后一個結(jié)點}//Collect算法10.16如下：算法10.16為一趟收集的算法，14voidRadixSort(SLList&L){ //L是采用靜態(tài)鏈表表示的順序表。對L作基數(shù)排序，使得L成為 //按關(guān)鍵字自小到大的有序靜態(tài)鏈表,L.r[0]為頭結(jié)點。 for(i=0;i<L.recnum;++i) L.r[i].next=i+1; L.r[L.recnum].next=0; //將L改造為靜態(tài)鏈表 for(i=0;i<L.keynum;++i){ //按最低位優(yōu)先依次對各關(guān)鍵字進行分配和收集 Distributr(L.r,i,f,e); //第i趟分配 Collect(L.r,i,f,e); //第i趟收集 }//for}//RadixSort算法10.17如下：算法10.17為鏈式基數(shù)排序的算法。15template<classElem,classComp>voidradix(ElemA[],ElemB[],intn,intk,intr,intcnt[]){//Iftherearekdigits,thenthisrequiresthatweassignkeys//tobinsktimes.//Ifweknowhowmanyvalueswillbeineachbin,thenan//auxiliaryarrayofsizercanbeusedtoholdthebins.//cnt[i]storesnumbersofrecordsinbin[i]intj;

for(inti=0,rtok=1;i<k;i++,rtok*=r){for(j=0;j<r;j++)cnt[j]=0;//Countnumbersofrecordsforeachbinfor(j=0;j<n;j++)cnt[(A[j]/rtok)%r]++;//IndexB:cnt[j]willbelastslotofbinj.

for(j=1;j<r;j++)