《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版)第十章內(nèi)部排序課件

10.1概述10.2插入排序10.3快速排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種排序方法的綜合比較第十章內(nèi)部排序*10.1概述10.2插入排序10.3快速排序101.了解排序的定義和各種排序方法的特點(diǎn)。2.熟悉各種方法的排序過(guò)程及其依據(jù)的原則。3.

掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。能從“關(guān)鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時(shí)間性能。4.理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。學(xué)習(xí)提要：*1.了解排序的定義和各種排序方法的特點(diǎn)。學(xué)習(xí)提要：*重難點(diǎn)內(nèi)容：直接插入排序、折半插入排序、起泡排序、簡(jiǎn)單選擇排序等排序方法的算法思想、實(shí)現(xiàn)和效率分析。希爾排序、快速排序、堆排序、歸并排序等高效方法。*重難點(diǎn)內(nèi)容：*10.1概述一、什么是排序三、內(nèi)部排序的方法二、內(nèi)部排序和外部排序*10.1概述一、什么是排序三、內(nèi)部排序的方法二、內(nèi)部排序和一、什么是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將下列關(guān)鍵字序列52,49,80,36,14,58,61,23,97,75調(diào)整為14,23,36,49,52,58,61,75,80,97*一、什么是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的一般情況下，假設(shè)含n個(gè)記錄的序列為{R1,R2,…，Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系：

Kp1≤Kp2≤…≤Kpn按此固有關(guān)系將上式記錄序列重新排列為{Rp1,Rp2,…，Rpn}的操作稱作排序。*一般情況下，這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們假設(shè)Ki=Kj(1≤i,j≤n,i≠j)，且在排序前的序列中Ri領(lǐng)先于Rj（即i<j）。若排序后的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；反之，若可能排序后的序列中Rj領(lǐng)先于Ri，則稱使用的排序方法是不穩(wěn)定的。*假設(shè)Ki=Kj(1≤i,j≤n,i≠j)，且在排例如：（14,36,49,

49,52,80）排序后（52,49,80,36,14,49）排序前（14,36,49,49,52,80）穩(wěn)定不穩(wěn)定*例如：（14,36,49,49,52,80）排序后二、內(nèi)部排序和外部排序若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成，則稱此類(lèi)排序問(wèn)題為內(nèi)部排序；

反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過(guò)程不可能在內(nèi)存中完成，則稱此類(lèi)排序問(wèn)題為外部排序。*二、內(nèi)部排序和外部排序若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成三、內(nèi)部排序的方法

內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過(guò)程。經(jīng)過(guò)一趟排序有序序列區(qū)無(wú)序序列區(qū)有序序列區(qū)無(wú)序序列區(qū)*三、內(nèi)部排序的方法內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大經(jīng)過(guò)一趟排基于不同的“擴(kuò)大”

有序序列長(zhǎng)度的方法，內(nèi)部排序方法大致可分下列幾種類(lèi)型：插入類(lèi)交換類(lèi)選擇類(lèi)歸并類(lèi)其它方法*基于不同的“擴(kuò)大”有序序列長(zhǎng)度的方法，內(nèi)部排序方法大致可1.插入類(lèi)

將無(wú)序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序序列中，從而增加記錄的有序子序列的長(zhǎng)度。*1.插入類(lèi)將無(wú)序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序2.交換類(lèi)通過(guò)“交換”無(wú)序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長(zhǎng)度。*2.交換類(lèi)通過(guò)“交換”無(wú)序序列中的記錄從而得到其中關(guān)鍵3.選擇類(lèi)從記錄的無(wú)序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長(zhǎng)度。*3.選擇類(lèi)從記錄的無(wú)序子序列中“選擇”關(guān)鍵字最小或最大4.歸并類(lèi)通過(guò)“歸并”兩個(gè)或兩個(gè)以上的記錄有序子序列，逐步增加記錄有序序列的長(zhǎng)度。5.其它方法*4.歸并類(lèi)通過(guò)“歸并”兩個(gè)或兩個(gè)以上的記錄有序子序列，逐待排記錄的數(shù)據(jù)類(lèi)型定義如下:#defineMAXSIZE1000

//待排順序表最大長(zhǎng)度typedefintKeyType;

//關(guān)鍵字類(lèi)型為整數(shù)類(lèi)型typedefstruct{KeyTypekey;//關(guān)鍵字項(xiàng)InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RcdType;//記錄類(lèi)型typedefstruct{RcdTyper[MAXSIZE+1];//r[0]閑置intlength;//順序表長(zhǎng)度}SqList;//順序表類(lèi)型*待排記錄的數(shù)據(jù)類(lèi)型定義如下:#defineMAXSIZE10.2插入排序一、直接插入排序三、表插入排序二、折半插入排序四、希爾（Shell）排序*10.2插入排序一、直接插入排序三、表插入排序二、折半插入有序序列R[1..i-1]R[i]無(wú)序序列R[i..n]一趟插入排序的基本思想：有序序列R[1..i]無(wú)序序列R[i+1..n]*有序序列R[1..i-1]R[i]無(wú)序序列R[i..n]一實(shí)現(xiàn)“一趟插入排序”可分三步進(jìn)行：3．將R[i]插入(復(fù)制)到R[j+1]的位置上。2．將R[j+1..i-1]中的所有記錄均后移一個(gè)位置；1．在R[1..i-1]中查找R[i]的插入位置，R[1..j].keyR[i].key<R[j+1..i-1].key；*實(shí)現(xiàn)“一趟插入排序”可分三步進(jìn)行：3．將R[i]插入(復(fù)制一、直接插入排序

利用

“順序查找”實(shí)現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”算法的實(shí)現(xiàn)要點(diǎn)：*一、直接插入排序利用“順序查找”實(shí)現(xiàn)算法的實(shí)現(xiàn)要點(diǎn)：*從R[i-1]起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在R[0]；R[0]=R[i];//設(shè)置“哨兵”循環(huán)結(jié)束表明R[i]的插入位置為j+1R[0]jR[i]for(j=i-1;R[0].key<R[j].key;--j);//從后往前找j=i-1插入位置*從R[i-1]起向前進(jìn)行順序查找，監(jiān)對(duì)于在查找過(guò)程中找到的那些關(guān)鍵字不小于R[i].key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；for(j=i-1;R[0].key<R[j].key;--j);

R[j+1]=R[j]R[0]jR[i]j=i-1上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”插入位置*對(duì)于在查找過(guò)程中找到的那些關(guān)鍵字不小于R[i].k第三趟排序后：（38，49，56）40，95例：待排序序列（56，38，49，40，95）jijj404038495695key013245R564940第四趟排序后：（38，40，49，56）95*第三趟排序后：（38，49，56）40，95例：待排序序列令i=2，3，…,n,實(shí)現(xiàn)整個(gè)序列的排序。for(i=2;i<=n;++i)

if

(R[i].key<R[i-1].key)

{

在

R[1..i-1]中查找R[i]的插入位置;插入R[i];

}*令i=2，3，…,n,for(i=2;i<voidInsertionSort(SqList&L){//對(duì)順序表L作直接插入排序。

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

}}//InsertSortL.r[0]=L.r[i];//復(fù)制為監(jiān)視哨L.r[i]=L.r[i-1];for(j=i-2;L.r[0].key<L.r[j].key;--j)L.r[j+1]=L.r[j];

//記錄后移L.r[j+1]=L.r[0];//插入到正確位置*voidInsertionSort(SqList&L內(nèi)部排序的時(shí)間分析：實(shí)現(xiàn)內(nèi)部排序的基本操作有兩個(gè)：（2）“移動(dòng)”記錄。（1）“比較”序列中兩個(gè)關(guān)鍵字的大??；*內(nèi)部排序的時(shí)間分析：實(shí)現(xiàn)內(nèi)部排序的基本操作有兩個(gè)：（2）“移對(duì)于直接插入排序：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：T(n)=O(n2)穩(wěn)定的*對(duì)于直接插入排序：最好的情況（關(guān)鍵字在記錄序列中順序有序）：

因?yàn)镽[1..i-1]是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R[1..i-1]中查找R[i]的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判?。二、折半插入排?因?yàn)镽[1..i-1]是一個(gè)按關(guān)鍵字有序voidBiInsertionSort(SqList&L){}//BInsertSort在L.r[1..i-1]中折半查找插入位置；for(i=2;i<=L.length;++i){}//forL.r[0]=L.r[i];//將L.r[i]暫存到L.r[0]for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//記錄后移L.r[high+1]=L.r[0];//插入*voidBiInsertionSort(SqListlow=1;high=i-1;while

(low<=high)

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

(L.r[0].key<L.r[m].key)high=m-1;//插入點(diǎn)在低半?yún)^(qū)elselow=m+1;//插入點(diǎn)在高半?yún)^(qū)*low=1;high=i-1;m=(lowilowhighmmlowlowmhighilowhighmhighmhighmlow例如:再如:插入位置插入位置14364952805861239775L.r14364952586180239775L.r*ilowhighmmlowlowmhighilowhighm折半插入排序時(shí)間分析：時(shí)間復(fù)雜度：折半插入排序比直接插入排序明顯地減少了關(guān)鍵字間的“比較”次數(shù)，但記錄“移動(dòng)”的次數(shù)不變。T(n)=O(n2)空間復(fù)雜度：S(n)=O(1)穩(wěn)定的*折半插入排序時(shí)間分析：時(shí)間復(fù)雜度：穩(wěn)定的*三、表插入排序?yàn)榱藴p少在排序過(guò)程中進(jìn)行的“移動(dòng)”記錄的操作，必須改變排序過(guò)程中采用的存儲(chǔ)結(jié)構(gòu)。利用靜態(tài)鏈表進(jìn)行排序，并在排序完成之后，一次性地調(diào)整各個(gè)記錄相互之間的位置，即將每個(gè)記錄都調(diào)整到它們所應(yīng)該在的位置上。*三、表插入排序?yàn)榱藴p少在排序過(guò)程中進(jìn)行的*#defineSIZE100//靜態(tài)鏈表容量Typedefstruct{//表結(jié)點(diǎn)類(lèi)型RcdTyperc;//記錄項(xiàng)intnext;//指針項(xiàng)}SLNode;Typedefstruct{//靜態(tài)鏈表類(lèi)型SLNoder[SIZE];//0號(hào)單元為表頭結(jié)點(diǎn)

intlength;//鏈表當(dāng)前長(zhǎng)度}SLinkListType;例如：*#defineSIZE100voidLInsertionSort(ElemSL[]，intn){//對(duì)記錄序列SL[1..n]作表插入排序SL[0].key=MAXINT;SL[0].next=1;SL[1].next=0;

for(i=2;i<=n;++i)for(j=0,k=SL[0].next;SL[k].key<=

SL[i].key;j=k,k=SL[k].next)

{SL[j].next=i;SL[i].next=k;

}//結(jié)點(diǎn)i插入在結(jié)點(diǎn)j和結(jié)點(diǎn)k之間}//LinsertionSort*voidLInsertionSort(ElemSL[算法中使用了三個(gè)指針：其中：p指示第i個(gè)記錄的當(dāng)前位置

i指示第i個(gè)記錄應(yīng)在的位置

q指示第i+1個(gè)記錄的當(dāng)前位置如何在排序之后調(diào)整記錄序列？例如：*算法中使用了三個(gè)指針：如何在排序之后調(diào)整記錄序列？例如：*voidArrange(SLinkListType&SL,intn){p=SL.r[0].next;//p指示第一個(gè)記錄的當(dāng)前位置

for(i=1;i<n;++i){

while(p<i)p=SL.r[p].next;

q=SL.r[p].next;

//q指示尚未調(diào)整的表尾

if(p!=i){

SL.r[p]←→SL.r[i];

//交換記錄，使第i個(gè)記錄到位

SL.r[i].next=p;

//指向被移走的記錄}p=q;

//p指示尚未調(diào)整的表尾，

//為找第i+1個(gè)記錄作準(zhǔn)備

}}//Arrange*voidArrange(SLinkListType&表插入排序時(shí)間分析：從表插入排序的過(guò)程可見(jiàn)，它的基本操作仍是將一個(gè)記錄插入到已排好序的有序表中。和直接插入排序相比，不同之處是用修改2n次指針值代替移動(dòng)記錄，但比較次數(shù)相同。T(n)=O(n2)

重排記錄的過(guò)程，最壞的情況是每個(gè)記錄到位都必須進(jìn)行一次交換，即移動(dòng)3(n-1)次。穩(wěn)定的*表插入排序時(shí)間分析：從表插入排序的過(guò)程可見(jiàn)，它的

四、希爾排序（又稱縮小增量排序）基本思想：對(duì)待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。具體做法為：*四、希爾排序（又稱縮小增量排序）基本思想：對(duì)待排記錄將記錄序列分成若干子序列，分別對(duì)每個(gè)子序列進(jìn)行插入排序。其中，d

稱為增量，它的值在排序過(guò)程中從大到小逐漸縮小，直至最后一趟排序減為1。例如：將n個(gè)記錄分成d個(gè)子序列：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}*將記錄序列分成若干子序列，分別對(duì)每個(gè)子序列進(jìn)行插162512304711233691831

例如：

第一趟希爾排序，設(shè)增量d=51123

12

9

181625

36

304731

第二趟希爾排序，設(shè)增量d=3918

121123

162531

304736第三趟希爾排序，設(shè)增量d=1

9111216182325303136471234567891011*16251230471123369voidShellInsert(SqList&L,intdk){

for(i=dk+1;i<=n;++i)

if(L.r[i].key<L.r[i-dk].key){

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

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}//ShellInsert*voidShellInsert(SqList&L,voidShellSort(SqList&L,intdlta[],intt){//增量為dlta[]的希爾排序

for(k=0;k<t;++t)ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}//ShellSort*voidShellSort(SqList&L,int例4938659776132748554#defineT3intdlta[]={5,3,1};ji49133827一趟排序：1327485544938659776jiji274jiji55ji38jijiji二趟排序：13

4

48

38

27

49

55

65

97

76jiji6548ji9755ji764

12345678910*例493865977613希爾排序時(shí)間分析：希爾排序的時(shí)間是所取“增量”序列的函數(shù)。T(n)=O(n1.3)增量序列取法：

沒(méi)有除1以外的公因子，最后一個(gè)增量值必須為1。不穩(wěn)定的*希爾排序時(shí)間分析：希爾排序的時(shí)間是所取“增量”序10.3快速排序一、起泡排序三、快速排序二、一趟快速排序*10.3快速排序一、起泡排序三、快速排序二、一趟快速排序*一、起泡排序

假設(shè)在排序過(guò)程中，記錄序列R[1..n]的狀態(tài)為：第i趟起泡排序無(wú)序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1無(wú)序序列R[1..n-i]有序序列R[n-i+1..n]比較相鄰記錄，將關(guān)鍵字最大的記錄交換到n-i+1的位置上*一、起泡排序假設(shè)在排序過(guò)程中，記錄序列R[1..n]的狀例4938659776132730初始關(guān)鍵字3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟132730第六趟38497697139727973097137676762730136527653065131349493049273827383038*例49386597761voidbubble_sort(SqList&L,intn){

for(i=n;i>1&&flag=1;--i){flag=0;

for(j=1;j<i;j++)

if(L.r[j].key>L.r[j+1].key){flag=1;x=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=x;}}}結(jié)束條件為:最后一趟沒(méi)有進(jìn)行“交換記錄”。*voidbubble_sort(SqList&L,in起泡排序時(shí)間分析:最好的情況（關(guān)鍵字在記錄序列中順序有序）：只需進(jìn)行一趟起泡“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：需進(jìn)行n-1趟起泡“比較”的次數(shù)：0“移動(dòng)”的次數(shù)：“移動(dòng)”的次數(shù)：n-1穩(wěn)定的*起泡排序時(shí)間分析:最好的情況（關(guān)鍵字在記錄序列中順序有序）：從起泡排序的過(guò)程可見(jiàn)，起泡排序是一個(gè)增加有序序列長(zhǎng)度的過(guò)程，也是一個(gè)縮小無(wú)序序列長(zhǎng)度的過(guò)程，每經(jīng)過(guò)一趟起泡，無(wú)序序列的長(zhǎng)度只縮小1。

試設(shè)想，若能在經(jīng)過(guò)一趟排序，使無(wú)序序列的長(zhǎng)度縮小一半，則必能加快排序的速度。*從起泡排序的過(guò)程可見(jiàn)，起泡排序是一個(gè)增加有序序列長(zhǎng)度的二、一趟快速排序（一次劃分）目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字小于樞軸的記錄均移動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動(dòng)至該記錄之后。致使一趟排序之后，記錄的無(wú)序序列L.r[s..t]將分割成兩部分:L.r

[s..i-1]和L.r

[i+1..t]，且L.r[j].key≤L.r

[i].key≤L.r

[j].key(s≤j≤i-1)

樞軸

(i+1≤j≤t)。*二、一趟快速排序（一次劃分）目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作p例初始關(guān)鍵字：4938659776132750lhh完成一趟排序：(273813)49(76976550)分別進(jìn)行快速排序:(13)27(38)49(5065)76(97)快速排序結(jié)束：13273849

506576974927lll4965h1349h4997h*p例初始關(guān)鍵字：49386intPartition(SqList&L,intlow,inthigh){pivotkey=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[low]←→L.r[high];

}

returnlow;//返回樞軸所在位置}//Partition*intPartition(SqList&L,intintPartition(SqList&L,intlow,inthigh){}//Partition

L.r[0]=L.r[low];pivotkey=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;*intPartition(SqList&L,int三、快速排序首先對(duì)無(wú)序的記錄序列進(jìn)行“一次劃分”，之后分別對(duì)分割所得兩個(gè)子序列“遞歸”進(jìn)行快速排序。無(wú)序的記錄序列無(wú)序記錄子序列(1)無(wú)序子序列(2)樞軸一次劃分分別進(jìn)行快速排序*三、快速排序首先對(duì)無(wú)序的記錄序列進(jìn)行“一次劃分”，voidQSort(SqList&L,intlow,inthigh){

//對(duì)順序表L中子序列L.r[low..high]作快速排序

if(low<high){

//長(zhǎng)度大于1

}}//QSortpivotloc=Partition(L,low,high);

//對(duì)L.r[low..high]進(jìn)行一次劃分QSort(L,low,pivotloc-1);

//對(duì)低子序列遞歸排序，pivotloc是樞軸位置QSort(L,pivotloc+1,high);

//對(duì)高子序列遞歸排序*voidQSort(SqList&L,intlovoidQuickSort(SqList&L){

//對(duì)順序表進(jìn)行快速排序QSort(L,1,L.length);}//QuickSort第一次調(diào)用函數(shù)Qsort時(shí)，待排序記錄序列的上、下界分別為1和L.length。*voidQuickSort(SqList&L){快速排序的時(shí)間分析:假設(shè)一次劃分所得樞軸位置i=k，則對(duì)n個(gè)記錄進(jìn)行快排所需時(shí)間：

其中Tpass(n)為對(duì)n個(gè)記錄進(jìn)行一次劃分所需時(shí)間。若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則k取1至n中任意一值的可能性相同。T(n)=Tpass(n)+T(k-1)+T(n-k)*快速排序的時(shí)間分析:假設(shè)一次劃分所得樞軸位置i=k，則設(shè)Tavg(1)≤b則可得結(jié)果：結(jié)論:快速排序的時(shí)間復(fù)雜度為O(nlogn)由此可得快速排序所需時(shí)間的平均值為：不穩(wěn)定的*設(shè)Tavg(1)≤b則可得結(jié)果：結(jié)論:快速排序的時(shí)間復(fù)雜若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判?，其時(shí)間復(fù)雜度為O(n2)。為避免出現(xiàn)這種情況，需在進(jìn)行一次劃分之前，進(jìn)行“予處理”，即：先對(duì)L.r[low].key,L.r[high].key和L.r[(low+high)/2].key，進(jìn)行相互比較，然后取關(guān)鍵字為“三者之中”的記錄為樞軸記錄。*若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟?0.4選擇排序一、簡(jiǎn)單選擇排序三、堆排序二、樹(shù)型選擇排序*10.4選擇排序一、簡(jiǎn)單選擇排序三、堆排序二、樹(shù)型選擇排一、簡(jiǎn)單選擇排序假設(shè)排序過(guò)程中，待排記錄序列的狀態(tài)為：有序序列R[1..i-1]無(wú)序序列R[i..n]第i趟簡(jiǎn)單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R[1..i]無(wú)序序列R[i+1..n]*一、簡(jiǎn)單選擇排序假設(shè)排序過(guò)程中，待排記錄序列的狀態(tài)為：有序序voidSelectSort(SqList&L,intn){

//對(duì)記錄序列R[1..n]作簡(jiǎn)單選擇排序。

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

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

}}//SelectSortj=SelectMinKey(L,i);

//在R[i..n]中選擇關(guān)鍵字最小的記錄if(i!=j)L.r[i]←→L.r[j];

//與第i個(gè)記錄交換*voidSelectSort(SqList&L,in例初始：[49386597761327]jkkkkkkjji=11349一趟：13[386597764927]i=2jjkkkkk2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序結(jié)束：13273849657697*例初始：[493865時(shí)間性能分析：

對(duì)n個(gè)記錄進(jìn)行簡(jiǎn)單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)總計(jì)為：

移動(dòng)記錄的次數(shù)，最小值為0,

最大值為3(n-1)。不穩(wěn)定的*時(shí)間性能分析：對(duì)n個(gè)記錄進(jìn)行簡(jiǎn)單選擇排序，所需進(jìn)行三、堆排序堆是滿足下列性質(zhì)的數(shù)列{k1,k2,…,kn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小頂堆)(大頂堆)*三、堆排序堆是滿足下列性質(zhì)的數(shù)列{k1,k2,…,kn}kik2ik2i+1若將該數(shù)列視作完全二叉樹(shù)，則k2i是ki的左孩子；k2i+1是ki的右孩子。1236276549817355403498例如:是堆14不*kik2ik2i+1若將該數(shù)列視作完全二叉樹(shù)，將無(wú)序序列建成一個(gè)堆，得到關(guān)鍵字最小（或最大）的記錄；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余的n-1個(gè)元素重又建成一個(gè)堆，則可得到n個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列，這個(gè)過(guò)程叫堆排序。

堆排序即是利用堆的特性對(duì)記錄序列進(jìn)行排序的一種排序方法。*將無(wú)序序列建成一個(gè)堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑睦纾航ù箜敹褅98,81,49,73,36,27,40,55,64,12}{12,

81,49,73,36,27,40,55,64,

98

}交換98和12重新調(diào)整為大頂堆{

81,

73,49,64,36,27,40,55,12,98}{40,55,49,73,12,27,98,81,64,36}*例如：建大頂堆{98,81,49,73,36,2（1）如何由一個(gè)無(wú)序序列建成一個(gè)堆？堆排序需解決的兩個(gè)問(wèn)題:（2）如何在輸出堆頂元素之后，調(diào)整剩余元素使之成為一個(gè)新的堆？*（1）如何由一個(gè)無(wú)序序列建成一個(gè)堆？堆排序需解決的兩個(gè)問(wèn)題:輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者（或大者）進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過(guò)程為“篩選”。第二個(gè)問(wèn)題解決方法——篩選:*輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然98814973556412362740例如:是大頂堆1298128173641298比較比較*98814973556412362740例如:是大頂堆129voidHeapAdjust(RcdType&H,int

s,int

m){//已知H.r[s..m]中記錄的關(guān)鍵字除H.r[s]之外均//滿足堆的特征，本函數(shù)自上而下調(diào)整H.r[s]的//關(guān)鍵字，使H.r[s..m]也成為一個(gè)大頂堆。}//HeapAdjustrc=H.r[s];//暫存H.r[s]for

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

{

//j初值指向左孩子

自上而下的篩選過(guò)程;}H.r[s]=rc;//將調(diào)整前的堆頂記錄插入到s位置*voidHeapAdjust(RcdType&H,iif(rc.key>=

H.r[j].key)break;//再作“根”和“子樹(shù)根”之間的比較，//若“>=”成立，則說(shuō)明已找到rc的插//入位置s，不需要繼續(xù)往下調(diào)整H.r[s]=H.r[j];s=j;

//否則記錄上移，尚需繼續(xù)往下調(diào)整if(j<m&&

H.r[j].key<H.r[j+1].key)++j;//左/右“子樹(shù)根”之間先進(jìn)行相互比較//令j指示關(guān)鍵字較大記錄的位置*if(rc.key>=H.r[j].key)b建堆是一個(gè)從下往上進(jìn)行反復(fù)“篩選”的過(guò)程。即從無(wú)序序列的第n/2個(gè)元素（此無(wú)序序列對(duì)應(yīng)的完全二叉樹(shù)的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選。第一個(gè)問(wèn)題（建堆）解決方法：*建堆是一個(gè)從下往上進(jìn)行反復(fù)“篩選”的過(guò)程。即從無(wú)40554973816436122798例如:

排序之前的關(guān)鍵字序列為123681734998817355現(xiàn)在，左/右子樹(shù)都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹(shù)是個(gè)“堆”即可。98494064361227*40554973816436122798例如:排序之前的關(guān)voidHeapSort(HeapType&H){

//對(duì)順序表H進(jìn)行堆排序}//HeapSortfor(i=H.length/2;i>0;--i)

HeapAdjust(H.r,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.r,1,i-1);

//對(duì)H.r[1]進(jìn)行篩選}*voidHeapSort(HeapType&H)堆排序的時(shí)間復(fù)雜度分析：1.對(duì)深度為k的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；3.調(diào)整“堆頂”n-1次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過(guò)

2(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)因此，堆排序的時(shí)間復(fù)雜度為O(nlogn)。2.對(duì)n個(gè)關(guān)鍵字，建成深度為h(=log2n+1)的堆，所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多4n；不穩(wěn)定的*堆排序的時(shí)間復(fù)雜度分析：1.對(duì)深度為k的堆，“篩選”所歸并：將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。10.5歸并排序*歸并：將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰的記錄有序子序列歸并為一個(gè)記錄的有序序列。有序序列R[l..n]有序子序列R[l..m]有序子序列R[m+1..n]這個(gè)操作對(duì)順序表而言，是輕而易舉的。*在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置例:給定待排序序列（49,38,65,97,76,13,27）初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]*例:給定待排序序列（49,38,65,97,76,13,2voidMerge(RcdTypeSR[],RcdType&TR[],

inti,intm,intn){

//將有序的記錄序列SR[i..m]和SR[m+1..n]//歸并為有序的記錄序列TR[i..n]}//Mergefor(j=m+1,k=i;i<=m&&j<=n;++k)

{

//將SR中記錄由小到大地并入TR

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

else

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

}

……

*voidMerge(RcdTypeSR[],RcdTif(i<=m)TR[k..n]=SR[i..m];//將剩余的SR[i..m]復(fù)制到TRif(j<=n)TR[k..n]=SR[j..n];//將剩余的SR[j..n]復(fù)制到TR*if(i<=m)TR[k..n]=SR[i..m];歸并排序的算法：如果記錄無(wú)序序列R[s..t]的兩部分R[s..(s+t)/2]和R[(s+t)/2+1..t]分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個(gè)記錄序列是一個(gè)有序序列。由此，應(yīng)該先分別對(duì)這兩部分進(jìn)行2-路歸并排序。*歸并排序的算法：如果記錄無(wú)序序列R[s..t]的兩部分例如：52,23,80,36,68,14(s=1,t=6)[52,23,80]

[36,68,14][52,23][80][52][23,52][

23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]*例如：52,23,80,36,68,void

Msort(RcdTypeSR[],RcdType&TR1[],ints,intt)

{

//將SR[s..t]歸并排序?yàn)門(mén)R1[s..t]

if(s==t)TR1[s]=SR[s];

else

{}}//Msort……*voidMsort(RcdTypeSR[],m=(s+t)/2;//將SR[s..t]平分為SR[s..m]和SR[m+1..t]Msort(SR,TR2,s,m);//遞歸地將SR[s..m]歸并為有序的TR2[s..m]Msort(SR,TR2,m+1,t);//遞歸地SR[m+1..t]歸并為有序的TR2[m+1..t]Merge(TR2,TR1,s,m,t);//將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]*m=(s+t)/2;Msort(SR,TR2,s,voidMergeSort(SqList&L){//對(duì)順序表L作2-路歸并排序MSort(L.r,L.r,1,L.length);}//MergeSort容易看出，對(duì)n

個(gè)記錄進(jìn)行歸并排序的時(shí)間復(fù)雜度為Ο(nlogn)。即：每一趟歸并的時(shí)間復(fù)雜度為O(n)，總共需進(jìn)行l(wèi)og2n趟。穩(wěn)定的*voidMergeSort(SqList&L){容

基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來(lái)實(shí)現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。10.6.1多關(guān)鍵字的排序10.6.2鏈?zhǔn)交鶖?shù)排序10.6基數(shù)排序*基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來(lái)實(shí)現(xiàn)“單關(guān)鍵字排例:對(duì)52張撲克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A兩個(gè)關(guān)鍵字：花色（<<<）

面值（2<3<……<A）并且“花色”地位高于“面值”。10.6.1多關(guān)鍵字的排序*例:對(duì)52張撲克牌按以下次序排序：10.6.1多關(guān)鍵字

n個(gè)記錄的序列{R1,R2,…，Rn}對(duì)關(guān)鍵字(Ki0,Ki1,…,Kid-1)有序是指：其中:K0被稱為“最主”位關(guān)鍵字Kd-1被稱為“最次”位關(guān)鍵字對(duì)于序列中任意兩個(gè)記錄Ri和Rj(1≤i<j≤n)都滿足下列(字典)有序關(guān)系：

(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)*n個(gè)記錄的序列{R1,R2,…，Rn

先對(duì)K0進(jìn)行排序，并按K0的不同值將記錄序列分成若干子序列之后，分別對(duì)K1進(jìn)行排序，...…，依次類(lèi)推，直至最后對(duì)最次位關(guān)鍵字排序完成為止。一、最高位優(yōu)先(MSD)法*先對(duì)K0進(jìn)行排序，并按K0的不同值將記錄序列分成若

先對(duì)

Kd-1

進(jìn)行排序，然后對(duì)Kd-2

進(jìn)行排序，依次類(lèi)推，直至對(duì)最主位關(guān)鍵字K0排序完成為止。按LSD排序，不必分成子序列，對(duì)每個(gè)關(guān)鍵字都是整個(gè)序列參加排序；并且可不通過(guò)關(guān)鍵字比較，而通過(guò)若干次分配與收集實(shí)現(xiàn)排序。二、最低位優(yōu)先(LSD)法*先對(duì)Kd-1進(jìn)行排序，然后對(duì)Kd-2進(jìn)行排例如:學(xué)生記錄含三個(gè)關(guān)鍵字:系別、班號(hào)和班內(nèi)的序號(hào)，其中以系別為最主位關(guān)鍵字。

無(wú)序序列對(duì)K2排序?qū)1排序?qū)0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18

1,2,152,1,202,3,183,1,203,2,30LSD的排序過(guò)程如下:*例如:學(xué)生記錄含三個(gè)關(guān)鍵字:無(wú)序序列對(duì)K2排序?qū)1排序?qū)?0.6.2鏈?zhǔn)交鶖?shù)排序假如多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的取值范圍相同，則按LSD法進(jìn)行排序時(shí)，可以采用“分配-收集”的方法，其好處是不需要進(jìn)行關(guān)鍵字間的比較。對(duì)于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用這種“分配-收集”的辦法進(jìn)行排序，稱作基數(shù)排序法。*10.6.2鏈?zhǔn)交鶖?shù)排序假如多關(guān)鍵字的記錄序列中，每例如：對(duì)下列這組關(guān)鍵字{209,386,768,185,247,606,230,834,539}首先按其“個(gè)位數(shù)”取值分別為0,1,…,9“分配”成10組，之后按從0至9的順序?qū)⑺鼈儭笆占痹谝黄?；然后按其“十位?shù)”取值分別為0,1,…,9“分配”成10組，之后再按從0至9的順序?qū)⑺鼈儭笆占痹谝黄?；最后按其“百位?shù)”重復(fù)一遍上述操作。*例如：對(duì)下列這組關(guān)鍵字首先按其“個(gè)位數(shù)”取值

在計(jì)算機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，應(yīng)采用鏈表作存儲(chǔ)結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為：

1.待排序記錄以指針相鏈，構(gòu)成一個(gè)鏈表；

2.

“分配”時(shí)，按當(dāng)前“關(guān)鍵字位”所取值，將記錄分配到不同的“鏈隊(duì)列”中，每個(gè)隊(duì)列中記錄的“關(guān)鍵字位”相同；3.“收集”時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大將各隊(duì)列首尾相鏈成一個(gè)鏈表;4.

對(duì)每個(gè)關(guān)鍵字位均重復(fù)2)和3)兩步。*在計(jì)算機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，應(yīng)采用鏈例初始狀態(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一趟收集：*例初始狀態(tài)：278109063930589184505269505008109930063269278083184589二趟收集：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一趟收集：*505008109930063269278083184589008063083109184269278505589930三趟收集：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二趟收集：*008063083109184269278505589930提醒注意：１．“分配”和“收集”的實(shí)際操作僅為修改鏈表中的指針和設(shè)置隊(duì)列的頭、尾指針；２．為查找使用，該鏈表尚需應(yīng)用算法Arrange將它調(diào)整為有序表。*提醒注意：１．“分配”和“收集”的實(shí)際操作僅為修改鏈表中的指

基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+rd))其中：分配為O(n)收集為O(rd)(rd為“基”)

d為“分配-收集”的趟數(shù)

基數(shù)排序時(shí)間分析：*基數(shù)排序的時(shí)間復(fù)雜度為O(d(n+rd))其中：分配為O(10.7各種排序方法的綜合比較一、時(shí)間性能三、排序方法的穩(wěn)定性能二、空間性能四、關(guān)于“排序方法的時(shí)間復(fù)雜度的下限”*10.7各種排序方法的綜合比較一、時(shí)間性能三、排序方法的一、時(shí)間性能1.平均的時(shí)間性能基數(shù)排序時(shí)間復(fù)雜度為O(nlogn)：快速排序、堆排序和歸并排序時(shí)間復(fù)雜度為O(n2)：直接插入排序、起泡排序和簡(jiǎn)單選擇排序時(shí)間復(fù)雜度為O(n):*一、時(shí)間性能1.平均的時(shí)間性能基數(shù)排序時(shí)間復(fù)雜度為O(2.當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)3.

簡(jiǎn)單選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。

直接插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度，

快速排序的時(shí)間性能蛻化為O(n2)。*2.當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)3.簡(jiǎn)單選擇排序、堆二、空間性能指的是排序過(guò)程中所需的輔助空間大小。1.

所有的簡(jiǎn)單排序方法(包括：直接插入、起泡和簡(jiǎn)單選擇)和堆排序的空間復(fù)雜度為O(1)；2.

快速排序?yàn)镺(logn)，為遞歸程序執(zhí)行過(guò)程中，棧所需的輔助空間；*二、空間性能指的是排序過(guò)程中所需的輔助空間大小。1.所有3.

歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n);4.

鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為O(rd)。*3.歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n);三、排序方法的穩(wěn)定性能

2.

當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時(shí)，必須采用穩(wěn)定的排序方法。1.

快速排序、堆排序和希爾排序是不穩(wěn)定的排序方法。

3.

對(duì)于不穩(wěn)定的排序方法，只要能舉出一個(gè)實(shí)例說(shuō)明即可。*三、排序方法的穩(wěn)定性能2.當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)行L四、關(guān)于“排序方法的時(shí)間復(fù)雜度的下限”本章討論的各種排序方法，除基數(shù)排序外，其它方法都是基于“比較關(guān)鍵字”進(jìn)行排序的排序方法?？梢宰C明，這類(lèi)排序法可能達(dá)到的最快的時(shí)間復(fù)雜度為O(nlogn)。(基數(shù)排序不是基于“比較關(guān)鍵字”的排序方法，所以它不受這個(gè)限制。)*四、關(guān)于“排序方法的時(shí)間復(fù)雜度的下限”本章討論的各例如:對(duì)三個(gè)關(guān)鍵字進(jìn)行排序的判定樹(shù)如下：１．樹(shù)上的每一次“比較”都是必要的;２．樹(shù)上的葉子結(jié)點(diǎn)包含所有可能情況。K1<K3K2<K3K3<K1<K2K1<K3K1<K2K2<K3K2<K1<K3K1<K2<K3K3<K2<K1K2<K3<K1K1<K3<K2是是是是是否否否否否*例如:對(duì)三個(gè)關(guān)鍵字進(jìn)行排序的判定樹(shù)如下：１．樹(shù)上的每一

一般情況下，對(duì)n個(gè)關(guān)鍵字進(jìn)行排序，可能得到的結(jié)果有n!種，由于含n!個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)的深度不小于log2(n!)+1,則對(duì)n個(gè)關(guān)鍵字進(jìn)行排序的比較次數(shù)至少是log2(n!)

nlog2n(斯蒂林近似公式)。所以，基于“比較關(guān)鍵字”進(jìn)行排序的排序方法，可能達(dá)到的最快的時(shí)間復(fù)雜度為O(nlogn)。*一般情況下，對(duì)n個(gè)關(guān)鍵字進(jìn)行排序，可能得到第十章作業(yè)10.110.310.1210.1以關(guān)鍵碼序列（503,087,512,061,908,170,897,275,653,426）為例，手工執(zhí)行以下排序算法，寫(xiě)出每一趟排序結(jié)束時(shí)的關(guān)鍵碼狀態(tài)：（1）直接插入排序；（2）希爾排序(增量d[1]=5)；（3）快速排序；（4）堆排序；（5）歸并排序；（6）基數(shù)排序；*第十章作業(yè)10.110.310.1210.1以1.設(shè)關(guān)鍵字序列為{96,83,40,11,67,25}，寫(xiě)出用下列算法排序時(shí)，第一趟結(jié)束時(shí)的狀態(tài)。（1）希爾排序（d1=3）

（2）快速排序（3）歸并排序（4）堆排序*1.設(shè)關(guān)鍵字序列為{96,83,40,11,67,25}，10.3試問(wèn)在10.1題所列各種排序方法中，哪些是穩(wěn)定的？哪些是不穩(wěn)定的？并為每一種不穩(wěn)定的排序方法舉出一個(gè)不穩(wěn)定的實(shí)例。10.12判別以下序列是否為堆（小頂堆或大頂堆）。如果不是，則把它調(diào)整為堆（要求記錄交換次數(shù)最少）。（1）(100,86,48,73,35,39,42,57,66,21)；（2）(12,70,33,65,24,56,48,92,86,33)；*10.3試問(wèn)在10.1題所列各種排序方法中，哪些是穩(wěn)定的？10.1概述10.2插入排序10.3快速排序10.4選擇排序10.5歸并排序10.6基數(shù)排序10.7各種排序方法的綜合比較第十章內(nèi)部排序*10.1概述10.2插入排序10.3快速排序101.了解排序的定義和各種排序方法的特點(diǎn)。2.熟悉各種方法的排序過(guò)程及其依據(jù)的原則。3.

掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。能從“關(guān)鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時(shí)間性能。4.理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。學(xué)習(xí)提要：*1.了解排序的定義和各種排序方法的特點(diǎn)。學(xué)習(xí)提要：*重難點(diǎn)內(nèi)容：直接插入排序、折半插入排序、起泡排序、簡(jiǎn)單選擇排序等排序方法的算法思想、實(shí)現(xiàn)和效率分析。希爾排序、快速排序、堆排序、歸并排序等高效方法。*重難點(diǎn)內(nèi)容：*10.1概述一、什么是排序三、內(nèi)部排序的方法二、內(nèi)部排序和外部排序*10.1概述一、什么是排序三、內(nèi)部排序的方法二、內(nèi)部排序和一、什么是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無(wú)序”的記錄序列調(diào)整為“有序”的記錄序列。例如：將下列關(guān)鍵字序列52,49,80,36,14,58,61,23,97,75調(diào)整為14,23,36,49,52,58,61,75,80,97*一、什么是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的一般情況下，假設(shè)含n個(gè)記錄的序列為{R1,R2,…，Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系：

Kp1≤Kp2≤…≤Kpn按此固有關(guān)系將上式記錄序列重新排列為{Rp1,Rp2,…，Rpn}的操作稱作排序。*一般情況下，這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們假設(shè)Ki=Kj(1≤i,j≤n,i≠j)，且在排序前的序列中Ri領(lǐng)先于Rj（即i<j）。若排序后的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；反之，若可能排序后的序列中Rj領(lǐng)先于Ri，則稱使用的排序方法是不穩(wěn)定的。*假設(shè)Ki=Kj(1≤i,j≤n,i≠j)，且在排例如：（14,36,49,

49,52,80）排序后（52,49,80,36,14,49）排序前（14,36,49,49,52,80）穩(wěn)定不穩(wěn)定*例如：（14,36,49,49,52,80）排序后二、內(nèi)部排序和外部排序若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成，則稱此類(lèi)排序問(wèn)題為內(nèi)部排序；

反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過(guò)程不可能在內(nèi)存中完成，則稱此類(lèi)排序問(wèn)題為外部排序。*二、內(nèi)部排序和外部排序若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成三、內(nèi)部排序的方法

內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過(guò)程。經(jīng)過(guò)一趟排序有序序列區(qū)無(wú)序序列區(qū)有序序列區(qū)無(wú)序序列區(qū)*三、內(nèi)部排序的方法內(nèi)部排序的過(guò)程是一個(gè)逐步擴(kuò)大經(jīng)過(guò)一趟排基于不同的“擴(kuò)大”

有序序列長(zhǎng)度的方法，內(nèi)部排序方法大致可分下列幾種類(lèi)型：插入類(lèi)交換類(lèi)選擇類(lèi)歸并類(lèi)其它方法*基于不同的“擴(kuò)大”有序序列長(zhǎng)度的方法，內(nèi)部排序方法大致可1.插入類(lèi)

將無(wú)序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序序列中，從而增加記錄的有序子序列的長(zhǎng)度。*1.插入類(lèi)將無(wú)序子序列中的一個(gè)或幾個(gè)記錄“插入”到有序2.交換類(lèi)通過(guò)“交換”無(wú)序序列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長(zhǎng)度。*2.交換類(lèi)通過(guò)“交換”無(wú)序序列中的記錄從而得到其中關(guān)鍵3.選擇類(lèi)從記錄的無(wú)序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中，以此方法增加記錄的有序子序列的長(zhǎng)度。*3.選擇類(lèi)從記錄的無(wú)序子序列中“選擇”關(guān)鍵字最小或最大4.歸并類(lèi)通過(guò)“歸并”兩個(gè)或兩個(gè)以上的記錄有序子序列，逐步增加記錄有序序列的長(zhǎng)度。5.其它方法*4.歸并