數(shù)據(jù)結(jié)構(gòu)第十章 內(nèi)部排序

第十章內(nèi)部排序10.1概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法比較本章學(xué)習(xí)要點(diǎn)習(xí)題與上機(jī)作業(yè)1.10.1概述10.1.1什么是排序其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列，是根據(jù)記錄關(guān)鍵字的值的非遞減或者非遞增（遞增或者遞減）的關(guān)系將文件記錄的次序重新排列。[例]

將下列關(guān)鍵字序列：

52,49,80,36,14,58,61,23,97,75

調(diào)整為：

14,23,36,49,52,58,61,75,80,972.10.1.2排序的分類[根據(jù)排序時(shí)文件記錄的存放位置]

內(nèi)部排序：排序過程中將全部記錄放在內(nèi)存中處理。

外部排序：排序過程中需在內(nèi)外存之間交換信息。[根據(jù)排序前后相同關(guān)鍵字記錄的相對次序]

穩(wěn)定排序：設(shè)文件中任意兩個(gè)記錄的關(guān)鍵字值相同，即Ki=Kj(ij)，若排序之前記錄Ri領(lǐng)先于記錄Rj

，排序后這種關(guān)系不變(對所有輸入實(shí)例而言)。

不穩(wěn)定排序：只要有一個(gè)實(shí)例使排序算法不滿足穩(wěn)定性要求。3.[根據(jù)文件的存儲結(jié)構(gòu)劃分排序的種類]

順序存儲

鏈?zhǔn)酱鎯?/p>

地址存儲:待排記錄順序存儲，排序時(shí)只對輔助表(關(guān)鍵字+指針)的表目進(jìn)行物理重排。[根據(jù)內(nèi)部排序的方法]

插入排序交換排序選擇排序歸并排序基數(shù)排序[根據(jù)排序算法所需的輔助空間]

就地排序：O(1)非就地排序：O(n)或與n有關(guān)

keyptr4.內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大記錄的有序序列長度的過程。經(jīng)過一趟排序有序序列區(qū)無序序列區(qū)有序序列區(qū)無序序列區(qū)

內(nèi)部排序方法基于不同的“擴(kuò)大”有序序列長度的方法。5.10.1.3評價(jià)排序算法的主要標(biāo)準(zhǔn)

[時(shí)間開銷]

考察算法的兩個(gè)基本操作的次數(shù)：比較關(guān)鍵字移動(dòng)記錄算法時(shí)間還與輸入實(shí)例的初始狀態(tài)有關(guān)時(shí)，分情況：最好最壞平均[空間開銷]

所需的輔助空間6.討論約定

(1)順序存儲

(2)按記錄關(guān)鍵字非遞減，關(guān)鍵字為整數(shù)#defineMAXSIZE20typedefintKeyType;typedefstruct{ KeyTypekey; InfoTypeotherinfo; }RedType;typedefstruct{ RedTyper[MAXSIZE+1];//r[0]閑置或作哨兵

intlength;}SqList;012…L.length…MAXSIZESqListL；L.r7.10.2插入排序有序序列R[1..i-1]R[i]無序序列R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]無序序列R[i+1..n]不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述： 直接插入排序（基于順序查找）

折半插入排序（基于折半查找）

表插入排序（基于鏈表存儲）

希爾排序（基于逐趟縮小增量）8.10.2.1直接插入排序（增量法）利用“順序查找”實(shí)現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”[示例]{R(0)R(-4)R(8)R(1)R(-4)R(-6)}n=6

i=1[0]-481-4-6i=2[-40]81-4-6i=3[-408]1-4-6i=4[-4018]

-4-6i=5[-4-4018]-6i=6[-6-4-4018][算法思想]

每次使有序區(qū)增加一個(gè)記錄穩(wěn)定排序9.[算法步驟]

01i-1ii+1nr[0..n]

r[i]

(有序區(qū))(無序區(qū))循環(huán)(n-1)次，初值i=21)若r[i]<r[i-1]，則把第i個(gè)記錄取出保存在r[0]中，j=i-12)若r[0]<r[j]，則r[j]后移一位，j=j-1，轉(zhuǎn)2)；否則r[0]放在r[j+1]處，i=i+1，轉(zhuǎn)1)[算法描述]voidInsertSort

(SqList&L){for(i=2;i<L.length;i++)if(LT(L.r[i].key,L.r[[i-1].key)){L.r[0]=L.r[i];

L.r[i]=L.r[i-1];

for(j=i-2;LT(L.r[0].key,L.r[[j].key);j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}//InsertSortj10.[哨兵/監(jiān)視哨的作用]簡化邊界條件的測試，提高算法時(shí)間效率。[性能分析]最好情況(原始數(shù)據(jù)按正序即非遞減序排列)Cmin=Mmin=0最壞情況(原始數(shù)據(jù)按逆序即非遞增序排列)Cmax=Mmax=隨機(jī)情況

Cavg=(Cmin+Cmax)/2n2/4Mavgn2/4時(shí)間復(fù)雜度O(n2)

輔助空間復(fù)雜度O(1)11.[改進(jìn)措施]折半插入排序算法思想：將循環(huán)中每一次在區(qū)間[1,i-1]上為確定插入位置的順序查找操作改為折半查找操作。效果：減少關(guān)鍵字間的比較次數(shù)。2-路插入排序算法思想：設(shè)置與r同樣大小的輔助空間d，將r[1]賦值給d[1]，將d看作循環(huán)向量。對于r[i](2in)，若r[i]d[1]，則插入d[1]之后的有序序列中，反之則插入d[1]之前的有序序列中。(避免r[1]關(guān)鍵字最小/最大)

效果：減少記錄的移動(dòng)次數(shù)。表插入排序算法思想：構(gòu)造靜態(tài)鏈表，用改變指針來代替移動(dòng)記錄操作效果：減少記錄的移動(dòng)次數(shù)。dr[1]12.10.2.2希爾排序(漸減/縮小增量排序)[算法思想的出發(fā)點(diǎn)]直接插入排序在待排序列的關(guān)鍵字基本有序時(shí)，效率較高在待排序的記錄個(gè)數(shù)較少時(shí)，效率較高[算法思想]

先選定一個(gè)記錄下標(biāo)的增量d，將整個(gè)記錄序列按增量d從第一個(gè)記錄開始劃分為若干組，對每組使用直接插入排序的方法；然后減小增量d，不斷重復(fù)上述過程，如此下去，直到d=1(此時(shí)整個(gè)序列是一組)。對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。13.[示例]<初態(tài)>46

82

52

406731

40

73

5376d1=53146

4082

5273

40536776不穩(wěn)定排序<第一趟結(jié)果>31

40

5240

674682

735376d2=331407682

406773465253<第二趟結(jié)果>31404640675276735382d3=1<第三趟結(jié)果>3140404652536773768214.voidShellSort(SqList&L,intdlta[],intt)//按增量序列dlta[0..t-1]對順序表L作希爾排序{for(k=0;k<t;k++){dk=dlta(k);//增量序列函數(shù)，如:……15,7,3,1

for(i=dk+1;i<=L.length;i++)if(L.r[i].key<L.r[i-dk].key){L.r[0]=L.r[i];//r[i]需插入時(shí)，暫存在r[0]for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)L.r[j+dk]=L.r[j];r[j+dk]=r[0];}}//ShellSort[算法描述]15.[性能分析]時(shí)間復(fù)雜度是n和d的函數(shù)如何選擇最佳d序列，目前尚未解決最后一個(gè)增量值必須為1避免增量序列中的值（尤其是相鄰的值）有公因子實(shí)驗(yàn)結(jié)果：當(dāng)n較大時(shí)，比較和移動(dòng)次數(shù)約在n1.25到1.6n1.25。就地排序16.10.3交換排序10.3.1起泡排序(冒泡排序)[算法思想]

將兩個(gè)相鄰記錄的關(guān)鍵字進(jìn)行比較，若為逆序則交換兩者位置，小者往上浮，大者往下沉。[算法步驟]

記錄1和2、2和3、……、(n-1)和n的關(guān)鍵字比較(交換)；記錄1和2、2和3、……、(n-2)和(n-1)的關(guān)鍵字比較(交換)；

……

直到某一趟不出現(xiàn)交換操作為止。17.[示例]<初態(tài)><第一趟><第二趟><第三趟><第四趟>0-4-4-6-6

-40-6-4-48-6-4

-4

-4

-6-40

00

-41

11118888sortedFFFT穩(wěn)定排序18.voidBubbleSort(SqList&L){sorted=FALSE;n=L.length;for(i=0;i<n-1&&(!sorted);i++)sorted=TRUE;for(j=1;j<n-i;j++) if(L.r[j].key>L.r[j+1].key){L.r[j]←→L.r[j+1];sorted=FALSE;}}}//BubbleSort[算法描述]19.[性能分析]最好情況(原始數(shù)據(jù)按正序即非遞減序排列)Cmin=n-1Mmin=0最壞情況(原始數(shù)據(jù)按逆序即非遞增序排列)Cmax=Mmax=時(shí)間復(fù)雜度O(n2)

輔助空間復(fù)雜度O(1)[算法的改進(jìn)]每趟排序中，記錄最后一次發(fā)生交換的位置雙向交替掃描，下上，最輕升頂；上下，最重沉底20.10.3.2快速排序(分劃交換排序/分治法)[分治算法原理]1)分解：將原問題分解為若干子問題2)求解：遞歸地解各子問題，若子問題的規(guī)模足夠小，則直接求解3)組合：將各子問題的解組合成原問題的解[快速排序算法思想]

指定樞軸/支點(diǎn)/基準(zhǔn)記錄r[p](通常為第一個(gè)記錄)，通過一趟排序?qū)⑵浞旁谡_的位置上，它把待排記錄分割為獨(dú)立的兩部分，使得

左邊記錄的關(guān)鍵字r[p].key右邊記錄的關(guān)鍵字對左右兩部分記錄序列重復(fù)上述過程，依次類推，直到子序列中只剩下一個(gè)記錄或不含記錄為止。(可以用遞歸方法實(shí)現(xiàn))21.[一趟快速排序示例]<初態(tài)>{(49)38659776132749}ij273865977613()49ij2738()9776136549ij2738139776()6549ij273813()76976549ij<一趟結(jié)束>{273813}49{76976549}(i=j)0123456784922.[算法描述]voidQuickSort(SqList&L)//對順序表L進(jìn)行快速排序{ QSort(L,1,L.length);}//QuickSortvoidQSort

(SqList&L，intlow,inthigh)//對順序表L中的子序列L.r[low..high]進(jìn)行快速排序{if(low<high){pivotloc=Partition(L,low,high);

Qsort(L,low,pivotloc-1);

Qsort(L,pivotloc+1,high)}}//QSort23.[算法描述]（續(xù)）intPartition(SqList&L，intlow,inthigh){L.r[0]=L.r[low];pivotkey=L.r[low].key;while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];}L.r[low]=L.r[0];returnlow;}//Partition24.[性能分析]

最壞情況(原始數(shù)據(jù)正/逆序排列)Cmax=(n-1)+(n-2)+……+1=n(n-1)/2MmaxCmin

O(n2)最好情況：每次劃分的結(jié)果是基準(zhǔn)的左、右兩個(gè)無序子區(qū)間的長度大致相等

CminO(nlgn)MminCmin

O(nlog2n)平均時(shí)間性能Tavg(n)=knln(n)k：某個(gè)常數(shù)；n：待排序序列中記錄個(gè)數(shù)就平均時(shí)間而言，快速排序是目前被認(rèn)為最好的一種內(nèi)部排序方法。輔助空間復(fù)雜度最好情況O(log2n)

最壞情況O(n)LL/2L/2L…………11125.[算法的改進(jìn)]

合理選擇樞軸記錄可改善性能。例如，三者取中隨機(jī)產(chǎn)生[算法的穩(wěn)定性]

是非穩(wěn)定排序反例[2，2，1]：{12}2

{}思考：在鏈表存儲結(jié)構(gòu)上如何實(shí)現(xiàn)快速排序？26.10.4選擇排序10.4.1簡單選擇排序(直接選擇排序)[算法思想]

每次從待排序列中選出關(guān)鍵字最小記錄作為有序序列中最后一個(gè)記錄，直至最后一個(gè)記錄為止。[示例]

（n=8）<初態(tài)>4938659776491327<第1趟>13

38659776494927<第2趟>1327659776494938<第3趟>1327389776494965<第4趟>1327384976974965<第5趟>1327384949977665<第6趟>1327384949657697<第7趟>1327384949657697

（每趟排序使有序區(qū)增加一個(gè)記錄）不穩(wěn)定排序27.[算法描述]voidSelectSort(SqList&L){for(i=1;i<L.length;i++){j=i;for(k=i+1;k<=L.length;k++)if(L.r[j].key>L.r[k].key)j=k;if(i!=j)L.r[i]←→L.r[j];}}//SelectSort[性能分析]總的比較次數(shù)與記錄排列的初始狀態(tài)無關(guān)

C=(n-1)+(n-2)+...+2+1=n(n-1)/2移動(dòng)次數(shù)初始記錄逆序時(shí)：Mmax=3(n-1)

初始記錄正序時(shí)：Mmin=0平均時(shí)間復(fù)雜度O(n2)

輔助空間復(fù)雜度O(1)簡單選擇排序記錄移動(dòng)次數(shù)少28.10.4.2樹形選擇排序(錦標(biāo)賽排序)[算法思想]

錦標(biāo)賽名次產(chǎn)生過程。較簡單選擇排序減少“比較”次數(shù)。[示例]23234038234046382338

40[性能]

除第一次外，每次都走了樹的一條分支，故其時(shí)間復(fù)雜度為O(nlog2n)。[缺陷]

輔助空間較多；需與“最大值”進(jìn)行多余的比較233838383846383838

464040

4646

穩(wěn)定排序29.10.4.3堆排序[特點(diǎn)]較直接選擇排序減少重復(fù)比較；較樹形選擇排序減少輔助存儲空間(僅需一個(gè))[(二叉)堆的定義]n個(gè)關(guān)鍵字的序列（k1,k2,...,kn）當(dāng)且僅當(dāng)滿足下列條件之一：

(1)KiK2i且KiK2i+1小根堆

(2)KiK2i且KiK2i+1

大根堆

則稱該序列為一個(gè)堆。[堆對應(yīng)于完全二叉樹的存儲結(jié)構(gòu)]

(i=1,2,...,n/2)9627911388396832738119123456大根堆30.[堆排序基本思想]將初始文件R[1..n]建成一個(gè)大根堆；第1趟：將關(guān)鍵字最大的記錄(堆頂)R[1]與無序區(qū)的最后一個(gè)記錄R[n]交換；再將新的無序區(qū)R[1..n-1]調(diào)整為堆；第2趟：將R[1]與R[n-1]交換；再將新的無序區(qū)R[1..n-2]調(diào)整為堆；......第i趟：將R[1]與R[n-i+1]交換；再將新的無序區(qū)

R[1..n-i]調(diào)整為堆；......直到執(zhí)行完第(n-1)趟為止。………………R[1]31.[堆排序需解決的兩個(gè)問題]如何由一個(gè)無序序列建成一個(gè)堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？1）調(diào)整堆的方法——篩選976576271349503838657627134950977665502713493897堆堆堆堆27655076134938976527507613493897堆32.2）將初始記錄序列R[1..n]建成大根堆

依次把以i=n/2，n/2-1，n/2-2，......，1為根的子樹調(diào)整為堆，則完成了整個(gè)建堆的過程。

（49，38，13，50，76，65，27，97）4913382765765097491338276576975049653827137697504965972713765038976576271349503833.[算法描述]voidHeapSort(HeapType&H){for(i=H.length/2;i>0;i--)HeapAdjust(H,i,H.length);for(i=H.length;i>1;i--){H.r[1]←→H.r[i];

HeapAdjust(H,1,i-1);}}//HeapSorttypedefSqListHeapType;voidHeapAdjust(HeapType&H,ints,intm){rc=H.r[s];for(j=2*s;j<=m;j*=2){if(j<m&&H.r[j].key<H.r[j+1].key)j++;if(rc.key>H.r[j].key)break;H.r[s]=H.r[j];s=j;}H.r[s]=rc;}//HeapAdjust0

1

2

3

nrcsj。。。。。。。。。。m34.[算法分析]最壞情況O(nlog2n)建初始堆時(shí)，比較次數(shù)4n反復(fù)調(diào)整堆時(shí)，比較次數(shù)<2nlog2n實(shí)驗(yàn)表明：平均性能接近于最壞性能O(nlog2n)輔助空間復(fù)雜度：O(1)不穩(wěn)定排序?qū)τ涗洈?shù)較大的文件很有效35.10.5歸并排序(合并排序)

[歸并的概念]

指將兩個(gè)或兩個(gè)以上的同序序列歸并成一個(gè)序列的操作。10.5.1兩路歸并排序[算法思想]第1趟：將待排序列R[1..n]看作n個(gè)長度為1的有序子序列，兩兩歸并，得到n/2個(gè)長度為2的有序子序列(或最后一個(gè)子序列長度為1)；第2趟：將上述n/2個(gè)有序子序列兩兩歸并；...…直到合并成一個(gè)序列為止。36.[示例]

(n=7)<初態(tài)>(49)(38)(65)(97)(76)(49)(13)<第1趟>(3849)(6597)(4976)(13)<第2趟>(38496597)(134976)<第3趟>(13384949657697)[性能分析]任何情況時(shí)間復(fù)雜度O(nlog2n)空間復(fù)雜度O(n)很少用于內(nèi)部排序穩(wěn)定排序37.[遞歸算法描述]VoidMSort(RedTypeSR[],RedType&TR1[],ints,intt)//將SR[s..t]歸并排序?yàn)門R1[s..t]{if(s==t)TR1[s]=SR[s];else{m=(S+t)/2;//將SR[s..t]分為SR[s..m]和SR[m+1..t]

Msort(SR,TR2,s,m);//將SR[s..m]歸并為有序的TR2[s..m]

Msort(SR,TR2,m+1,t);//將SR[m+1..t]歸并為有序的TR2[m+1..t]Merge(TR2,TR1,s,m,t);//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]}}//MSortVoidMergeSort(SqList&L) //將順序表L進(jìn)行歸并排序{Msort(L.r,L.r,1,L.length)；}//MergeSortVoidMerge(RedTypeSR[],RedType&TR[],inti,intm,intn)//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]{for(j=m+1,k=i;i<=m&&j<=n;k++){if(SR[i].key<=SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];}if(i<=m)TR[k..n]=SR[i..m];if(j<=n)TR[k..n]=SR[j..n];}//MergeSRTRimnjk38.[非遞歸算法描述]

voidMergeSort(SqList&L){len=1;n=L.Length;while(len<n){s1=1;while(s1+len<=n){t1=s1+len-1;t2=t1+len;if(t2>n)t2=n;

Merge(L.r,TR,s1,t1,t2);s1=t2+1;}for(i=1;i<s1;i++)L.r[i]=TR[i];len=len*2;}}//MergeSortrTRs1t1s2t2lenlen39.10.5.2自然兩路歸并排序[特點(diǎn)]

以游程(自然的有序段)作為子序列進(jìn)行歸并，可以比直接兩路歸并更有效。[示例]

5038751261908170897275653426154512503512612758979081706535124261548787154426503512512653908897275170616187154170275426503512512653897908不穩(wěn)定排序40.10.6基數(shù)排序(分配排序)[特點(diǎn)]

通過“分配”和“收集”過程來實(shí)現(xiàn)排序，時(shí)間復(fù)雜度可以突破基于關(guān)鍵字比較一類方法的下界O(nlgn)，達(dá)到O(n)。[方法]

借助多關(guān)鍵字排序的思想對單關(guān)鍵字排序[多關(guān)鍵字排序示例]

撲克牌排序(點(diǎn)數(shù)+花色)

雙關(guān)鍵字花色：<<<

點(diǎn)數(shù)：2<3<…<Q<K<A“花色”地位高于“面值”

最高位優(yōu)先法（MSD法,MostSignificantDigitfirst）按花色分成4堆；

對每一堆：按面值分堆；從小到大排序；按花色從小到大排序41.最低位優(yōu)先法（LSD法,LeastSignificantDigitfirst）按點(diǎn)數(shù)大小分成13堆；按點(diǎn)數(shù)從小到大收集起來；再按花色分成四堆；按花色從小到大收集起來[MSD與LSD不同特點(diǎn)]按MSD排序，必須將序列逐層分割成若干子序列，然后對各子序列分別排序按LSD排序，不必分成子序列，對每個(gè)關(guān)鍵字都是整個(gè)序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實(shí)現(xiàn)排序42.[基數(shù)排序算法思想]

借鑒LSD法設(shè)參加排序的序列為K={K1,K2,...,Kn}，其中Ki是d位rd進(jìn)制的數(shù)，rd稱為基數(shù)；

d由所有元素中最長的一個(gè)元素的位數(shù)計(jì)量，

Ki=Ki0Ki1...Kid-1

從低位到高位依次對Kj(j=d-1,d-2,...,0)根據(jù)基數(shù)分配，再按基數(shù)遞增序收集，則可得有序序列。[例]

(1)

K={362107248385007505147368

0008}rd=10,d=4(2)K={ZhangWangLiZhao}rd=27,d=5高低43.[鏈?zhǔn)交鶖?shù)排序示例]

{477241467536381

5}

第1趟：分配[0][1][2][3][4][5][6][7][8][9]2413635477815467

收集{2418136355477467}第2趟：分配[0][1][2][3][4][5][6][7][8][9]524136347781

5467

收集{5524136346747781}第3趟：分配[0][1][2][3][4][5][6][7][8][9]5241363467

547781

收集{5581241363467477}rd=10d=3穩(wěn)定排序44.[數(shù)據(jù)結(jié)構(gòu)]主：靜態(tài)鏈表r[0..n]數(shù)據(jù)域(key+otheritem)：記錄指針域(next)：下一個(gè)記錄的序號輔：f[0..rd-1]各鏈?zhǔn)疥?duì)列頭指針

e[0..rd-1]各鏈?zhǔn)疥?duì)列尾指針[數(shù)據(jù)結(jié)構(gòu)定義]

keyotheritemnext012n0rd-1r[0..n]fe0001203#defineMAX_NUM_OF_KEY8//可容納的最多子關(guān)鍵字個(gè)數(shù)#defineRADIX10//關(guān)鍵字的基數(shù)rd#defineMAX_SPACE10000//記錄空間可容納的最多記錄數(shù)typedefstruct{KeysTypekey[MAX_NUM_OF_KEY];InfoTypeotheritem;intnext;}SLCell;typedefstruct{SLCellr[MAX_SPACE];//r[0]為頭結(jié)點(diǎn)intkeynum;//實(shí)際劃分的關(guān)鍵字位數(shù)dintrecnum;//實(shí)際記錄數(shù)}SLList;TypedefintArrType[RADIX];45.[算法描述]

主過程RadixSort分配過程：Distribute收集過程：CollectvoidRadixSort(SLList&L){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++){Distribute(L.r,i,f,e);Collect(L.r,i,f,e);}}//RadixSort46.voidDistribute(SLCell&r,inti,ArrType&f,ArrType&e){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]);//求記錄中關(guān)鍵字的第i位的隊(duì)列編號if(!f[j])f[j]=p;elser[e[j]].next=p;e[j]=p;}}//DistributevoidCollect(SLCell&r,inti,ArrType&f,ArrType&e){for(j=0;!f[j];j++);//找第一個(gè)非空子隊(duì)列r[0].next=f[j];t=e[j];while(j<RADIX){for(;j<RADIX-1&&!f[j];j++);//找下一個(gè)非空子隊(duì)列if(f[j]){r[t].next=f[j];t=e[j];}//鏈接}r[t].next=0;}//Collect47.[鏈?zhǔn)交鶖?shù)排序的性能分析]

設(shè)記錄數(shù)為n，關(guān)鍵字位數(shù)為d,基數(shù)為rd每一趟：分配O(n)收集O(rd)d趟總計(jì)：O(d(n+rd))O(n)通常d,rd均為常數(shù)輔助空間n個(gè)指針域（游標(biāo)）空間隊(duì)頭指針數(shù)組f[0..rd-1]和隊(duì)尾指針數(shù)組e[0..rd-1]

輔助空間復(fù)雜度：O(rd+n)48.