數(shù)據(jù)結(jié)構(gòu)與算法分析課件第7章

數(shù)據(jù)結(jié)構(gòu)與算法分析

APracticalIntroductionto

DataStructuresandAlgorithmAnalysis

陳星

第三部分排序和檢索

第7章內(nèi)排序。第8章文件管理和外排序。第9章檢索。第10章索引技術(shù)。參考文獻(xiàn)：DataStructuresandAlgorithmAnalysis，C.A.Shaffer，電子工業(yè)出版社2002。數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），嚴(yán)蔚敏等，清華大學(xué)出版社1997。數(shù)據(jù)結(jié)構(gòu)—C++與面向?qū)ο蟮耐緩剑瑥埬诵?裘宗燕，高等教育出版社，2001。第7章內(nèi)排序在計(jì)算機(jī)主存內(nèi)對(duì)一組記錄進(jìn)行排序的標(biāo)準(zhǔn)算法。先介紹三種簡(jiǎn)單但較慢（Θ(n2)）的算法.1.插入排序。

2.起泡（冒泡排序）。

3.選擇排序。再介紹幾種復(fù)雜但較快的算法.

如Shell排序、快速排序、堆排序、歸并排序……排序操作中的基本運(yùn)算.1.比較2.交換排序方法插入類(lèi)排序選擇類(lèi)排序交換類(lèi)排序歸并排序插入排序希爾排序選擇排序堆排序快速排序分配類(lèi)排序：基數(shù)排序起泡排序排序技術(shù)種類(lèi)

按平均時(shí)間將排序分為四類(lèi)：（1）平方階(O(n2))排序

一般稱(chēng)為簡(jiǎn)單排序，例如直接插入、直接選擇和冒泡排序（2）線性對(duì)數(shù)階(O(nlogn))排序

如快速、堆和歸并排序；

（3）O(n1+￡)階排序

￡是介于0和1之間的常數(shù)，即0<￡<1，如希爾排序；

（4）線性階(O(n))排序

如分配和基數(shù)排序。排序技術(shù)種類(lèi)7.1排序術(shù)語(yǔ)及記號(hào)記錄之間通過(guò)一個(gè)比較器類(lèi)進(jìn)行比較。關(guān)鍵字是數(shù)據(jù)元素中的某個(gè)數(shù)據(jù)項(xiàng)。每個(gè)記錄中都有一個(gè)關(guān)鍵碼域(key)。比較器類(lèi)就是對(duì)該關(guān)鍵碼進(jìn)行比較;設(shè)對(duì)每一種記錄類(lèi)型都已定義Swap函數(shù)。思考?

有一堆雜亂無(wú)章的撲克牌,要求你從A到2的順序在手上理好。想一想你會(huì)采用什么方法理好牌？

7.2三種代價(jià)為Θ（n2）的排序方法算法簡(jiǎn)單、易懂、易于實(shí)現(xiàn)，但速度慢。7.2.1插入排序原理：將無(wú)序序列中的各元素依次與前面已排序的子序列進(jìn)行比較，將它插入到有序子序列中正確的位置。步驟：(1)首先將只含第1個(gè)元素的看成有序表。

(2)從線性表的第2個(gè)元素直到最后一個(gè)元素，依次將每個(gè)元素插入前面已經(jīng)有序的子表中。

(3)插入第j個(gè)元素的方法：將j放在變量T中，從有序子表（原線性表的前j-1個(gè)元素）的最后一個(gè)元素開(kāi)始，往前逐個(gè)與T比較，將大于T的元素?zé)o向后移一個(gè)位置，直到發(fā)現(xiàn)一個(gè)元素不大于T為止，將T插入到剛移出的空位置上，有序子表的長(zhǎng)度增加為j。插入排序比較1次交換1次

比較6次交換5次比較3次交換2次比較5次交換4次比較2次交換1次比較3次交換3次比較2次交換2次比較22次交換18次

插入排序的代價(jià)分析時(shí)間代價(jià)：最差情況下(原始紀(jì)錄全是逆序)：需要的比較次數(shù)：Θ(n2)

最佳情況下(原始紀(jì)錄已經(jīng)有序)：只需要n-1次比較；Θ(n)平均情況下：平均的時(shí)間代價(jià)是最差情況的一半，仍為Θ(n2)

空間代價(jià)：只需要一個(gè)暫存單元:Θ(1)

7.2.2起泡排序起泡排序的基本思想對(duì)所有相鄰記錄的關(guān)鍵字值進(jìn)行比效，如果是逆序（a[j]>a[j+1]），則將其交換，最終達(dá)到有序化。其處理過(guò)程為：對(duì)待排序的記錄序列從后向前（或從前向后）進(jìn)行掃描。依次比較相鄰記錄的關(guān)鍵字。交換比較中發(fā)現(xiàn)的逆序。因此關(guān)鍵字值小的記錄左移，關(guān)鍵字值大的記錄右移。一次掃描后，最小值移動(dòng)序列的頂端。做n-1遍從后向前（或從前向后）的掃描和逆序交換，或直到未發(fā)現(xiàn)逆序?yàn)橹?。起泡排序算法P144-145算法：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);}教科書(shū)上有錯(cuò)起泡排序代價(jià)分析比較次數(shù)：時(shí)間代價(jià)：Θ(n2)

需增加一個(gè)輔助單元進(jìn)行交換；空間代價(jià)：Θ(1)問(wèn)：如何改進(jìn)P144-145算法，減少起泡排序的比較和交換次數(shù)？7.2.3選擇排序基本思想：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面；然后對(duì)剩下的子表采用同樣的辦法，直到子表空為止。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);}}選擇排序和起泡排序的比較相同：表面上來(lái)看，一輪比較和交換后，最小值都放到了頂部；實(shí)質(zhì)上而言，選擇排序就是起泡排序；不同：選擇排序中最小元素一次交換到位；選擇排序的交換次數(shù)要比起泡排序少得多。起泡排序選擇排序選擇排序的時(shí)間代價(jià)選擇排序?qū)嵸|(zhì)上是起泡排序。選擇排序比較次數(shù)：Θ(n2)交換的次數(shù)比起泡排序少。因此，總的時(shí)間代價(jià)為Θ(n2)

。交換指針只交換指針，不移動(dòng)記錄本身，換來(lái)更高的效率,特別當(dāng)記錄很大的時(shí)候?？梢越档团判蛩惴ㄖ薪粨Q記錄所需要的時(shí)間。7.2.4交換排序算法的時(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)這些排序方法只比較相鄰的記錄。交換排序的最小時(shí)間代價(jià)(平均來(lái)說(shuō)):考慮一個(gè)有n個(gè)元素的序列L；L中有n(n-1)/2對(duì)不同的元素，每一對(duì)都可能是一個(gè)逆置；平均而言，一半正序，一半逆序(即每個(gè)序列有n(n-1)/4對(duì)逆置序列)；相鄰元素交換只能處理掉一個(gè)逆序；任何一種將比較限制在相鄰兩個(gè)元素之間進(jìn)行的交換算法的平均時(shí)間代價(jià)都是Q

(n2)。7.3Shell排序又稱(chēng)為縮小增量排序。基本思想：將整個(gè)線性表進(jìn)行分割，相隔某個(gè)增量h的元素構(gòu)成一個(gè)子表，對(duì)子表分別進(jìn)行插入排序，并逐漸減小增量h。最后當(dāng)h為1時(shí)，進(jìn)行一次插入排序，排序完成。希爾排序中，確定增量的大小是關(guān)鍵，但迄今未能得到解決。增量序列一般取ht=n/2k(k=1,2,3,…,[logn])，其中n為待排序列的長(zhǎng)度。

增量序列也可以以每次除以3來(lái)選?。ā?，121，40，13，4，1）希爾排序例子對(duì)關(guān)鍵字序列<07,19,24,13,31,08,82,18,44,63,05,29>

進(jìn)行希爾排序：該例中n=12，[logn]=[log12]=3；取增量系列為ht=12/2k(k=1,2,3)，即h1=12/2=6,h2=12/4=3,h3=12/8≈1071924133108821844630529h1=6071824130508821944633129結(jié)果h2=3071824130508821944633129結(jié)果070508131824631929823144h3=1結(jié)果070508131824631929823144050708131819242931446382Shell排序分析相當(dāng)困難，其效率依賴(lài)于增量序列的選取?？梢哉J(rèn)為Shell排序的平均時(shí)間代價(jià)為Θ(n1.5)希爾排序的空間代價(jià)為Θ(1)；同插入排序一樣，希爾排序也只需要一個(gè)記錄大小的輔助空間，用于暫存當(dāng)前待插入的記錄。當(dāng)n為中等規(guī)模大小時(shí)Shell排序是不錯(cuò)的選擇二叉查找樹(shù)中序遍歷有序序列888082688582

7571778880826885827177757.4快速排序分治法(divideandconquer)的思想：根結(jié)點(diǎn)將左、右子樹(shù)分開(kāi)，形成：左子樹(shù)<根右子樹(shù)二叉查找樹(shù)中序周游可得到有序序列，但弊端多：存儲(chǔ)占用大量結(jié)點(diǎn)空間、二叉樹(shù)不平衡時(shí)插入時(shí)間代價(jià)大。

快速排序以一種更有效的方法實(shí)現(xiàn)了“分治法”思想?；舅枷耄簭拇判蛐蛄兄羞x取一個(gè)元素，以該關(guān)鍵字值為軸值(pivot)，將待排序列分割為兩個(gè)子序列。軸值左側(cè)子序列中記錄都小于或等于軸值，右側(cè)子序列中記錄都大于或等于軸值。對(duì)子序列反復(fù)進(jìn)行分割，直到每個(gè)子序列的元素個(gè)數(shù)為1。整個(gè)線性表變成了有序表?？焖倥判蛞?0為軸值，一趟分割后結(jié)果以6為軸值，二趟分割后結(jié)果以73為軸值，二趟分割后結(jié)果關(guān)鍵技術(shù)：線性表的分割考慮：1、大（?。┑脑匾苿?dòng)到表的后（前）半部分。2、在原表中移動(dòng)，要考慮空位。具體步驟：附設(shè)兩個(gè)指針i和j，初值分別指向第一個(gè)記錄和最后一個(gè)記錄，將分割中項(xiàng)保存在臨時(shí)變量T中

，再將第一個(gè)記錄移動(dòng)分割中項(xiàng)的位置。首先從j所指位置起向前搜索，找到小于T的記錄移動(dòng)到i指向的位置，然后從i所指位置起向后搜索，找到大于T的記錄移動(dòng)到j(luò)指向的位置。重復(fù)這兩步直至i=j為止?？焖倥判虻牟襟E123 456783865764913273997

j

i分割中項(xiàng)T快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。整個(gè)表：從38，97和49中取出中項(xiàng)49作為分割中項(xiàng)T進(jìn)行快速排序123 456783865764913273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。將分割中項(xiàng)49保存在變量T中，將i所指向的記錄38移到分割中項(xiàng)位置。123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。首先指針j指向的記錄與T進(jìn)行比較。97>T，不交換。123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。指針j繼續(xù)向前掃描。39<T。123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。將39移動(dòng)i所指位置。123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。指針i開(kāi)始向后掃描，65>T。123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。將65移動(dòng)j所指位置，指針j開(kāi)始向前掃描。123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。27<T123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。將27移動(dòng)i所指位置，指針i開(kāi)始向后掃描。123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。76>T。123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。將76移動(dòng)j所指位置，指針j開(kāi)始掃描。123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。13<T。123 4567865763813273997123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。123 4567865763813273997將13移動(dòng)i所指位置，指針i開(kāi)始向后掃描。123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。123 456786576381327399738<T，不移動(dòng)，指針i繼續(xù)向后掃描。123 456783865764913273997

j

i分割中項(xiàng)T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進(jìn)行排序。123 4567865763813273997指針i和j相遇，將分割中項(xiàng)填入i和j所指位置。一趟分割結(jié)束。49快速排序的時(shí)間代價(jià)最佳情況:分割中項(xiàng)每次都為序列中記錄中間值，時(shí)間代價(jià)為Θ(nlogn);最環(huán)情況:分割中項(xiàng)每次都為序列中記錄的最大值或最小值，時(shí)間代價(jià)為Θ(n2);平均情況:平均時(shí)間代價(jià)Θ(nlogn)?？焖倥判虻目臻g代價(jià)快速排序每次只能對(duì)一個(gè)子表進(jìn)行排序，已劃分的另一個(gè)子表需要用棧來(lái)記錄下來(lái)，留待以后進(jìn)行排序。通常情況下空間代價(jià)(記錄子表的棧)為Θ(logn);最壞情況下空間代價(jià)為Θ(n);快速排序的優(yōu)化軸值pivot的選取第一個(gè)或最后一個(gè)記錄的關(guān)鍵字易退化為起泡算法。隨機(jī)選取值開(kāi)銷(xiāo)大數(shù)組中間點(diǎn)三者取中法首中尾三個(gè)記錄的中間值用于小子表的更佳算法劃分過(guò)程沒(méi)有必要?jiǎng)澐值阶颖黹L(zhǎng)度為1的情況，當(dāng)子表長(zhǎng)度小于某個(gè)值時(shí)，調(diào)用其他排序方法會(huì)快點(diǎn)。消除遞歸將遞歸改成非遞歸算法。速度加快。快速排序總結(jié)快速排序是一個(gè)遞歸的過(guò)程。在遞歸調(diào)用時(shí)需要占據(jù)一定的存儲(chǔ)空間用來(lái)保存每一層遞歸調(diào)用時(shí)的必要信息?？焖俚男逝c起泡排序相比有很大地提高。在起泡排序過(guò)程中是對(duì)相鄰兩個(gè)記錄進(jìn)行關(guān)鍵字比較和互換的，這樣每次交換記錄后，只能改變一對(duì)逆序記錄；而快速排序則從待排序記錄的兩端開(kāi)始進(jìn)行比較和交換，并逐漸向中間靠攏，每經(jīng)過(guò)一次交換，有可能改變幾對(duì)逆序記錄，從而加快了排序速度。到目前為止快速排序是平均速度最快的一種排序方法，歸并排序歸并是指將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。歸并排序的基本思想是將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長(zhǎng)度為1的有序序列，然后進(jìn)行兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序序列，再進(jìn)行兩兩歸并，得到n/4個(gè)長(zhǎng)度為4的有序序列，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。歸并排序的關(guān)鍵技術(shù)

－將兩個(gè)有序序列合并為一個(gè)有序序列方法：順序比較兩個(gè)表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 44913659776780AB0123 4567Cijk設(shè)置指針i,j,k分別指向A,B,C的第一個(gè)單元。歸并排序的關(guān)鍵技術(shù)

－將兩個(gè)有序序列合并為一個(gè)有序序列方法：設(shè)置指標(biāo)，順序比較兩個(gè)表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 44913659776780AB0123 4567Cijk7<13，移走7，指標(biāo)j和k后移一位。7歸并排序的關(guān)鍵技術(shù)

－將兩個(gè)有序序列合并為一個(gè)有序序列方法：設(shè)置指標(biāo)，順序比較兩個(gè)表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 449659776780AB0123 4567Cijk

13<76，移走13，指標(biāo)i和k后移一位。713歸并排序的關(guān)鍵技術(shù)

－將兩個(gè)有序序列合并為一個(gè)有序序列方法：設(shè)置指標(biāo)，順序比較兩個(gè)表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 4659776780AB0123 4567Cijk

49<76，移走13，指標(biāo)i和k后移一位。71349歸并排序的關(guān)鍵技術(shù)

－將兩個(gè)有序序列合并為一個(gè)有序序列方法：設(shè)置指標(biāo)，順序比較兩個(gè)表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 49776780AB0123 4567Cijk

65<76，移走65，指標(biāo)i和k后移一位。7134965歸并排序的關(guān)鍵技術(shù)

－將兩個(gè)有序序列合并為一個(gè)有序序列方法：設(shè)置指標(biāo)，順序比較兩個(gè)表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 497780AB0123 4567Cijk

76<97，移走76，指標(biāo)j和k后移一位。713496576歸并排序的關(guān)鍵技術(shù)

－將兩個(gè)有序序列合并為一個(gè)有序序列方法：設(shè)置指標(biāo)，順序比較兩個(gè)表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 4977AB0123 4567Cijk

80<97，移走80。71349657680歸并排序的關(guān)鍵技術(shù)

－將兩個(gè)有序序列合并為一個(gè)有序序列方法：設(shè)置指標(biāo)，順序比較兩個(gè)表中的元素，將值小者移入合并后的新表中，反復(fù)如此，直至所有元素都移入新表。0123 47AB0123 4567Cijk由于B已移空，停止比較，將A中剩余元素全部移到C中。7134965768097歸并排序的偽代碼Listmergesort(Listinlist){if(length(inlist)<=1)returninlist;Listl1=halfoftheitemsfrominlist;Listl2=otherhalfofitemsfrominlist;returnmerge(mergesort(l1),mergesort(l2));}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--];}用插入排序處理較短的數(shù)組兩個(gè)子數(shù)組相向插入，不需要檢查子序列是否處理完成歸并排序的優(yōu)化實(shí)現(xiàn)歸并排序的時(shí)/空間代價(jià)每次合并的時(shí)間代價(jià)為Θ(n)；從步長(zhǎng)為1開(kāi)始，整個(gè)合并完成需要logn次，總的時(shí)間代價(jià)為Θ(nlogn)。該時(shí)間代價(jià)并不依賴(lài)于待排數(shù)組中數(shù)值的相對(duì)順序，因此，它也就是歸并排序最佳、平均和最差的運(yùn)行時(shí)間。歸并排序同樣也適用于處理鏈?zhǔn)酱鎯?chǔ)的待排關(guān)鍵字序列.需要與待排序空間等量的輔助空間，空間代價(jià)為Θ(n).這是歸并排序的嚴(yán)重缺陷。7.4堆排序堆排序耗時(shí)：初始建堆時(shí)間＋(n-1)?調(diào)整一次堆的時(shí)間。最初，堆調(diào)整的路長(zhǎng)決定于樹(shù)的深度Θ(logn)，隨著選出結(jié)點(diǎn)的增多，待排的堆體積不斷減小，調(diào)整的路長(zhǎng)也不斷減小，所以調(diào)整的時(shí)間代價(jià)最多為Θ(logn)；即堆排序總的時(shí)間為Θ(n)+(n-1)?Θ(logn)，也就是說(shuō)堆排序的時(shí)間代價(jià)為Θ(nlogn)；堆排序需要一個(gè)輔助空間，即空間代價(jià)為Θ(1)。堆排序?qū)υ加涗浀呐帕袪顟B(tài)并不敏感，適用于規(guī)模(n)較大的待排序序列。分配排序一個(gè)簡(jiǎn)單、有效的排序:for(i=0;i<n;i++)B[A[i]]=A[i];關(guān)鍵碼B[]用來(lái)確定一個(gè)記錄在排序中的最終記錄，用“盒子”來(lái)存放待排記錄。這種排序方法的時(shí)間代價(jià)是(n),

但是它只能處理對(duì)一個(gè)從0到n-1的排列進(jìn)行排序。擴(kuò)展分配排序方法一：盒子可變長(zhǎng)，允許關(guān)鍵碼重復(fù)。即數(shù)組B中元素為一個(gè)鏈表的頭結(jié)點(diǎn).

關(guān)鍵碼重復(fù)的記錄在一個(gè)鏈表中，需要額外進(jìn)行排序。方法二：允許關(guān)鍵碼范圍大于n，先將所有的A[i]放入B中，再依次從關(guān)鍵碼B中讀出記錄.B的大小決定于記錄的最大值MaxKeyValue.將所有記錄A[i]放入B中的時(shí)間代價(jià)是(n)，從B中讀出所有記錄的時(shí)間代價(jià)是(MaxKeyValue)，故總時(shí)間代價(jià)是(n+MaxKeyValue)。但是,記錄的規(guī)模n和MaxKeyValue之間沒(méi)有任何必然聯(lián)系,因此,該算法的時(shí)間代價(jià)可能為(n2)甚至更糟.分配排序的擴(kuò)展桶式排序

BucketSort每一個(gè)“盒子(桶)”中存放一組相關(guān)的關(guān)鍵碼,然后借助其他排序技術(shù)對(duì)每一個(gè)“桶”中的記錄排序。分桶處理技術(shù)＋收尾排序。基數(shù)排序?qū)⑴判蜿P(guān)鍵字K看作是由多個(gè)關(guān)鍵字組成的組合關(guān)鍵字，即K=k1k2…kd。每個(gè)關(guān)鍵字ki表示關(guān)鍵字的一位，其中k1為最高位，kd為最低位，d為關(guān)鍵字的位數(shù)。例如，序列(101,203,567,231,478,352)，可以將每個(gè)關(guān)鍵字K看成由三個(gè)單關(guān)鍵字組成，即K=k1k2k3，每個(gè)關(guān)鍵字的取