第10章排序(上課用)講述

數(shù)據(jù)結構主講人：張立震e-mail:system0@打撲克例子世界杯比賽排名阿根廷法國阿根廷意大利法國意大利法國英國中國巴西巴西阿根廷西班牙葡萄牙阿根廷例子數(shù)據(jù)結構期末成績排名學號姓名成績1110810113劉德華981110810221陳鑫961110820109劉亦菲911110820104黃渤871110820116頊曉宇83………例子第十章內部排序10.1概述10.2插入排序(直接插入、折半插入、希爾排序)10.3交換排序(冒泡排序、快速排序)10.4選擇排序(簡單選擇、樹形選擇、堆排序)10.5歸并排序10.6基數(shù)排序10.7各種排序小結排序：整理文件中的記錄，使之按關鍵字遞增

(或遞減)次序排列起來。關鍵字：以數(shù)據(jù)對象的多個屬性域中的一個為排序依據(jù)，該屬性域即為關鍵字。如何排序什么是排序？為什么排序？？內部排序外部排序將欲處理的數(shù)據(jù)整個存放到內部存儲器中排序，數(shù)據(jù)可被隨機存取交換式排序選擇式排序插入式排序由于排序期間數(shù)據(jù)太多，需要借助外部的輔助存儲器，不斷在內、外存只見移動的排序，數(shù)據(jù)不可隨機存取

排序的分類歸并排序基數(shù)排序排序算法衡量標準穩(wěn)定性不穩(wěn)定性排序過后能使值相同的數(shù)據(jù)保持原順序中的相對位置

排序過后不能使值相同的數(shù)據(jù)保持原順序中的相對位置

49325649272732494956時間復雜度（最好情況和最壞情況）空間復雜度穩(wěn)定性排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。

本教材定義的待排數(shù)據(jù)表類型

typedefstruct{KeyTypekey;//關鍵字項

InfoTypeotherinfo;//其他數(shù)據(jù)項

}RedType;typedefstruct{RedTyper[MAXSIZE+1];//r[0]閑置或作哨兵

intlength;}SqList;

直接插入排序(InsertSort)

折半插入排序(BinaryInsertSort)

2-路插入排序（略）表插入排序（略）希爾排序(ShellSort)10.2插入排序基本思想

每步將一個待排序的對象，按其排序碼大小，插入到前面已經排好序的一組對象的適當位置上，直到對象全部插入為止?；舅枷耄喉樞虻匕汛判虻臄?shù)據(jù)元素按其值的大小插入到已排序數(shù)據(jù)元素子集合的適當位置。有序序列無序序列1.直接插入排序(InsertSort)12578630941256783094基本思想：順序地把待排序的數(shù)據(jù)元素按其值的大小插入到已排序數(shù)據(jù)元素子集合的適當位置。1.直接插入排序(InsertSort)

當插入第i(i

1)個對象時，前面的r[1],…,r[i-1]已經排好序。這時，用r[i]的排序碼與r[i-1],r[i-2],…的排序碼順序進行比較，找到插入位置即將V[i]插入，原來位置上的對象向后順移。子集合的數(shù)據(jù)元素個數(shù)從只有一個數(shù)據(jù)元素開始逐次增大。當子集合大小最終和集合大小相同時排序完畢。647]896468989646464直接插入排序[64]789624[5]89624[57]624[5724[56][567246489]578924初始序列:第1趟排序:第2趟排序:第3趟排序:第4趟排序:第5趟排序:jjjj6Temp6

直接插入排序的算法(p265算法10.1)voidInsertSort(SqList&L){inti,j;for(i=2;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-1].key)){//"<"時，需將L.r[i]插入有序子表

L.r[0]=L.r[i];//L.r[0]為監(jiān)視哨

for(j=i-1;LT(L.r[0].key,L.r[j].key);--j) L.r[j+1]=L.r[j]; //記錄后移

L.r[j+1]=L.r[0];//插入到正確位置

}

}最壞情況下

最好情況下比較次數(shù)：n-1移動次數(shù)：0算法分析比較次數(shù)：移動次數(shù)：2)1)(2(2-+=?=nnini2)1)(4(1-+=+?nnin2=i）（（正序）

（逆序）直接插入排序的時間復雜度為O(n2)?？臻g性能：需要一個記錄的輔助空間（監(jiān)視哨）。穩(wěn)定性：直接插入排序算法是一種穩(wěn)定的排序算法。特點：簡單、容易實現(xiàn)，適用于待排序記錄基本有序或待排序記錄較小時。算法分析2464[57]624[576489]896第2趟排序:第3趟排序:temp62.折半插入(BinaryInsertSort)

基本思想：在查找插入位置時，使用折半查找算法。如何提高查找效率呢？642.折半插入(BinaryInsertSort)

基本思想：在查找插入位置時，使用折半查找算法。如何提高查找效率呢？[57]624[576489]896第2趟排序:第3趟排序:temp689647low6mhighvoidBInsertSort(SqList&L){inti,j,high,low,m;for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//將L.r[i]暫存到L.r[0]

low=1;high=i-1;

while(low<=high)//在r[low..high]中折半查找有序插入的位置

{m=(low+high)/2;//折半

if(LT(L.r[0].key,L.r[m].key))high=m-1;//插入點在低半?yún)^(qū)

elselow=m+1;//插入點在高半?yún)^(qū)

}for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//記錄后移

L.r[high+1]=L.r[0];//插入

}}//BInsertSort折半插入排序算法時間性能分析：移動次數(shù)與直接插入排序相同比較次數(shù)與初始順序無關，只依賴于記錄個數(shù)插入每個記錄需要log2i次比較時間復雜度為O(n2)?？臻g代價:

與直接插入排序相同穩(wěn)定性:

穩(wěn)定算法分析

基本思想：把待排序的數(shù)據(jù)元素分成若干個小組，對同一小組內的數(shù)據(jù)元素用直接插入法排序；小組的個數(shù)逐次縮小；當完成了所有數(shù)據(jù)元素都在一個組內的排序后排序過程結束。希爾排序又稱作縮小增量排序。3.希爾排序(ShellSort)開始時

gap（間隔值）

的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，gap

值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎，大多數(shù)對象已基本有序，所以排序速度仍然很快。希爾排序過程653425871238564614779223566514257787382356341477122365462587923865771234561214653423774625879238121423253438465665778792結果序列gap=6gap=3gap=1voidShellInsert(SqList&L,intgap){

//對順序表L作一趟希爾插入排序。本算法對算法10.1作了以下修改：

//1.前后記錄位置的增量是gap，而不是1；

//2.r[0]只是暫存單元，不是哨兵。當j<=0時，插入位置已找到。

inti,j;for(i=gap+1;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-gap].key)){//將L.r[i]插入有序增量子表

L.r[0]=L.r[i];//暫存在L.r[0]

for(j=i-gap;j>0&<(L.r[0].key,L.r[j].key);j-=gap)

L.r[j+gap]=L.r[j];//記錄后移，查找插入位置

L.r[j+gap]=L.r[0];//插入

}}//ShellInsert希爾排序的算法(算法10.4)voidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]對順序表L作希爾排序。

for(intk=0;k<t;++k)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}//ShellSort希爾排序的算法(算法10.5)算法分析對特定的待排序序列，可準確地估算關鍵字的比較次數(shù)和對象移動次數(shù)。但想要弄清關鍵字比較次數(shù)和對象移動次數(shù)與增量選擇之間的依賴關系，并給出完整的數(shù)學分析，還沒有人能夠做到。增量序列的取法有多種。最初shell提出取gap=n/2，gap=gap/2，直到gap=1。后來Knuth提出取gap=gap/3+1。還有人提出各gap互素為好。Knuth利用大量的實驗統(tǒng)計資料得出，當n很大時，關鍵字平均比較次數(shù)和對象平均移動次數(shù)大約在n1.25到1.6n1.25的范圍內。

冒泡排序(BubbleSort)

快速排序(QuickSort)10.3交換排序基本思想

兩兩比較待排序對象的關鍵字，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有對象都排好序為止?；舅枷耄涸O待排序序列中的對象個數(shù)為n，最多作n-1趟排序。在第i

趟中順次兩兩比較r[j].Key和r[j+1].Key，

j=1,2,…,i-1;i=n,n-1,…,2.如果發(fā)生逆序，則交換r[j]和r[j+1]。1.冒泡排序(BubbleSort)冒泡排序4938659776132749979797384927137665493849276513493849271349384927133827137676654949382713特點：

n

個數(shù)排序共需進行n-1趟比較第i趟共需進行n-i次比較冒泡排序的原始算法voidBubbleSort(SqList&L){//將L中整數(shù)序列排列成自小至大有序的序列

for(i=n;i>=2;--i)for(j=1;j<i;++j)if(L.r[j].key>L.r[j+1].key){ElemTypetemp=L.r[j];//交換

L.r[j]=L.r[j+1];

L.r[j+1]=temp;

}}問題：剛才的改進算法是否已經最優(yōu)?冒泡排序的改進算法123456789123456789123456789123456789

如何解決呢？

冒泡排序的改進算法voidBubbleSort(SqList&L){for(i=n,Change=TRUE;i>=2&&Change;--i){Change=FALSE;for(j=1;j<i;++j)if(L.r[j].key>L.r[j+1].key){ElemTypetemp=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=temp;Change=TRUE;}}}最壞情況（逆序）：最好情況（正序）：比較次數(shù)：n-1移動次數(shù)：0

比較次數(shù)：移動次數(shù)：2)1(1-=?=nn(n-i)n-1i2)1(1-=?=n3n3(n-i)n-1i算法分析

時間復雜度為O(n2)

穩(wěn)定性：穩(wěn)定基本思想：任取待排序對象序列中的某個對象（例如取第一個對象）作為樞軸(pivot)，按照該對象的關鍵字大小，將整個對象序列劃分為左右兩個子序列：2.快速排序(QuickSort)左側子序列中所有對象的關鍵字都小于樞軸對象的關鍵字。右側子序列中所有對象的關鍵字都大于或等于樞軸對象的關鍵字。樞軸對象則排在這兩個子序列中間(這也是該對象最終應安放的位置)。然后分別對這兩個子序列重復施行上述方法，直到所有的對象都排在相應位置上為止。一趟快速排序的具體過程4938659776132749pivot=49lowhigh27low65high13low97highhigh49第一趟結果：

[273813]49[76976549]小于49大于等于49快速排序每一趟的劃分

intPartition(SqList&L,intlow,inthigh){/*交換順序表L中子表r[low…h(huán)igh]的記錄，樞軸記錄到位，并返回其所在的位置，此時在它之前（后）的記錄均不大（小）于它*/}//Partition

快速排序每一趟的劃分

intPartition(SqList&L,intlow,inthigh){/*交換順序表L中子表r[low…h(huán)igh]的記錄，樞軸記錄到位，并返回其所在的位置，此時在它之前（后）的記錄均不大（?。┯谒?/

L.r[0]=L.r[low];//用子表的第一個記錄作樞軸記錄

intpivotkey=L.r[low].key;//樞軸記錄關鍵字}//Partition

快速排序每一趟的劃分

intPartition(SqList&L,intlow,inthigh){/*交換順序表L中子表r[low…h(huán)igh]的記錄，樞軸記錄到位，并返回其所在的位置，此時在它之前（后）的記錄均不大（?。┯谒?/

L.r[0]=L.r[low];//用子表的第一個記錄作樞軸記錄

intpivotkey=L.r[low].key;//樞軸記錄關鍵字

while(low<high){}}//Partition

快速排序每一趟的劃分

intPartition(SqList&L,intlow,inthigh){/*交換順序表L中子表r[low…h(huán)igh]的記錄，樞軸記錄到位，并返回其所在的位置，此時在它之前（后）的記錄均不大（?。┯谒?/

L.r[0]=L.r[low];//用子表的第一個記錄作樞軸記錄

intpivotkey=L.r[low].key;//樞軸記錄關鍵字

while(low<high){}L.r[low]=L.r[0];//樞軸記錄到位

returnlow;//返回樞軸位置

}//Partition

快速排序每一趟的劃分

intPartition(SqList&L,intlow,inthigh){/*交換順序表L中子表r[low…h(huán)igh]的記錄，樞軸記錄到位，并返回其所在的位置，此時在它之前（后）的記錄均不大（小）于它*/

L.r[0]=L.r[low];//用子表的第一個記錄作樞軸記錄

intpivotkey=L.r[low].key;//樞軸記錄關鍵字

while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;

}L.r[low]=L.r[0];//樞軸記錄到位

returnlow;//返回樞軸位置

}//Partition

快速排序每一趟的劃分

intPartition(SqList&L,intlow,inthigh){/*交換順序表L中子表r[low…h(huán)igh]的記錄，樞軸記錄到位，并返回其所在的位置，此時在它之前（后）的記錄均不大（?。┯谒?/

L.r[0]=L.r[low];//用子表的第一個記錄作樞軸記錄

intpivotkey=L.r[low].key;//樞軸記錄關鍵字

while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//將比樞軸記錄小的記錄移到低端

}L.r[low]=L.r[0];//樞軸記錄到位

returnlow;//返回樞軸位置

}//Partition

快速排序每一趟的劃分

intPartition(SqList&L,intlow,inthigh){/*交換順序表L中子表r[low…h(huán)igh]的記錄，樞軸記錄到位，并返回其所在的位置，此時在它之前（后）的記錄均不大（?。┯谒?/

L.r[0]=L.r[low];//用子表的第一個記錄作樞軸記錄

intpivotkey=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;//返回樞軸位置

}//Partition

快速排序算法voidQSort(SqList&L,intlow,inthigh){//對順序表L中的子序列L.r[low…h(huán)igh]作快速排序

if(low<high)//長度大于1{pivotloc=Partition(L,low,high);//將L.r[low..high]一分為二

QSort(L,low,pivotloc-1);//對低子表遞歸排序

QSort(L,pivotloc+1,high);//對高子表遞歸排序

}}//QSort算法分析最理想的情況：每次劃分對一個對象定位后，該對象的左側子序列與右側子序列的長度相同。就平均時間而言，快速排序是最好的一種內部排序方法。平均計算時間是O(nlog2n)最壞情況：初始關鍵字有序或基本有序。此時快速排序蛻化為冒泡排序，時間復雜度為O(n2)。占用附加存儲(即棧)將達到O(n)。快速排序是一種不穩(wěn)定的排序方法。對于n較大的平均情況而言，快速排序是“快速”的，但是當n

很小時，這種排序方法往往比其它簡單排序方法還要慢。

簡單選擇排序(SimpleSelectionSort)

樹形選擇排序(TreeSelectionSort)

堆排序(HeapSort)10.4選擇排序基本思想

每一趟(例如第i趟,i=1,…,n-1)在后面n-i+1個待排序記錄中選出排序碼最小的記錄,作為有序序列中的第i個記錄。待到第n-1趟作完,待排序記錄只剩下1個,就不用再選了?；舅枷耄篿從1開始，直到n-1，進行n-1趟排序。第i

趟的排序過程為：在一組對象r[i]～r[n](i=1,2,…,n-1)中選擇具有最小關鍵字的對象，并和第i個對象進行交換。1.簡單選擇排序(SimpleSelectionSort)一趟簡單選擇排序的過程149238365497576613727849ki=1jkjjjjkjjk1349149238365497576613727849i=kjjjjjj1349kk2一趟簡單選擇排序的過程voidSelectSort(SqList&L){for(inti=1;i<L.length;i++){k=SelectMinKey(L,i);if(i!=k){ElemTypetemp=L.r[i];L.r[i]=L.r[k];L.r[k]=temp;}}}intSelectMinKey(SqList&L,inti){intm=i; for(j=i+1;j<=L.length;j++)if(L.r[j].key<L.r[m].key) m=j;//當前具最小關鍵碼的對象

returnm; }簡單選擇排序的算法最壞情況：算法分析移動次數(shù)：最好情況：比較次數(shù)：)()1(21211nOnninni=-=-?-=）（

時間復雜度為O(n2)。

穩(wěn)定性：不穩(wěn)定為什么？0次3(n-1)次世界杯比賽排名巴西法國巴西意大利法國意大利法國英國中國巴西巴西阿根廷西班牙葡萄牙阿根廷8個國家參加世界杯，需要多少次比賽得出冠軍？樹形選擇排序又稱為錦標賽排序?；舅枷耄号c體育比賽時的淘汰賽類似。首先取得n個對象的關鍵碼，進行兩兩比較，得到n/2

個比較的優(yōu)勝者(關鍵碼小者)，作為第一步比較的結果保留下來。然后對這n/2

個對象再進行關鍵碼的兩兩比較，…，如此重復，直到選出一個關鍵碼最小的對象。2.樹形選擇排序(TreeSelectionSort)133813973865493876131327652749139749387613652749381338651327∞27382738657627279749387613652749382738657627∞13∞38384938657649錦標賽排序構成的樹是滿的完全二叉樹，其深度為log2(2n-1)取上整，其中n為待排序元素個數(shù)。除第一次選擇具有最小關鍵字的對象需要進行n-1次關鍵字比較外，重構勝者樹選擇具有次小、再次小關鍵字對象所需的關鍵字比較次數(shù)均為O(log2n)?？傟P鍵字比較次數(shù)為O(nlog2n)。對象的移動次數(shù)不超過關鍵字的比較次數(shù)，所以錦標賽排序總的時間復雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時間，但是使用了較多的附加存儲。錦標賽排序是一個穩(wěn)定的排序方法。算法分析3.堆排序(HeapSort)堆定義：n

個元素的序列{k1,k2,…,kn}當且僅當滿足下列關系時，稱之為堆。

ki≤k2i

ki≥k2i

ki≤k2i+1

ki

≥

k2i+1其中，i=1,2,…,[n/2].前者稱為最小堆，后者稱為最大堆?；蜃钚《雅c最大堆舉例9683273811091236248547913053最大堆最小堆基本思想：在輸出堆頂?shù)淖钚≈抵?，使得剩余n-1個元素的序列重又建成一個堆，則得到n個元素中的次小值。反復執(zhí)行，直到得到一個有序序列。堆排序分為兩個步驟：根據(jù)初始輸入數(shù)據(jù)形成初始堆；通過一系列的對象交換和重新調整堆進行排序。3.堆排序(HeapSort)關鍵問題：如何由一個無序序列建成一個堆?如何調整余下的元素成為一個新堆?3.堆排序(HeapSort)堆調整過程1338277697654949rc=13492525*211608123456082525*16214913654249252125*160808252125*1649交換1

號與6號對象,6號對象就位初始最大堆堆調整2525*082116491234561625*082521491365422525*210816491625*210825

49交換1

號與5號對象,5號對象就位從1號到5號重新調整為最大堆堆調整25*1608212549123456081625*25214913654225*16210825

4908162125*

25

49交換1

號與4號對象,4號對象就位從1號到4號重新調整為最大堆堆調整211625*082549123456081625*25214913654221160825*

25

49081621

25*

25

49交換1

號與3號對象,3號對象就位從1號到3號重新調整為最大堆堆調整160825*212549123456081625*25214913654216082125*

25

490816

21

25*

25

49交換1

號與2號對象,2號對象就位從1號到2號重新調整為最大堆堆調整212525*491608123456i212525*164908136542i21254925*1608初始關鍵字集合21254925*1608i=3時的局部調整建立初始的最大堆212525*491608123456i492525*16210813654221254925*160849252125*1608i=1時的局部調整形成大頂堆i=2時的局部調整建立初始的最大堆最大堆的第一個對象r[1]具有最大的關鍵字，將r[1]與r[n]對調，把具有最大關鍵字的對象交換到最后，再對前面的n-1個對象，使用堆的調整算法HeapAdjust(1,n-1)，重新建立最大堆。結果具有次最大關鍵字的對象又上浮到堆頂，即r[1]位置。再對調r[1]和r[n-1]，調用HeapAdjust(1,n-2)，對前n-2個對象重新調整。如此反復執(zhí)行，最后得到全部排序好的對象序列。這個算法即堆排序算法。typedefSqListHeapType;//順序存儲方式基于初始堆進行堆排序voidHeapAdjust(HeapType&H,ints,intm){//調整H.r[s]的關鍵字，使H.r[s…m]成為一個大頂堆

ElemTyperc=H.r[s];

for(intj=2*s;j<=m;j*=2)//沿較大的孩子結點向下篩選

{if((j<m)&&(LT(H.r[j].key,H.r[j+1].key)))++j;//j為key較大的結點下標

if(!(LT(rc.key,H.r[j].key)))break;//找到rc待插位置s

H.r[s]=H.r[j];s=j;/*改變后的局部子堆頂?shù)闹?，s隨著

j的向下移動而向下移動*/

}

H.r[s]=rc;//插入}最大堆的向下調整算法voidHeapSort(HeapType&H){inti;RedTypetemp;for(i=H.length/2;i>0;--i)//把H.r[1..H.length]建成大頂堆

HeapAdjust(H,i,H.length);for(i=H.length;i>1;--i){temp=H.r[i];H.r[i]=H.r[1];H.r[1]=temp;/*將堆頂記錄和當前未經排序子序列Hr[1..i]中

最后一個記錄相互交換*/

HeapAdjust(H,1,i-1);//將H.r[1..i-1]重新調整為大頂堆

}}//HeapSort堆排序算法算法分析適宜記錄較多的文件在最壞的情況下，時間復雜度為O(nlog2n)堆排序是一個不穩(wěn)定的排序方法。10.5歸并排序基本思想

將一個具有n個待排序記錄的序列看成是n個長度為1的有序序列，然后進行兩兩歸并，得到

n/2

個長度為2的有序序列，再進行兩兩歸并，得到

n/4個長度為4的有序序列，……，直至得到一個長度為n的有序序列為止。歸并排序過程<初態(tài)>(49)(38)(65)(97)(76)(13)(27)(3849)(13273849657697)<第1趟>(6597)(1376)(27)<第2趟>(38496597)(132776)<第3趟>voidMerge(ElemTypeSR[],ElemTypeTR[],inti,intm,intn){for(intj=m+1,k=i;i<=m&&j<=n;++k){if(LQ(SR[i].key,SR[j].key))TR[k]=SR[i++]; elseTR[k]=SR[j++];}

if(i<=m)for(intn1=k,n2=i;n1<=n&&n2<=m;n1++,n2++) TR[n1]=SR[n2];if(j<=n)for(intn1=k,n2=j;n1<=n&&n2<=n;n1++,n2++) TR[n1]=SR[n2];}二路歸并排序算法voidMSort(ElemTypeSR[],ElemTypeTR1[],ints,intt){ElemTypeTR2[MAXSIZE];if(s==t)TR1[s]=SR[s];else{intm=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t); }}voidMergeSort(SqList&L){MSort(L.r,L.r,1,L.length);}二路歸并排序算法在歸并排序算法中，遞歸深度為O(log2n)，對象關鍵字的比較次數(shù)為O(nlog2n)。算法總的時間復雜度為O(nlog2n)。歸并排序占用附加存儲較多，需要另外一個與原待排序對象數(shù)組同樣大小的輔助數(shù)組。這是這個算法的缺點。歸并排序是一個穩(wěn)定的排序方法。算法分析10.6基數(shù)排序基本思想

基數(shù)排序是按組成關鍵字的各位的值進行“分配”和“收集”，與前面介紹的排序方法不同，它無需進行關鍵字之間的比較，而是借助多關鍵字進行排序。多關鍵字對象X=(K1,K2,…,Kd)以撲克牌排序為例。每張撲克牌有兩個“關鍵字”：花色和面值。其有序關系為：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A如果把所有撲克牌排成以下次序：

2,…,A,2,…,A,2,…,A,2,…,A這就是多關鍵字排序。排序后形成的有序序列叫做詞典有序序列。多關鍵字排序一般情況下，假定有一個n

個對象的序列

{V0,V1,…,Vn-1}，且每個對象Vi

中含有d

個關鍵字如果對于序列中任意兩個對象Vi和Vj(0

i<j

n-1)都滿足：則稱序列對關鍵字(K1,K2,…,Kd)有序。其中，K1

稱為最高位關鍵字，Kd

稱為最低位關鍵字。多關鍵字排序如果關鍵字是由多個數(shù)據(jù)項組成的數(shù)據(jù)項組，則依據(jù)它進行排序時就需要利用多關鍵字排序。實現(xiàn)多關鍵字排序有兩種常用的方法最高位優(yōu)先MSD(MostSignificantDigitfirst)最低位優(yōu)先LSD(LeastSignificantDigitfirst)多關鍵字排序原始序列：278109063930589184505269008083第一遍：按個位數(shù)放入10個箱子（隊列）01234567890123456789278012345678910901234567890630123456789930012345678958901234567891840123456789505012345678926901234567890080123456789083按0-9的順序從10個箱子中收集數(shù)字第一趟收集的序列：930

063083

184

505

278008

109589269

收集序列：930

063083

184

505

278008

109589269

第二遍：按十位數(shù)放入10個箱子（隊列）按0-9的順序從10個箱子中收集數(shù)字第二趟收集的序列：50500810993006326927808318458901234567890123456789930012345678906301234567890830123456789184012345678950501234567892780123456789008