中山大學(xué)-數(shù)據(jù)結(jié)構(gòu)-內(nèi)部排序

第十章內(nèi)部排序?qū)W習(xí)目標(biāo)理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用。排序方法有不同的分類方法，基于“關(guān)鍵字間的比較”進(jìn)行排序的方法可以按排序過程所依據(jù)的不同原則分為插入排序、快速（交換）排序、選擇排序、歸并排序和基數(shù)排序等五類。掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。能從“關(guān)鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時(shí)間性能。按平均時(shí)間復(fù)雜度劃分，內(nèi)部排序可分為三類：O(n2)的簡(jiǎn)單排序方法，O(n·logn)的高效排序方法和O(d·n)的基數(shù)排序方法。理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義。2/3/20231重點(diǎn)和難點(diǎn)重點(diǎn)：希爾排序、快速排序、堆排序和歸并排序等高效方法難點(diǎn)：希爾排序、快速排序、堆排序和歸并排序等高效方法知識(shí)點(diǎn)排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序、2-路歸并排序、基數(shù)排序、排序方法的綜合比較。2/3/2023210.1概述排序假設(shè)含有n個(gè)記錄的序列為：{R1，R2，…，Rn}，

它們的關(guān)鍵字相應(yīng)為{K1，K2，…，Kn}，

對(duì)記錄序列進(jìn)行排序就是要確定序號(hào)1，2，…，n的一種排列P1，P2，…，Pn，使其相應(yīng)的關(guān)鍵字滿足如下的非遞減（或非遞增）的關(guān)系：

Kp1<=Kp2<=…<=Kpn

使序列成為一個(gè)按關(guān)鍵字有序的序列

{Rp1，Rp2，…，Rpn}目的利用高效的查找方法，以提高查找效率。2/3/20233排序分類按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存。外部排序：排序過程中需對(duì)外存進(jìn)行訪問的排序。按排序依據(jù)原則插入排序：直接插入排序、折半插入排序、希爾排序。快速（交換）排序：冒泡排序、快速排序。選擇排序：簡(jiǎn)單選擇排序、堆排序。歸并排序：2-路歸并排序。基數(shù)排序2/3/20234穩(wěn)定若待排序文件中有關(guān)鍵字相等的記錄，排序后，其前后相對(duì)次序與排序前未發(fā)生變化，這種排序稱為“穩(wěn)定”排序；否則是“不穩(wěn)定”排序。穩(wěn)定排序與不穩(wěn)定排序只是表示所用的排序方法，并不說明哪種方法好與差。排序基本操作比較兩個(gè)關(guān)鍵字大小；將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置；就全面性能而言，很難提出一種被認(rèn)為最好的方法，每種方法均有優(yōu)點(diǎn)和適用環(huán)境。2/3/20235本章討論中，待排記錄如下結(jié)構(gòu)。#defineMAXSIZE20; //假設(shè)的順序表最大長(zhǎng)度

typeint

KeyType; //定義關(guān)鍵字類型為整數(shù)類型typedef

struct{

KeyTypekey;

//關(guān)鍵字項(xiàng)

InfoType

otherinfo;

//其它數(shù)據(jù)項(xiàng)

}RcdType; //記錄類型typedef

struct{

RcdTyper[MAXSIZE+1];

//r[0]閑置或作為判別標(biāo)志的“哨兵”單元

intlength;

//順序表長(zhǎng)度

}SqList； //順序表類型2/3/2023610.2插入排序10.2.1直接插入排序基本思想整個(gè)排序過程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序。2/3/2023749386597761327i=2(49)386597761327i=3(3849)6597761327i=4

(384965)97761327i=5

(38496597)761327i=6

(3849657697)1327i=1()i=7(133849657697)2727977665493827(13273849657697)排序結(jié)果：383849659797769776137665493813))))))))))))監(jiān)視哨r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]穩(wěn)定的排序方法2/3/20238voidInsertSort(SqList&L){

//對(duì)順序表L作直接插入排序

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]; //哨兵

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];

//插入到正確位置

}//if

}//InsertSort直接插入排序的算法1

2

3

4

5

6

7

8時(shí)間復(fù)雜度T(n)=O(n2)2/3/20239算法評(píng)價(jià)時(shí)間復(fù)雜度若待排序記錄按關(guān)鍵字從小到大排列(正序)

關(guān)鍵字比較次數(shù)：若待排序記錄按關(guān)鍵字從大到小排列(逆序)

關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：2/3/202310若待排序記錄是隨機(jī)的，取平均值。關(guān)鍵字比較次數(shù)：記錄移動(dòng)次數(shù)：空間復(fù)雜度S(n)=O(1)2/3/20231110.2.2其它插入排序折半插入排序基本思想用折半查找方法確定插入位置的排序。i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…i=820(6133039427085)20ihi=820(613203039427085)hmimhm插入位置2/3/202312voidBInsertSort(SqList&L){

//對(duì)順序表L作折半插入排序

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;

//插入點(diǎn)在低半?yún)^(qū)

elselow=m+1;

//插入點(diǎn)在高半?yún)^(qū)

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

L.r[high+1]=L.r[0];

//插入

}}//BInsertSort時(shí)間復(fù)雜度：T(n)=O(n2)2/3/202313算法評(píng)價(jià)時(shí)間復(fù)雜度：T(n)=O(n2)空間復(fù)雜度：S(n)=O(1)折半插入排序只能減少排序過程中關(guān)鍵字比較的時(shí)間，并不能減少記錄移動(dòng)的時(shí)間。2/3/2023142-路插入排序基本思想

另設(shè)一個(gè)和L.r同類型的數(shù)組d，首先將L.r[1]賦給d[1]，并將d[1]看成是在排好序的序列中處于中間位置的記錄，然后從L.r中第2個(gè)記錄起依次插入到d[1]之前或之后的有序序列中。目的對(duì)折半插入排序的改進(jìn)，減少記錄的移動(dòng)次數(shù)。2/3/202315初始關(guān)鍵字4938659776132749i=1(49)firstfinali=2(49)(38)firstfinali=3(4965)(38)firstfinali=4(496597)(38)firstfinal2/3/202316初始關(guān)鍵字4938659776132749i=4(496597)(38)firstfinali=5(49657697)(38)firstfinali=6(49657697)(1338)firstfinali=7(49657697)(132738)firstfinal2/3/202317初始關(guān)鍵字4938659776132749i=7(49657697)(132738)firstfinali=8firstfinal(4949657697)(132738)

2路插入排序的移動(dòng)記錄次數(shù)減少了，約為n2/8，但不能避免移動(dòng)。2/3/20231810.2.3希爾(shell)排序基本思想是對(duì)插入排序的一個(gè)改進(jìn)，也稱縮小增量排序。先將整個(gè)待排序記錄序列分割成若干個(gè)子序列，分別對(duì)這些子序列進(jìn)行直接插入排序；待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。排序過程取一個(gè)正整數(shù)d1<n，把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2<d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹埂?/3/202319初始關(guān)鍵字：49,38,65,97,76,13,27,49,55,4取d3=1三趟分組：三趟排序結(jié)果：一趟排序結(jié)果：二趟排序結(jié)果：取d1=5一趟分組：取d2=3二趟分組：493865977613274955413274955449386597761327495544938659776134493827495565977613449382749556597764132738494955657697不穩(wěn)定的排序方法2/3/202320一趟希爾排序算法10.4voidShellInsert(SqList&L，int

dk){

//對(duì)順序表L作一趟希爾插入排序。本算法是和一趟直接插入排序

//相比，作了如下修改：1.前后記錄位置的增量是dk，不是1；

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

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

//需將L.r[i]插入有序增量子表

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

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

L.r[j+dk]=L.r[0];

//插入

}//if}//ShellInsert2/3/202321希爾排序的算法10.5voidShellSort(SqList&L,int

dlta[],intt){

//按增量序列dlta[0..t-1]對(duì)順序表L作希爾排序

for(k=0;k<t;++t) //一趟增量為dlta[k]的插入排序

ShellInsert(L,dlta[k]);}//ShellSort希爾排序的時(shí)間復(fù)雜度和所取增量序列相關(guān)，例如已有學(xué)者證明，當(dāng)增量序列為2t-k-1(k=0,1,…，t-1)時(shí)，希爾排序的時(shí)間復(fù)雜度為O(n3/2)。2/3/202322希爾排序特點(diǎn)子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列。希爾排序可提高排序速度，因?yàn)榉纸M后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了；關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序。增量序列取法無除1以外的公因子；最后一個(gè)增量值必須為1；如……,9,5,3,2,1或……,31,15,7,3,1或……,40,13,4,1等。2/3/20232310.3交換排序起泡排序排序過程將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至第n-1個(gè)記錄和第n個(gè)記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上。對(duì)前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交換記錄的操作”為止。2/3/202324381327

4949第四趟后49384913273065第三趟后4938496513273076第二趟后493849657613273097第一趟后494938659776132749初始關(guān)鍵字132738

49第五趟后497697139727979713767627136527656513134949273827383849497649132738第六趟后時(shí)間復(fù)雜度最好情況（正序）比較次數(shù)：n-1

移動(dòng)次數(shù)：0最壞情況（逆序）

比較次數(shù)：空間復(fù)雜度：S(n)=O(1)移動(dòng)次數(shù)：為什么是比較次數(shù)的3倍？2/3/202325快速排序?qū)ζ鹋莘ǖ囊环N改進(jìn)。基本思想通過一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄進(jìn)行排序，以達(dá)到整個(gè)序列有序。2/3/202326排序過程對(duì)r[s……t]中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針i和j，設(shè)樞軸記錄rp=r[s]，x=rp.key，初始時(shí)令i=s,j=t；首先，從j所指位置向前搜索第一個(gè)關(guān)鍵字小于x的記錄，并和rp交換；再?gòu)膇所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于x的記錄，和rp交換；重復(fù)上述兩步，直至i==j為止；再分別對(duì)兩個(gè)子序列進(jìn)行快速排序，直到每個(gè)子序列只含有一個(gè)記錄為止。2/3/202327493865977613274927i初始關(guān)鍵字：jx49jii65j13i97jj494938659776132749初始關(guān)鍵字：完成一趟排序：2738134976976549一次劃分后：(273813)49(76976549)分別進(jìn)行快速排序：(13)

27

(38)

49(4965)

76(97)

(13)

27

(38)

49

49(65)

76(97)快速排序結(jié)束：13

27

3849

4965

76

97不穩(wěn)定的排序方法2/3/202328一趟快速排序的算法10.6intPartition(SqList&L,intlow,inthigh){

//交換順序表L中子表r[low..high]中的記錄，樞軸記錄到位，并返回

//其所在位置，此時(shí)，在它之前（后）的記錄均不大（?。┯谒?。

L.r[0]=L.r[low];

//用子表的第一個(gè)記錄作樞軸記錄

pivotkey=L.r[low].key;

//樞軸記錄關(guān)鍵字

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];

//將比樞軸記錄大的記錄移到高端

}//while L.r[low]=L.r[0];

//樞軸記錄到位

returnlow;

//返回樞軸位置}//Partition2/3/202329快速排序算法10.7和10.8voidQsort(SqList&L,intlow,inthigh){

//對(duì)順序表L中的子序列L.r[low…h(huán)igh]作快速排序

if(low<high){ //長(zhǎng)度大于1

pivotloc=Partition(L,low,high); //將L.r[low…h(huán)igh]劃分

Qsort(L,low,pivotloc-1); //對(duì)低子表排序

Qsort(L,pivotloc+1,high); //對(duì)高子表排序

}}//QsortvoidQuickSort(SqList&L){

//對(duì)順序表L作快速排序

Qsort(L,1,L.length);}//QuickSort時(shí)間復(fù)雜度T(n)=O(n2)2/3/202330算法分析時(shí)間復(fù)雜度最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n2)為防止最差情況的出現(xiàn)，一般采取“三者取中”法來確定樞軸。即在第一個(gè)記錄和最后一個(gè)記錄，以及中間位置的記錄中，選取值為中間的那個(gè)來作樞軸，這樣就能防止最差情況的出現(xiàn)?？臻g復(fù)雜度：需棧空間以實(shí)現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n)對(duì)隨機(jī)的關(guān)鍵字序列，快速排序是目前被認(rèn)為是最好的排序方法。2/3/20233110.4選擇排序基本思想每一趟在n-i+1（i=1,2,…,n-1）個(gè)記錄中選取關(guān)鍵字最小的記錄，并將它和第i個(gè)記錄進(jìn)行互換，從而使其成為有序序列中第i個(gè)記錄。10.4.1簡(jiǎn)單選擇排序排序過程首先，通過n-1次關(guān)鍵字比較，從n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換；再通過n-2次比較，從剩余的n-1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換；重復(fù)上述操作，共進(jìn)行n-1趟排序后，排序結(jié)束。2/3/202332

13(38659776492749)初始：(4938659776132749)i=11349i=22738i=3i=4i=5i=61327(659776493849)3865132738(9776496549)499713273849(76976549)49761327384976(9765)49766597132738497697(97)497665767697排序結(jié)束13273849769765()497676976576穩(wěn)定的排序方法2/3/202333簡(jiǎn)單選擇排序算法10.9voidSelectSort(SqList&L){

//對(duì)順序表L作簡(jiǎn)單選擇排序

for(i=1;i<L.length;++i){

//選擇第i小的記錄，并交換到位

j=i; for(k=i+1;k<=L.length;k++)

//在L.r[i..L.length]中選擇關(guān)鍵字最小的記錄

if(LT(L.r[k].key,L.r[j].key))j=k; if(i!=j)L.r[j]L.r[i];

//與第i個(gè)記錄互換

}//for}//SelectSort時(shí)間復(fù)雜度T(n)=O(n2)2/3/202334算法評(píng)價(jià)時(shí)間復(fù)雜度記錄移動(dòng)次數(shù)最好情況：0最壞情況：3(n-1)比較次數(shù)：空間復(fù)雜度：S(n)=O(1)2/3/20233510.4.3堆排序堆的定義n個(gè)元素的序列(k1,k2,……kn)，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆?；蛉魧⒋诵蛄袑?duì)應(yīng)的一維數(shù)組看成是一個(gè)完全二叉樹，則ki為二叉樹的根結(jié)點(diǎn)，k2i和k2i+1分別為ki的“左子樹根”和“右子樹根”。2/3/202336（96，83，27，38，11，9）（13，38，27，50，76，65，49，97）962791138831327384965765097大頂堆小頂堆2/3/202337堆排序?qū)o序序列建成一個(gè)堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑挠涗洠惠敵龆秧?shù)淖钚。ù螅┲岛?，使剩余的n-1個(gè)元素重又建成一個(gè)堆，則可得到n個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列的過程。堆排序需解決的兩個(gè)問題：如何由一個(gè)無序序列建成一個(gè)堆？(初始建堆)如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？2/3/202338第二個(gè)問題解決方法——篩選（以小頂堆為例）輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選”。2/3/20233913273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13,273849502765769713輸出：13,276549502738769713輸出：13,27,382/3/2023404965502738769713輸出：13,27,387665502738499713輸出：13,27,38,495065762738499713輸出：13,27,38,499765762738495013輸出：13,27,38,49,506597762738495013輸出：13,27,38,49,509765762738495013輸出：13,27,38,49,50,652/3/2023417665972738495013輸出：13,27,38,49,50,659765762738495013輸出：13,27,38,49,50,65,769765762738495013輸出：13,27,38,49,50,65,76,972/3/202342篩選算法10.10voidHeapAdjust(SqList&H,ints,intm){

//已知H.r[s..m]中記錄的關(guān)鍵字除H.r[s].key之外均滿足堆的定義，//本函數(shù)調(diào)整H.r[s]的關(guān)鍵字，使H.r[s..m]成為一個(gè)大頂堆（對(duì)其中

//記錄的關(guān)鍵字而言）

rc=H.r[s];

//暫存根結(jié)點(diǎn)的記錄

for(j=2*s;j<=m;j*=2){

//沿關(guān)鍵字較大的孩子結(jié)點(diǎn)向下篩選

if(j<m&<(H.r[j].key,H.r[j+1].key))++j;

//j為關(guān)鍵字較大的孩子記錄的下標(biāo)

if(!LT(rc.key,H.r[j].key))break;

//不需要調(diào)整，跳出循環(huán)

H.r[s]=H.r[j];s=j;//將大關(guān)鍵字記錄往上調(diào)

}//for H.r[s]=rc;

//回移篩選下來的記錄}//HeapAdjust若改為小頂堆，該如何修改語(yǔ)句？j<m&<(H.r[j+1].key,H.r[j].key)LT(rc.key,H.r[j].key)2/3/202343第一個(gè)問題解決方法從無序序列的第n/2個(gè)元素（即此無序序列對(duì)應(yīng)的完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選。496538271376975049653827137650974913382765765097例如：含8個(gè)元素的無序序列（49，38，65，97，76，13，27，50）2/3/20234449133827657650971327384965765097496538271376975049653827137650974913382765765097例如：含8個(gè)元素的無序序列（49，38，65，97，76，13，27，50）2/3/202345堆排序算法10.11voidHeapSort(SqList&H){

//對(duì)順序表H進(jìn)行堆排序

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){

H.r[1]H.r[i]; //將堆頂記錄和當(dāng)前未經(jīng)排

//序的子序列H.r[1..i]中最

//后一個(gè)記錄互相交換

HeapAdjust(H,1,i-1); //將H.r[1..i-1]重新調(diào)整為

//大頂堆

}//for}//HeapSort2/3/202346算法評(píng)價(jià)時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn)篩選算法：最多從第1層篩到最底層，為完全二叉樹的深度

log2n+1;初始建堆：調(diào)用篩選算法n/2次；重建堆：調(diào)用篩選算法n-1次?？臻g復(fù)雜度：S(n)=O(1)記錄較少時(shí)，不提倡使用。不穩(wěn)定的排序方法2/3/20234710.5歸并排序歸并將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。2-路歸并排序排序過程設(shè)初始序列含有n個(gè)記錄，則可看成n個(gè)有序的子序列，每個(gè)子序列長(zhǎng)度為1；兩兩合并，得到n/2個(gè)長(zhǎng)度為2或1的有序子序列；再兩兩合并，……如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。2/3/202348初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]穩(wěn)定的排序方法2/3/202349兩個(gè)有序序列歸并為一個(gè)有序序列的算法10.12voidMerge(RcdTypeSR[],RcdType&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){

//將SR中記錄按關(guān)鍵字從小到大地復(fù)制到TR中

if(LQ(SR[i].key,SR[j].key))TR[k]=SR[i++];

elseTR[k]=SR[j++];

} while(i<=m)TR[k++]=SR[i++];//將剩余的SR[i..m]復(fù)制到TR while(j<=n)TR[k++]=SR[j++];//將剩余的SR[j..n]復(fù)制到TR}//Merge2/3/202350算法評(píng)價(jià)時(shí)間復(fù)雜度：T(n)=O(nlog2n)每趟兩兩歸并需調(diào)用merge算法n/2h次（h為有序段長(zhǎng)度）；整個(gè)歸并要進(jìn)行l(wèi)og2n趟。空間復(fù)雜度：S(n)=O(n)2/3/20235110.6基數(shù)排序10.6.1多關(guān)鍵字的排序多關(guān)鍵字排序例對(duì)52張撲克牌按以下次序排序：兩個(gè)關(guān)鍵字：花色（<<<）

面值（2<3<……<A）

并且“花色”地位高于“面值”2<3<……<A<2<3<……<A<

2<3<……<A<2<3<……<A2/3/202352多關(guān)鍵字排序方法最高位優(yōu)先法（MSD)：

先對(duì)最高位關(guān)鍵字k1排序，將序列分成若干子序列，每個(gè)子序列有相同的k1值；然后讓每個(gè)子序列對(duì)次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個(gè)子序列對(duì)最低位關(guān)鍵字kd排序；最后將所有子序列依次連接在一起成為一個(gè)有序序列。最低位優(yōu)先法(LSD)：

從最低位關(guān)鍵字kd起進(jìn)行排序，然后再對(duì)高一位的關(guān)鍵字排序，……依次重復(fù)，直至對(duì)最高位關(guān)鍵字k1排序后，便成為一個(gè)有序序列。2/3/202353MSD與LSD不同特點(diǎn)按MSD排序，必須將序列逐層分割成若干子序列，然后對(duì)各子序列分別排序。按LSD排序，不必分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實(shí)現(xiàn)排序。2/3/20235410.6.2鏈?zhǔn)交鶖?shù)排序基數(shù)排序一種借助"多關(guān)鍵字排序"的思想來實(shí)現(xiàn)"單邏輯關(guān)鍵字排序"的內(nèi)部排序算法。基數(shù)排序的步驟設(shè)置10個(gè)隊(duì)列，f[i]和e[i]分別為第i個(gè)隊(duì)列的頭指針和尾指針；第一趟分配對(duì)最低位關(guān)鍵字（個(gè)位）進(jìn)行，改變記錄的指針值，將鏈表中記錄分配至10個(gè)鏈隊(duì)列中，每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位相同；第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，重新將10個(gè)隊(duì)列鏈成一個(gè)鏈表；重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別對(duì)十位、百位進(jìn)行，最后得到一個(gè)有序序列。2/3/202355初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：2/3/202356505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：2/3/202357008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二趟收集：穩(wěn)定的排序方法2/3/202358算法評(píng)價(jià)時(shí)間復(fù)雜度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd))其中：n——記錄數(shù)

d——關(guān)鍵字?jǐn)?shù)

rd——關(guān)鍵字取值范圍空間復(fù)雜度：S(n)=2rd個(gè)隊(duì)列指針+n個(gè)指針域空間2/3/20235910.7各種內(nèi)部排序方法的比較討論時(shí)間性能按平均的時(shí)間性能來分，有三類排序方法：時(shí)間復(fù)雜度為O(nlogn)

的方法有：快速排序、堆排序和歸并排序，其中快速排序目前被認(rèn)為是最快的一種排序方法，后兩者之比較，在n值較大的情況下，歸并排序較堆排序更快；時(shí)間復(fù)雜度為O(n2)

的有：插入排序、起泡排序和選擇排序，其中以插入排序?yàn)樽畛Ｓ?，特別是對(duì)于已按關(guān)鍵字基本有序排列的記錄序列尤為如此，選擇排序過程中記錄移動(dòng)次數(shù)最少；時(shí)間復(fù)雜度為O(n)

的排序方法基數(shù)排序。2/3/202360當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)，插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度；而對(duì)于快速排序而言，這是最不好的情況，此時(shí)的時(shí)間性能蛻化為O(n2)，因此應(yīng)盡量避免。選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。以上對(duì)排序的時(shí)間復(fù)雜度的討論主要考慮排序過程中所需進(jìn)行的關(guān)鍵字間的比較次數(shù)，當(dāng)待排序記錄中其它各數(shù)據(jù)項(xiàng)比關(guān)鍵字占有更大的數(shù)據(jù)量時(shí)，還應(yīng)考慮到排序過程中移動(dòng)記錄的操作時(shí)間，有時(shí)這種操作的時(shí)間在整個(gè)排序過程中占的比例更大，從這個(gè)觀點(diǎn)考慮，簡(jiǎn)單排序的