數(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á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.交換排序方法插入類排序選擇類排序交換類排序歸并排序插入排序希爾排序選擇排序堆排序快速排序分配類排序：基數(shù)排序起泡排序排序技術(shù)種類

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

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

如快速、堆和歸并排序；

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

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

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

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

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

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

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

(3)插入第j個(gè)元素的方法：將j放在變量T中，從有序子表（原線性表的前j-1個(gè)元素）的最后一個(gè)元素開始，往前逐個(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á)到有序化。其處理過程為：對(duì)待排序的記錄序列從后向前（或從前向后）進(jìn)行掃描。依次比較相鄰記錄的關(guān)鍵字。交換比較中發(fā)現(xiàn)的逆序。因此關(guān)鍵字值小的記錄左移，關(guān)鍵字值大的記錄右移。一次掃描后，最小值移動(dòng)序列的頂端。做n-1遍從后向前（或從前向后）的掃描和逆序交換，或直到未發(fā)現(xiàn)逆序?yàn)橹埂Ｆ鹋菖判蛩惴≒144-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);}教科書上有錯(cuò)起泡排序代價(jià)分析比較次數(shù)：時(shí)間代價(jià)：Θ(n2)

需增加一個(gè)輔助單元進(jìn)行交換；空間代價(jià)：Θ(1)問：如何改進(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);}}選擇排序和起泡排序的比較相同：表面上來看，一輪比較和交換后，最小值都放到了頂部；實(shí)質(zhì)上而言，選擇排序就是起泡排序；不同：選擇排序中最小元素一次交換到位；選擇排序的交換次數(shù)要比起泡排序少得多。起泡排序選擇排序選擇排序的時(shí)間代價(jià)選擇排序?qū)嵸|(zhì)上是起泡排序。選擇排序比較次數(shù)：Θ(n2)交換的次數(shù)比起泡排序少。因此，總的時(shí)間代價(jià)為Θ(n2)

。交換指針只交換指針，不移動(dòng)記錄本身，換來更高的效率,特別當(dāng)記錄很大的時(shí)候。可以降低排序算法中交換記錄所需要的時(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à)(平均來說):考慮一個(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排序又稱為縮小增量排序?；舅枷耄簩⒄麄€(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來選?。ā?21，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)困難，其效率依賴于增量序列的選取?？梢哉J(rèn)為Shell排序的平均時(shí)間代價(jià)為Θ(n1.5)希爾排序的空間代價(jià)為Θ(1)；同插入排序一樣，希爾排序也只需要一個(gè)記錄大小的輔助空間，用于暫存當(dāng)前待插入的記錄。當(dāng)n為中等規(guī)模大小時(shí)Shell排序是不錯(cuò)的選擇二叉查找樹中序遍歷有序序列888082688582

7571778880826885827177757.4快速排序分治法(divideandconquer)的思想：根結(jié)點(diǎn)將左、右子樹分開，形成：左子樹<根右子樹二叉查找樹中序周游可得到有序序列，但弊端多：存儲(chǔ)占用大量結(jié)點(diǎn)空間、二叉樹不平衡時(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為止。快速排序的步驟123 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開始向后掃描，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開始向前掃描。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開始向后掃描。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開始掃描。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開始向后掃描。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)。快速排序的空間代價(jià)快速排序每次只能對(duì)一個(gè)子表進(jìn)行排序，已劃分的另一個(gè)子表需要用棧來記錄下來，留待以后進(jìn)行排序。通常情況下空間代價(jià)(記錄子表的棧)為Θ(logn);最壞情況下空間代價(jià)為Θ(n);快速排序的優(yōu)化軸值pivot的選取第一個(gè)或最后一個(gè)記錄的關(guān)鍵字易退化為起泡算法。隨機(jī)選取值開銷大數(shù)組中間點(diǎn)三者取中法首中尾三個(gè)記錄的中間值用于小子表的更佳算法劃分過程沒有必要?jiǎng)澐值阶颖黹L(zhǎng)度為1的情況，當(dāng)子表長(zhǎng)度小于某個(gè)值時(shí)，調(diào)用其他排序方法會(huì)快點(diǎn)。消除遞歸將遞歸改成非遞歸算法。速度加快。快速排序總結(jié)快速排序是一個(gè)遞歸的過程。在遞歸調(diào)用時(shí)需要占據(jù)一定的存儲(chǔ)空間用來保存每一層遞歸調(diào)用時(shí)的必要信息?？焖俚男逝c起泡排序相比有很大地提高。在起泡排序過程中是對(duì)相鄰兩個(gè)記錄進(jìn)行關(guān)鍵字比較和互換的，這樣每次交換記錄后，只能改變一對(duì)逆序記錄；而快速排序則從待排序記錄的兩端開始進(jìn)行比較和交換，并逐漸向中間靠攏，每經(jīng)過一次交換，有可能改變幾對(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開始，整個(gè)合并完成需要logn次，總的時(shí)間代價(jià)為Θ(nlogn)。該時(shí)間代價(jià)并不依賴于待排數(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)決定于樹的深度Θ(logn)，隨著選出結(jié)點(diǎn)的增多，待排的堆體積不斷減小，調(diào)整的路長(zhǎng)也不斷減小，所以調(diào)整的時(shí)間代價(jià)最多為Θ(logn)；即堆排序總的時(shí)間為Θ(n)+(n-1)?Θ(logn)，也就是說堆排序的時(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[]用來確定一個(gè)記錄在排序中的最終記錄，用“盒子”來存放待排記錄。這種排序方法的時(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之間沒有任何必然聯(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)鍵字的取