數(shù)據(jù)結(jié)構(gòu)與算法分析：第七章內(nèi)排序

第8章內(nèi)排序數(shù)據(jù)結(jié)構(gòu)與算法分析1內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限2內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限3排序Sorting每個(gè)記錄內(nèi)都有一個(gè)關(guān)鍵碼域,這個(gè)域的值正是比較器所用到的.線性順序:比較.給定一組記錄r1,r2,…,rn,其關(guān)鍵碼分別為k1,k2,…,kn,排序問題就是要將這些記錄排成順序?yàn)閞s1,rs2,…,rsn的一個(gè)序列,滿足條件ks1ks2

…

ksn.4排序的穩(wěn)定性在待排記錄序列中，任何兩個(gè)關(guān)鍵字相同的記錄，用某種排序方法排序后相對(duì)位置不變，則稱這種排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的

例設(shè)49,38,65,97,76,13,27,49是待排序列排序后:13,27,38,49,49,65,76,97——穩(wěn)定排序后:13,27,38,49,49,65,76,97——不穩(wěn)定5穩(wěn)定排序的應(yīng)用例股票交易系統(tǒng)考慮一種股票交易(清華紫光)1）顧客輸入：股東帳號(hào)、股票代碼、申購(gòu)價(jià)格、數(shù)量，股票交易系統(tǒng)將用戶申購(gòu)請(qǐng)求插入申購(gòu)隊(duì)列隊(duì)尾；

2）股票交易系統(tǒng)按如下原則交易：

A）申購(gòu)價(jià)高者先成交 B）申購(gòu)價(jià)相同者按申購(gòu)時(shí)間先后順序成交申購(gòu)隊(duì)列：用線性表表示交易前：將申購(gòu)隊(duì)列按申購(gòu)價(jià)排序，顯然為滿足交易原則B），要求排序方法是穩(wěn)定的申購(gòu)隊(duì)列((09,10),(06,10.5),(033,9.8),(051,10))排序后：((06,10.5),(09,10),(051,10),(033,9.8))6排序方法分類按記錄的存放位置分類有內(nèi)排序：待排記錄放在內(nèi)存外排序：待排記錄放在外存（數(shù)量大）性能分類簡(jiǎn)單但相對(duì)較慢的排序算法，(n2)先進(jìn)的排序算法，(nlogn)一種特殊的方法，(n)待排序的記錄序列通常有下列三種存貯方法順序表靜態(tài)鏈表：在排序過程，只需修改指針，不需要移動(dòng)記錄待排記錄本身放在連續(xù)單元中，同時(shí)另建一索引表用于存放各記錄存貯位置；排序時(shí)不移動(dòng)記錄本身，而移動(dòng)索引表中的記錄“地址”，在排序結(jié)束后再按地址調(diào)整記錄的存貯位置7排序算法性能分析分析排序算法時(shí),需測(cè)量的代價(jià):關(guān)鍵碼比較的次數(shù)記錄交換的次數(shù)8約定本章中排序算法的輸入都是存儲(chǔ)在數(shù)組中的一組記錄將按關(guān)鍵字遞增的順序排序除非特別說明，本章中排序算法都適用于處理具有重復(fù)關(guān)鍵碼的問題為簡(jiǎn)潔起見，對(duì)待排記錄只寫出其關(guān)鍵字序列關(guān)鍵字都采用了整數(shù)，或使用比較器假設(shè)定義了一個(gè)swap函數(shù)9內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限10插入排序示例11插入排序基本思想輸入： 序列R1,R2,…,Rn

(凌亂無序)基本思想： 插入排序逐個(gè)處理待排序的記錄。每個(gè)新記錄與前面已排序的子序列進(jìn)行比較，將它插入到子序列中正確的位置。12插入排序算法template<classElem,classComp>voidinssort(ElemA[],intn){for(inti=1;i<n;i++)for(intj=i;(j>0)&&(Comp::lt(A[j],A[j-1]));j--)swap(A,j,j-1);}BestCase:WorstCase:AverageCase:13插入排序算法分析最佳情況數(shù)組中的關(guān)鍵碼按從小到大正序排列。沒有記錄移動(dòng)總的比較次數(shù)為n-1次最佳情況下插入排序的時(shí)間代價(jià)為(n)14插入排序算法分析最差情況數(shù)組中的原始數(shù)據(jù)是逆序的。每個(gè)記錄都必須移動(dòng)到數(shù)組的頂端比較的次數(shù)為i交換的次數(shù)為i最差情況下總的比較次數(shù)為=

(n2)15插入排序算法分析－比較次數(shù)平均情況當(dāng)處理到第i個(gè)記錄時(shí)，內(nèi)層for循環(huán)的執(zhí)行次數(shù)依賴于該記錄“無序”的程度逆置的數(shù)目（即數(shù)組中位于一個(gè)給定值之前，并比它大的值的數(shù)目）將決定比較及交換的次數(shù)平均情況下，在數(shù)組的前i-1個(gè)記錄中有一半關(guān)鍵碼比第i個(gè)記錄的關(guān)鍵碼值大平均的時(shí)間代價(jià)是最差情況的一半，為i=

(n2)16平均情況每執(zhí)行一次內(nèi)層for循環(huán)就要比較一次并交換一次每一輪的最后一次比較找到應(yīng)該插入的位置，此時(shí)沒有發(fā)生交換總排序次數(shù)是總比較次數(shù)減去n-1插入排序算法分析－交換次數(shù)最佳情況下為0，在最差及平均情況下為

(n2)17例子例:初始關(guān)鍵字:[49][38659776132749]i=1:[3849]659776132749]i=2:[384965]9776132749]i=3:[38496597]76132749]i=5:[133849657697]2749]i=6:[13273849657697]49]i=7:[1327384949657697]i=4:[3849657697]132749]無序源記錄文件有序函數(shù)18插入排序算法的特點(diǎn)特點(diǎn)

1)算法簡(jiǎn)單

2)時(shí)間復(fù)雜度為（n2）3)初始序列基本（正向）有序時(shí)，時(shí)間復(fù)雜度為(n)4)穩(wěn)定排序該方法適用于記錄基本（正向）有序或n較少的情況19內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限20冒泡排序BubbleSort21冒泡排序基本思想輸入： 序列R1,R2,…,Rn

(凌亂無序)基本思想：

比較并交換相鄰元素對(duì),直到所有元素都被放到正確的地方為止22冒泡排序代碼template<classElem,classComp>voidbubsort(ElemA[],intn){for(inti=0;i<n-1;i++)for(intj=n-1;j>i;j--)if(Comp::lt(A[j],A[j-1]))swap(A,j,j-1);}BestCase:WorstCase:AverageCase:23冒泡排序算法分析不考慮數(shù)組中結(jié)點(diǎn)的組合情況，內(nèi)層for循環(huán)比較的次數(shù)總會(huì)是i，因此時(shí)間代價(jià)為(n2)冒泡排序的最佳、平均和最差情況的運(yùn)行時(shí)間幾乎是相同的假定交換的概率是平均情況下比較次數(shù)的一半，代價(jià)為(n2)24例:[4938659776132749]一趟:[38496576132749]97二趟:[384965132749]7697三趟:[3849132749]657697四趟:[38132749]49657697五趟:[132738]4949657697六趟:[1327]384949657697七趟:[13]27384949657697例子25冒泡排序特點(diǎn)沒有什么特殊的價(jià)值一種相對(duì)較慢的排序、沒有插入排序易懂，而且沒有較好的最佳情況執(zhí)行時(shí)間冒泡排序?yàn)楹竺鎸⒁懻摰囊环N更好的排序提供了基礎(chǔ)26內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限27選擇排序SelectionSort28選擇排序的基本思想對(duì)于n個(gè)記錄的數(shù)組，共進(jìn)行n1趟排序。每一趟在ni+1個(gè)(i=1,2,…,n1)記錄中通過ni次關(guān)鍵字的比較選出關(guān)鍵碼最小的記錄和第i個(gè)記錄進(jìn)行交換29選擇排序的代碼template<classElem,classComp>voidselsort(ElemA[],intn){for(inti=0;i<n-1;i++){

intlowindex=i;//Rememberitsindexfor(intj=n-1;j>i;j--)//Findleastif(Comp::lt(A[j],A[lowindex]))

lowindex=j;//Putitinplaceswap(A,i,lowindex);}}BestCase:WorstCase:AverageCase:30選擇排序算法分析實(shí)質(zhì)是延遲交換的冒泡排序比較的次數(shù)仍為(n2)但是交換的次數(shù)要比冒泡法少得多最佳情況n-1次交換（重寫）最差情況n-1次交換平均情況(n)3113 [38 65 97 76 49 27 49]一趟ik例：[49 38 65 97 76 13 27 49]初始關(guān)鍵字ik13 27[65 97 76 49 38 49]二趟13 2738[97 76 49 65 49]ik三趟13 273849[76 97 65 49]四趟13 27384949[97 65 76]五趟13 27384949 65[97 76]六趟13 27384949 6576 97 七趟例子32選擇排序的特點(diǎn)對(duì)于處理那些作一次交換花費(fèi)代價(jià)（時(shí)間）較多的問題，選擇排序是很有效的33交換指向記錄的指針34交換排序算法的時(shí)間代價(jià)InsertionBubbleSelectionComparisons:BestCase(n)Q(n2)Q(n2)AverageCaseQ(n2)Q(n2)Q(n2)WorstCaseQ(n2)Q(n2)Q(n2)SwapsBestCase00(n)AverageCaseQ(n2)Q(n2)(n)WorstCaseQ(n2)Q(n2)(n)35交換排序ExchangeSorting迄今為止介紹的排序算法依靠交換（比較）相鄰的元素.交換排序的最小時(shí)間代價(jià)（平均來說）到底是多少呢?每對(duì)元素平均需要n(n-1)/2交換.36內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限37Shell排序38Shell排序的基本思想插入排序算法簡(jiǎn)單，在n值較小時(shí)，效率比較高，在n值很大時(shí)，若序列按關(guān)鍵碼基本有序，效率依然較高，其時(shí)間效率可提高到(n)。shell排序即是從這兩點(diǎn)出發(fā)，給出插入排序的改進(jìn)方法基本思想 先將整個(gè)待排記錄序列分割成若干個(gè)較小的子序列，對(duì)子序列分別進(jìn)行插入排序；待整個(gè)序列中的記錄“基本有序”時(shí),再對(duì)全體記錄進(jìn)行一次插入排序39Shell排序代碼//ModifiedversionofInsertionSorttemplate<classElem,classComp>voidinssort2(ElemA[],intn,intincr){for(inti=incr;i<n;i+=incr)for(intj=i;(j>=incr)&&(Comp::lt(A[j],A[j-incr]));j-=incr)swap(A,j,j-incr);}template<classElem,classComp>voidshellsort(ElemA[],intn){//Shellsort

for(inti=n/2;i>2;i/=2)//Foreachincr

for(intj=0;j<i;j++)//Sortsublists

inssort2<Elem,Comp>(&A[j],n-j,i);inssort2<Elem,Comp>(A,n,1);}40Shell排序的分析與特點(diǎn)性能分析分析Shell排序是很困難的，因此我們必須不加證明地承認(rèn)Shell排序的平均運(yùn)行時(shí)間是Θ(n1.5)(對(duì)于選擇“增量每次除以3”遞減)。選取其他增量序列可以減少這個(gè)上界。因此，Shell排序確實(shí)比插入排序或在第7.2節(jié)中講到的任何一種運(yùn)行時(shí)間為Θ(n2)的排序算法要快有人在大量實(shí)驗(yàn)的基礎(chǔ)上推出，當(dāng)N在某個(gè)特定范圍內(nèi)，所需比較和移動(dòng)次數(shù)約為n1.3當(dāng)n時(shí)，可減少到n(log2n)2增量序列可以有各種取法，但需注意：應(yīng)使增量序列中的值沒有除1之外的公因子，并且最后一個(gè)增量值必須等于141待排序列為39，80，76，41，13，29，50，78，30，11，100，7，41，86步長(zhǎng)因子分別取5、3、1，則排序過程如下：p=5 3980764113295078301110074186子序列分別為{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}

第一趟排序結(jié)果：29

7

41

301139

50

76

4113100

80

78

86

例子（續(xù)）p=3 2974130113950764113100807886子序列分別為{29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}。第二趟排序結(jié)果：13

73929

11

41

30

764150

868078

100例子（續(xù)）43p=1 1373929114130764150868078100

此時(shí)，序列基本“有序”，對(duì)其進(jìn)行直接插入排序，得到最終結(jié)果：7111329303941415076788086100

例子（續(xù)）44Shell排序的特點(diǎn)特點(diǎn)

1）時(shí)間復(fù)雜度，取決于增量序列的選擇，選擇的好，效率優(yōu)于插入排序

2）不穩(wěn)定排序方法

3）適用于n較大情況（中等大小規(guī)模）45內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限46快速排序Quicksort的基本思想1）選定一記錄R，將所有其他記錄關(guān)鍵字k’與記錄R的關(guān)鍵字k比較,

若

k’<k則將記錄換至R之前,若k’

>k則將記錄換至R之后2）繼續(xù)對(duì)R前后兩部分記錄進(jìn)行快速排序，直至排序范圍為1我們將待排序列按關(guān)鍵碼作為軸值（pivot）分成兩部分的過程，稱為一次劃分（一趟排序）47快速排序Quicksort代碼template<classElem,classComp>voidqsort(ElemA[],inti,intj){if(j<=i)return;//Listtoosmall

intpivotindex=findpivot(A,i,j);swap(A,pivotindex,j);//Putpivotatend//kwillbefirstpositiononrightside

intk=partition<Elem,Comp>(A,i-1,j,A[j]);swap(A,k,j);//Putpivotinplace

qsort<Elem,Comp>(A,i,k-1);

qsort<Elem,Comp>(A,k+1,j);}template<classElem>intfindpivot(ElemA[],inti,intj){return(i+j)/2;}48QuicksortPartitiontemplate<classElem,classComp>intpartition(ElemA[],intl,intr,

Elem&pivot){

do{//Movetheboundsinuntiltheymeetwhile(Comp::lt(A[++l],pivot));while((r!=0)&&Comp::gt(A[--r],pivot));swap(A,l,r);//Swapout-of-placevalues}while(l<r);//Stopwhentheycross

swap(A,l,r);//Reverselastswapreturnl;//Returnfirstposonright}ThecostforpartitionisQ(n).49PartitionExamplepivot50QuicksortExample51CostofQuicksort最佳情況:每次將數(shù)列分割為等長(zhǎng)的兩部分.最差情況:糟糕的分割.平均情況:T(n)=n+1+1/(n-1)(T(k)+T(n-k))k=1n-152快速排序舉例初始關(guān)鍵字：{49，38，65，97，76，13，27，49}pivotkey49jji1次交換后：{27，38，65，97，76，13，，49}iji2次交換后：{27，38，，97，76，13，65，49}ijj3次交換后：{27，38，13，97，76，，65，49}iji4次交換后：{27，38，13，，76，97，65，49}jij一趟完成后：{27，38，13，49，76，97，65，49}53

273865977613

27

49ii例待排記錄

49

38659776132749

jj273865

97761365

49jj273813

4976976549jji被指定的關(guān)鍵字從后向前，將關(guān)鍵字與49比較，直至遇到小于49的關(guān)鍵字，前移從后向前，將關(guān)鍵字與49比較，直至遇到小于49的關(guān)鍵字，前移從前向后，將關(guān)鍵字與49比較，直至遇到大于49的關(guān)鍵字，后移從前向后，將關(guān)鍵字與49比較，直至遇到大于49的關(guān)鍵字，后移273813977613

6549ii從后向前，將關(guān)鍵字與49比較，直至遇到i=j,將49放至i處49一趟快速排序結(jié)束54[273813]49[769765

49]

[13

2738]49[49657697][13]

27[38]49[4965]76[97]1327384949657697兩趟快速排序結(jié)束三趟快速排序結(jié)束快速排序結(jié)束55快速排序的特點(diǎn)軸值的取值影響性能時(shí)間復(fù)雜度為（nlog2n）不穩(wěn)定快速排序的優(yōu)化:更好的軸值對(duì)于小的子數(shù)列采用更好的排序算法用棧來模擬遞歸調(diào)用56內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限57Mergesort的基本思想基本思想：

將兩個(gè)或多個(gè)有序表歸并成一個(gè)有序表2路歸并

1）設(shè)有n個(gè)待排記錄，初始時(shí)將它們分為n個(gè)長(zhǎng)度為1的有序子表；

2）

兩兩歸并相鄰有序子表，得到若干個(gè)長(zhǎng)度2為的有序子表；

3）

重復(fù)2）直至得到一個(gè)長(zhǎng)度為n的有序表58初始關(guān)鍵字序例：[49] [38] [65] [97] [76] [13] [27] [49][38,49] [65,97] [13,76] [27,49]第一趟[38,49,65,97] [13,27,49,76] 第二趟[13, 27, 38, 49, 49, 65, 76, 97]第三趟Mergesort舉例59歸并排序MergesortListmergesort(Listinlist){if(inlist.length()<=1)returninlist;Listl1=halfoftheitemsfrominlist;Listl2=otherhalfofitemsfrominlist;returnmerge(mergesort(l1),

mergesort(l2));}60歸并排序的實(shí)現(xiàn)template<classElem,classComp>voidmergesort(ElemA[],Elemtemp[],

intleft,intright){

intmid=(left+right)/2;if(left==right)return;

mergesort<Elem,Comp>(A,temp,left,mid);

mergesort<Elem,Comp>(A,temp,mid+1,right);

for(inti=left;i<=right;i++)//Copytemp[i]=A[i];

inti1=left;inti2=mid+1;for(intcurr=left;curr<=right;curr++){

if(i1==mid+1)//LeftexhaustedA[curr]=temp[i2++];elseif(i2>right)//RightexhaustedA[curr]=temp[i1++];

elseif(Comp::lt(temp[i1],temp[i2]))A[curr]=temp[i1++];elseA[curr]=temp[i2++];}}61優(yōu)化歸并排序template<classElem,classComp>voidmergesort(ElemA[],Elemtemp[],

intleft,intright){

if((right-left)<=THRESHOLD){

inssort<Elem,Comp>(&A[left],right-left+1);return;}

inti,j,k,mid=(left+right)/2;if(left==right)return;

mergesort<Elem,Comp>(A,temp,left,mid);

mergesort<Elem,Comp>(A,temp,mid+1,right);

for(i=mid;i>=left;i--)temp[i]=A[i];for(j=1;j<=right-mid;j++)

temp[right-j+1]=A[j+mid];

for(i=left,j=right,k=left;k<=right;k++)if(temp[i]<temp[j])A[k]=temp[i++];elseA[k]=temp[j--];}62MergesortCostMergesortcost:在最佳、平均、最差情況下，時(shí)間復(fù)雜度為(nlogn)當(dāng)輸入的待排序數(shù)據(jù)存儲(chǔ)在鏈表中時(shí)，歸并排序是一個(gè)很好的選擇.歸并排序需要兩倍的空間代價(jià).63歸并排序的特點(diǎn)需要輔助空間:(n)整個(gè)歸并需要[log2n]趟時(shí)間復(fù)雜度:(nlog2n)它是穩(wěn)定的排序方法思想可以推廣到“多-路歸并“64內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限65堆排序的基本思想基本思想：一個(gè)基于“最大值堆”(max-heap)排序算法的思想是很直接的。首先將數(shù)組轉(zhuǎn)化為一個(gè)滿足堆定義的序列。然后將堆頂?shù)淖畲笤厝〕?，再將剩下的?shù)排成堆，再取堆頂數(shù)值，…。如此下去，直到堆為空。到最后結(jié)束時(shí)，就排出了一個(gè)由小到大排列的數(shù)組。應(yīng)該注意的是每次應(yīng)將堆頂?shù)淖畲笤厝〕龇诺綌?shù)組的最后。66堆排序Heapsorttemplate<classElem,classComp>voidheapsort(ElemA[],intn){//HeapsortElemmval;

maxheap<Elem,Comp>H(A,n,n);for(inti=0;i<n;i++)//NowsortH.removemax(mval);//Putmaxatend}用最大值堆,到最后結(jié)束時(shí),就排出了一個(gè)由小到大排列的數(shù)組.67堆排序的性能分析堆排序的時(shí)間代價(jià):建堆要用(n)時(shí)間并且n次取堆的最大元素要用(logn) (2nlogn)尋找K個(gè)最大元素的時(shí)間代價(jià): (n+klogn)68HeapsortExample(1)69HeapsortExample(2)70堆排序的特點(diǎn)基于堆數(shù)據(jù)結(jié)構(gòu)，具有許多優(yōu)點(diǎn)：整棵樹是平衡的，而且它的數(shù)組實(shí)現(xiàn)方式對(duì)空間的利用率也很高，可以利用有效的建堆函數(shù)一次性把所有值裝入數(shù)組中。堆排序的最佳、平均、最差執(zhí)行時(shí)間均為(nlogn)更適合于外排序，處理那些數(shù)據(jù)集太大而不適合在內(nèi)存中排序的情況71內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限72分配排序Binsort

的基本思想一個(gè)簡(jiǎn)單、有效的排序:for(i=0;i<n;i++)B[A[i]]=A[i];關(guān)鍵碼用來確定一個(gè)記錄在排序中的最終位置擴(kuò)展分配排序算法的方法:允許關(guān)鍵碼重復(fù),也就是使數(shù)組B中的每個(gè)元素成為一個(gè)鏈表的頭結(jié)點(diǎn).允許關(guān)鍵碼范圍大于記錄數(shù)n.73分配排序的代碼template<classElem>voidbinsort(ElemA[],intn){List<Elem>B[MaxKeyValue];

Elemitem;for(i=0;i<n;i++)B[A[i]].append(A[i]);for(i=0;i<MaxKeyValue;i++)for(B[i].setStart();B[i].getValue(item);B[i].next())output(item);}74分配排序的性能分析時(shí)間代價(jià)：分配排序的時(shí)間代價(jià)初看起來是(n)。實(shí)際上時(shí)間代價(jià)為(n+MaxKeyValue)如果MaxKeyValue很大，那么這個(gè)算法的時(shí)間代價(jià)可能會(huì)為(n2)或更差。75基數(shù)排序RadixSort(1)76基數(shù)排序(2)template<classElem,classComp>voidradix(ElemA[],ElemB[],

intn,intk,intr,intcnt[]){//cnt[i]stores#ofrecordsinbin[i]

intj;for(inti=0,rtok=1;i<k;i++,rtok*=r){

for(j=0;j<r;j++)cnt[j]=0;

//Count#ofrecordsforeachbinfor(j=0;j<n;j++)cnt[(A[j]/rtok)%r]++;

//cnt[j]willbelastslotofbinj.for(j=1;j<r;j++)

cnt[j]=cnt[j-1]+cnt[j];

for(j=n-1;j>=0;j--)\B[--cnt[(A[j]/rtok)%r]]=A[j];for(j=0;j<n;j++)A[j]=B[j];}}77基數(shù)排序的例子78基數(shù)排序的時(shí)間代價(jià)Cost:Q(nk

+rk)n,k,和

r

之間有關(guān)系嗎?如果關(guān)鍵碼很小，那么基數(shù)排序的時(shí)間代價(jià)為Q(n).如果有n

個(gè)不同的關(guān)鍵碼,那么關(guān)鍵碼的長(zhǎng)度最小要大于logn.因而,在一般情況下基數(shù)排序的時(shí)間代價(jià)為Q(nlogn)79內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限80對(duì)各種排序算法的實(shí)驗(yàn)比較(1)81對(duì)各種排序算法的實(shí)驗(yàn)比較(2)82內(nèi)容排序術(shù)語與記號(hào)三種代價(jià)為(n2)的排序方法插入排序起泡排序選擇排序交換排序算法的時(shí)間代價(jià)Shell排序快速排序歸并排序堆排序分配排序和基數(shù)排序?qū)Ω鞣N排序算法的實(shí)驗(yàn)比較排序問題的下限83排序問題的下限我們想知道對(duì)所有可能的排序算法的時(shí)間代價(jià)的下限.排序算法的時(shí)間代價(jià)（在平均、最差情況）為O(n