教案紙（首頁）第1頁第次課學時授課時間_______教學主題排序的定義和相關(guān)概念；插入排序算法；教學要求1、掌握排序的定義和相關(guān)概念。2、掌握插入排序算法，包括直接插入排序、折半插入排序和希爾排序。教學重點直接插入排序、折半插入排序和希爾排序教學難點接插入排序、折半插入排序和希爾排序教學方法講授教學手段多媒體、板書講授要點1、排序的定義和排序的相關(guān)概念。2、直接插入排序算法及其性能分析。3、折半插入排序算法及其性能分析。4、希爾排序算法及其性能分析。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學出版社，嚴蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學內(nèi)容備注與后記什么是"排序"？簡單說，排序是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。例如，將下列記錄序列

{52,49,80,36,14,58,61,23,97,75}

調(diào)整為序列

{14,23,36,49,52,58,61,75,80,97}

一般情況下，對排序的定義為：

假設含有n個記錄的序列為：

{r1,r2,…,rn}(10-1)

它們的關(guān)鍵字相應為

{k1,k2,…,kn}

對式（10-1）的記錄序列進行排序就是要確定序號1，2，…，n的一種排列

p1,p2,…,pn，

使其相應的關(guān)鍵字滿足如下的非遞減（或非遞增）的關(guān)系：

(10-2)

也就是使式(10-1)的記錄序列重新排列成一個按關(guān)鍵字有序的序列

(10-3)

當待排序記錄中的關(guān)鍵字ki(i=1,2,…,n)都不相同時，則任何一個記錄的無序序列經(jīng)排序后得到的結(jié)果是唯一的；反之，若待排序的序列中存在兩個或兩個以上關(guān)鍵字相等的記錄，則排序所得到的結(jié)果不唯一。假設ki=kj(1≤i≤n,1≤j≤n,i≠j)，且在排序前的序列中ri領(lǐng)先于rj(即i<j)。若在排序后的序列中ri仍領(lǐng)先于rj，則稱所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中rj領(lǐng)先于ri，則稱所用的排序方法是不穩(wěn)定的。在某些有特殊要求的應用問題中需要考慮所用排序方法的穩(wěn)定性的問題。

根據(jù)在排序過程中涉及的存儲器不同，可將排序方法分為兩大類：（1）內(nèi)部排序：在排序進行的過程中不使用計算機外部存儲器的排序過程。2）外部排序：在排序進行的過程中需要對外存進行訪問的排序過程。本章僅討論各種內(nèi)部排序的方法。

內(nèi)部排序的過程是一個逐步擴大記錄的"有序序列"區(qū)域的長度的過程。大多數(shù)排序方法在排序過程中將出現(xiàn)如動畫所示"有序"和"無序"兩個區(qū)域，其中有序區(qū)內(nèi)的記錄已按關(guān)鍵字非遞減有序排列，而無序區(qū)內(nèi)為待排記錄，通常稱"使有序區(qū)中記錄數(shù)目增加一個或幾個"的操作過程為"一趟排序"。按何種策略擴大有序區(qū)域?qū)е虏煌呐判蚍椒?。例如在無序區(qū)域中選取一個關(guān)鍵字最小記錄加到有序區(qū)域中的排序方法稱為"選擇類"的排序法，除此之外還有插入類、交換類、歸并類和計數(shù)類等排序方法。本章僅就各類介紹一二個典型算法。

待排序的記錄序列可以用順序表表示，也可以用鏈表表示。直接插入排序

插入排序的準則是，在有序序列中插入新的記錄以達到擴大有序區(qū)的長度的目的。一趟直接插入排序的基本思想則是:在對記錄序列R[1..n]的排序過程中，區(qū)段R[1..i-1]中的記錄已按關(guān)鍵字非遞減的順序排列，將R[i]插入到有序序列R[1..i-1]中，使區(qū)段R[1..i]中的記錄按關(guān)鍵字非遞減順序排列，如右圖所示。

由此實現(xiàn)一趟插入排序的步驟為：

1)在R[1..i-1]中查找R[i]的插入位置，即確定j(0≤j＜i＝使得

R[1..j].key≤R[i].key＜R[j+1..i-1].key

2＝將R[j+1..i-1]中的記錄后移一個位置；

3＝將R[i]插入到j+1的位置。

和9.2.2中討論的順序查找類似，為了避免在查找過程中判別循環(huán)變量是否出界，設置R[0]為監(jiān)視哨，并在查找的同時進行"記錄后移"，如動畫演示所示。

算法10.1

voidInsertPass(SqList&L,inti)

{

//已知L.r[1..i-1]中的記錄已按關(guān)鍵字非遞減的順序有序排列,本算法實

//現(xiàn)將L.r[i]插入其中,并保持L.r[1..i]中記錄按關(guān)鍵字非遞減順序有序

L.r[0]=L.r[i];//復制為哨兵

for(j=i-1;L.r[0].key<L.r[j].key;--j)

L.r[j+1]=L.r[j];//記錄后移

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

}//InsertPass

顯然，只含一個記錄的序列是有序的，因此令i從2起，逐個插入直到n便可實現(xiàn)整個插入排序，算法如下。

算法10.2

voidInsertSort(SqList&L)

{

//對順序表L作直接插入排序

for(i=2;i<=L.length;++i)

if(L.r[i].key<L.r[i-1].key){//將L.r[i]插入有序子表

L.r[0]=L.r[i];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];//插入到正確位置

}//if

}//InsertSortR[1..n]表示記錄序列的長度為n，1..n表示它們的序號(下標)連續(xù)地從1至n。

如果L.r[i].key≥L.r[i-1].key，則L.r[1..r]已經(jīng)有序，不需要再進行查找和插入；反之，若已知L.r[i].key＜L.r[i-1].key，查找插入位置可從i-2開始。直接插入排序的時間復雜度從上述排序過程可見，排序中的兩個基本操作是：（關(guān)鍵字間的）比較和（記錄的）移動。因此排序的時間性能取決于排序過程中這兩個操作的次數(shù)。從直接插入排序的算法可見，這兩個操作的次數(shù)取決于待排記錄序列的狀態(tài)，當待排記錄處于"正序"(即記錄按關(guān)鍵字從小到大的順序排列)的情況時，所需進行的關(guān)鍵字比較和記錄移動的次數(shù)最少，反之，當待排記錄處于"逆序"(即記錄按關(guān)鍵字從大到小的順序排列)的情況時，所需進行的關(guān)鍵字比較和記錄移動的次數(shù)最多，如下表所列。待排記錄序列狀態(tài)"比較"次數(shù)"移動"次數(shù)正序n-10逆序

若待排記錄序列處于隨機狀態(tài)，則可以最壞和最好的情況的平均值作為插入排序的時間性能的量度。一般情況下，直接插入排序的時間復雜度為O(n2)。"移動記錄"的次數(shù)包括監(jiān)視哨的設置。

先分析一趟直接插入排序的情況：

若L.r[i].key≥L.r[i-1].key，只進行"1"次比較，不移動記錄；

若L.r[i].key＜L.r[1].key，需進行"i"次比較，i+1次移動。

整個插入排序的過程中，i從2至n，則得

折半插入排序

由于插入排序的基本思想是在一個有序序列中插入一個新的記錄，則可以利用"折半查找"查詢插入位置，由此得到的插入排序算法為"折半插入排序"。算法如下：

算法10.3

voidBInsertSort(SqList&L)

{

//對順序表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(L.r[0].key<L.r[m].key)}high=m-1;//插入點在低半?yún)^(qū)

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

}//while

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

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

}

}//BInsertSort

但是，折半插入排序只能減少排序過程中關(guān)鍵字比較的時間，并不能減少記錄移動的時間，因此折半插入排序的時間復雜度仍為O(n2)。表插入排序

表插入排序是以靜態(tài)鏈表作待排記錄序列的存儲結(jié)構(gòu)實現(xiàn)的插入排序。這個靜態(tài)鏈表由存儲記錄的順序表和附加的指針數(shù)組構(gòu)成，靜態(tài)鏈表中的指針實際上指的是數(shù)組的下標。

表插入排序分兩步進行：首先構(gòu)造一個有序鏈表；然后按照"附加指針"的指示將結(jié)點中的記錄重新排列成一個有序序列。

先看一個具體的例子。

從例子中可見，構(gòu)成有序鏈表的過程和前面討論的直接插入排序的過程基本相同，先生成一個只含一個記錄的有序鏈表，之后將從第2個至最后一個記錄逐個插入，差別僅在于查找插入位置是從前到后進行查詢直至找到一個記錄的關(guān)鍵字大于當前待插入的記錄的關(guān)鍵字，因此在查詢過程中應該保持一個指"前驅(qū)"結(jié)點的指針。其算法在此不再詳述，請讀者自行補充。

所謂"重排記錄"是將記錄移動到正確位置（即按關(guān)鍵字從小至大有序排列）。在重排的過程中設置了三個指針：其中i指示當前需要"歸位"的記錄的正確位置；p指示該記錄的原始位置；q指示第i+1個記錄（即指針p所指記錄的后繼）的原始位置。顯然，重排的主要操作是互換p和i所指記錄，以便使第i小關(guān)鍵字記錄歸位至正確位置，但由于互換記錄破壞了鏈表的鏈接關(guān)系，可利用和當前已歸位記錄相應的指針予以修補，由于i值從小至大變化，因此第i個記錄當前所在的原始位置p必定大于i，若當前p的值比i小，說明該位置的記錄已被移走，可由相應指針值找到它當前所在位置。算法如下：

算法10.4

voidArrange(SqList&L，intNext[])

{

//根據(jù)Next[]中的指針值調(diào)整記錄位置，使得L中記錄

//按關(guān)鍵字非遞減有序順序排列

p=Next[0];//p指示第一個記錄的當前位置

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

{//SL.r[1..i-1]中記錄已按關(guān)鍵字有序排列，

//第i個記錄在L中的當前位置應不小于i

while(p<i)p=Next[p];//找到第i個記錄，并用p指示其在L中當前位置

q=Next[p];//q指示尚未調(diào)整的后繼記錄

if(p!=i){

L.r[p]←→L.r[i];//交換記錄，使第i個記錄到位

Next[i]=p;//指向被移走的記錄，使得以后可由while循環(huán)找回

}//if

p=q;//p指向下一個將要調(diào)整的記錄

}//for

}//Arrange

容易看出，在重排過程中至多進行3(n-1)次移動記錄，然而整個表插入排序過程也僅僅是減少了移動記錄的時間，所以它的時間復雜度仍為O(n2)。希爾排序

希爾排序又稱"縮小增量排序"，它的基本思想是，先對待排序列進行"宏觀調(diào)整"，待序列中的記錄"基本有序"時再進行直接插入排序。

先看一個具體例子的希爾排序的過程。例如一個含11個關(guān)鍵字的序列(16，25，12，30，47，11，23，36，9，18，31)，先對它進行"增量為5"的插入排序，即分別使(R1,R6,R11)、(R2,R7)、(R3,R8)、(R4,R9)和(R5,R10)為有序序列，然后將增量"縮小到3"，排序結(jié)果使(R1,R4,R7,R10)、(R2,R5,R8,R11)和(R3,R6,R9)分別成為有序序列，此時序列中在關(guān)鍵字18，23，25，31和47之前的關(guān)鍵字均比它們小，即在進行最后一趟排序時這幾個關(guān)鍵字都不需要"往前進行"插入，之后經(jīng)過最后一趟插入排序即得到有序序列。

從上述例子的排序過程可見，由于希爾排序在前幾趟的排序過程中，關(guān)鍵字較大的記錄是"跳躍式"地往后移動，從而使得在進行最后一趟插入排序之前序列中記錄的關(guān)鍵字已基本有序，只需作少量關(guān)鍵字比較和移動記錄，由此減少了整個排序過程中所需進行的"比較"和"移動"的次數(shù)。所謂"基本有序"是指，在序列中的各個關(guān)鍵字之前，只存在少量關(guān)鍵字比它大的記錄。算法10.5

voidShellInsert(SqList&L，intdk)

{

//對順序表L作一趟增量為dk的希爾排序

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

if(L.r[i].key<L.r[i-dk].key){//將L.r[i]插入有序子表

L.r[0]=L.r[i];L.r[i]=L.r[i-dk];

for(j=i-2*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

算法10.6

voidShellSort(SqList&L,intdlta[],intt)

{

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

for(k=0;k<t;++t)

ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序

}//ShellSort

希爾排序的時間復雜度和所取增量序列相關(guān)，例如已有學者證明，當增量序列為2t-k-1(k=0,1,…，t-1)時，希爾排序的時間復雜度為O(n3/2)。希爾排序的增量序列dlta[]可以有多種取法，但必須是，

(1)dlta[]中各值沒有除1之外的公因子；

(2)dlta[t-1]必須為1。

例如，dlta[]=……,9,5,3,2,1

或dlta[]=……,31,15,7,3,1

或dlta[]=……,40,13,4,1等。

第次課學時授課時間______教學主題交換排序算法；選擇排序算法教學要求1、掌握交換排序算法，包括冒泡排序和快速排序。2、掌握選擇排序算法，包括簡單選擇排序和堆排序。教學重點冒泡排序算法、快速排序算法、堆排序算法教學難點冒泡排序算法、快速排序算法、堆排序算法教學方法講授教學手段多媒體、板書講授要點1、冒泡排序算法及其性能分析。2、快速排序算法及其性能分析。3、簡單選擇排序算法及其性能分析。4、堆定義及特點、堆排序算法及其性能分析。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學出版社，嚴蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）第3頁教學內(nèi)容備注與后記交換排序法(快速排序)起泡排序

起泡排序是交換類排序方法中的一種簡單排序方法。其基本思想為：依次比較相鄰兩個記錄的關(guān)鍵字，若和所期望的相反，則互換這兩個記錄。如右圖所示，在第i趟起泡排序之前，區(qū)段R[n-i+2..n]中的記錄已按關(guān)鍵字從小到大有序排列，而區(qū)段R[1..n-i+1]中的記錄不一定有序，但該區(qū)段中所有記錄的關(guān)鍵字均不大于有序序列中記錄的關(guān)鍵字(即小于或等于R[n-i+2].key)，則第i趟起泡排序的操作為，從第1個記錄起，逐個和相鄰記錄的關(guān)鍵字進行比較，若第j(1≤j≤n-i)個記錄的關(guān)鍵字大于第j+1個記錄的關(guān)鍵字，則互換記錄，由此可將區(qū)段R[1..n-i+1]中關(guān)鍵字最大的記錄"交換"到R[n-i+1]的位置上，從而使有序序列的長度增1。顯然，如果第i趟起泡排序的過程中，沒有進行任何記錄的交換，則表明區(qū)段R[1..n-i+1]中的記錄已經(jīng)按關(guān)鍵字從小到大有序排列，由此不再需要進行下一趟的起泡，即起泡排序已經(jīng)完成，可見排序結(jié)束的條件是(i=n-1)或者（第i趟的起泡中沒有進行記錄交換），如算法10.7所示。

算法10.7

voidBubbleSort(SqList&L)

{

//對順序表L作起泡排序

for(i=L.length,change=TRUE;i>1&&change;--i){

change=FALSE;

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

if(L.r[j].key>L.r[j+1].key)

{L.r[j]←→L.r[j+1];change=TRUE}

}//fori

}//BubbleSort

分析起泡排序的時間復雜度：和直接插入相似，排序過程中所進行的"比較"和"移動"操作的次數(shù)取決于待排記錄序列的狀態(tài)，在待排記錄處于"正序"時取最小值，此時只需進行一趟起泡排序，反之，在待排記錄處于"逆序"時取最大值，此時需進行n-1趟起泡，列表如下：待排記錄狀態(tài)"比較"次數(shù)"移動"次數(shù)正序n-10逆序算法中設立了一個標志一趟起泡中是否進行了交換記錄操作的布爾型變量change，在每一趟起泡之前均將它設為"FALSE"，一旦進行記錄交換，則將它改為"TRUE"，因此change=TRUE是進行下一趟起泡的必要條件。當待排序列中的記錄已按關(guān)鍵字有序排列時，顯然，在進行n-1次關(guān)鍵字的比較，而不需要交換記錄；然而，當待排序列中的記錄按關(guān)鍵字逆序排列時，需進行n-1趟起泡，并且每一趟起泡都需進行所有記錄的互換，因此進行的關(guān)鍵字比較的總數(shù)為：

，

進行的記錄移動的總數(shù)為：

。在算法10.7中，經(jīng)過每一趟起泡，待排記錄序列的上界i都只是減1。但實際上，有的時候起泡的上界可以縮減不止1個記錄的位置，例如右側(cè)所示例子。

從這個例子可見，在一趟起泡的過程中，有可能只是在區(qū)段的前端進行記錄的交換，而其后端記錄已經(jīng)按關(guān)鍵字有序排列，由此應在算法中設置一個指示"最后一個進行交換的記錄的位置"的變量。改進后的起泡算法如下：

算法10.8

voidBubbleSort(SqList&L)

{

//對順序表L作起泡排序

i=L.length;

while(i>1){//i>1表明上一趟曾進行過記錄的交換

lastExchangeIndex=1;

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

if(L.r[j+1].key<L.r[j].key){

L.r[j]←→.r[j+1]；//互換記錄

lastExchangeIndex=j;//記下進行交換的記錄的位置

}//if

}//for

i=lastExchangeIndex;

//一趟起泡后仍處于無序狀態(tài)的最后一個記錄的位置

}//while

}//BubbleSort

快速排序

起泡排序是通過一趟"起泡"選定關(guān)鍵字最大的記錄，所有剩余關(guān)鍵字均小于它的記錄繼續(xù)進行排序，快速排序則是通過一趟排序選定一個關(guān)鍵字介于"中間"的記錄，從而使剩余記錄可以分成兩個子序列分別繼續(xù)排序，通常稱該記錄為"樞軸"。如右圖所示，假設一趟快速排序之后樞軸記錄的位置為i，則得到的無序記錄子序列(1)R[s..i-1]中記錄的關(guān)鍵字均小于樞軸記錄的關(guān)鍵字，反之，得到的無序記錄子序列(2)R[i+1..t]中記錄的關(guān)鍵字均大于樞軸記錄的關(guān)鍵字，由此這兩個子序列可分別獨立進行快速排序。

例如，關(guān)鍵字序列(52,49,80,36,14,75,58,97,23,61)

經(jīng)第1趟快速排序之后為(23,49,14,36)52(75,58,97,80,61)

經(jīng)第2趟快速排序之后為(14)23(49,36)52(61,58)75(80,97)

經(jīng)第3趟快速排序之后為(14,23,36,49,52,58,61,75,80,97)

快速排序的算法如下：

算法10.9

voidQSort(RcdTypeR[],ints,intt)

{

//對記錄序列R[s..t]進行快速排序

if(s<t){//長度大于1

pivotloc=Partition(R,s,t);

//對R[s..t]進行一趟快排，并返回樞軸位置

QSort(R,s,pivotloc-1);//對低子序列遞歸進行排序

QSort(R,pivotloc+1,t);//對高子序列遞歸進行排序

}//if

}//Qsort

算法10.10

voidQuickSort(SqList&L)

{

//對順序表L進行快速排序

QSort(L.r,1,L.length);

}//QuickSort

快速排序的算法是一個遞歸函數(shù)，因此算法10.9中必須引入一對參數(shù)s和t作為待排序區(qū)域的上下界。在算法的遞歸調(diào)用過程執(zhí)行中，這兩個參數(shù)隨著"區(qū)域的劃分"而不斷變化。對順序表L進行快速排序調(diào)用算法10.9時，s和t的初值應分別置為1和L.length。一趟快排也稱"一次劃分"，即將待排序列R[s..t]"劃分"為兩個子序列R[s..i-1]和R[i+1..t]，i為一次劃分之后的樞軸位置。可以取待排序列中任何一個記錄作為樞軸，但為方便起見，通常取序列中第一個記錄R[s]為樞軸，以它的關(guān)鍵字作為劃分的依據(jù)。劃分可如下進行：設置兩個指針low和high，分別指向待排序列的低端s和高端t。若R[high].key<R[s].key，則將它移動至樞軸記錄之前；反之，若R[low].key>R[s].key，則將它移動至樞軸記錄之后，并為避免樞軸來回移動，可先將樞軸R[s]暫存在數(shù)組的閑置分量R[0]中。如右側(cè)所示為"一次劃分"過程的一個例子。一次劃分（一趟快速排序）的算法如下：

算法10.11

intPartition(RcdTypeR[],intlow,inthigh)

{

//對記錄子序列R[low..high]進行一趟快速排序，并返回樞軸記錄

//所在位置，使得在它之前的記錄的關(guān)鍵字均不大于它的關(guān)鍵字，

//而在它之后的記錄的關(guān)鍵字均不小于它的關(guān)鍵字

R[0]=R[low];//將樞軸記錄移至數(shù)組的閑置分量

pivotkey=R[low].key;//樞軸記錄關(guān)鍵字

while(low<high){//從表的兩端交替地向中間掃描

while(low<high&&R[high].key>=pivotkey)

--high;

R[low++]=R[high];//將比樞軸記錄小的記錄移到低端

while(low<high&&R[low].key<=pivotkey)

++low;

R[high--]=R[low];//將比樞軸記錄大的記錄移到高端

}//while

R[low]=R[0];//樞軸記錄移到正確位置

returnlow;//返回樞軸位置

}//Partition

可以推證，快速排序的平均時間復雜度為O(nlogn)，在三者取中的前提下，對隨機的關(guān)鍵字序列，快速排序是目前被認為是最好的排序方法，如果借用起泡排序中設置記錄"交換與否"的布爾變量的作法，快速排序也適用于已經(jīng)有序的記錄序列。選擇排序法簡單選擇排序

選擇排序的基本思想是，在待排區(qū)段的記錄序列中選出關(guān)鍵字最大或最小的記錄，并將它移動到法定位置。第i(i=1,2,…,n-1)趟的簡單選擇排序（序列中前i-1個記錄的關(guān)鍵字均小于后n-i+1個記錄的關(guān)鍵字）的作法是，在后n-i+1個記錄中選出關(guān)鍵字最小的記錄，并將它和第i個記錄進行互換。如右圖所示。

算法10.12

voidSelectSort(SqList&L)

{

//對順序表L作簡單選擇排序

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(L.r[k].key<L.r[j].key)j=k;

if(i!=j)L.r[j]←→L.r[i];//與第i個記錄互換

}//for

}//SelectSort

無論待排序列處于什么狀態(tài)，選擇排序所需進行的"比較"次數(shù)都相同，為，而"移動"次數(shù)在待排序列為"正序"時達最小為0，在"逆序"時達最大為3(n-1)。堆排序

何謂"堆"？

若含n個元素的序列{K1,K2,…,Kn}滿足下列關(guān)系則稱作"小頂堆"或"大頂堆"。"堆頂"元素為序列中的"最小值"或"最大值"。

例如，{12,39,20,65,47,34,98,81,73,56}為"小頂堆"；

{98,81,34,73,56,12,20,39,65,47}為"大頂堆"。

若將上述數(shù)列視作為一個完全二叉樹，則堆頂元素即為二叉樹的根結(jié)點，和分別為ki的"左子樹根"和"右子樹根"，如右圖所示。

利用堆的特性進行的排序方法即為"堆排序"，其排序過程如下：

假設待排關(guān)鍵字序列為：{34,39,20,65,47,12,98,73,81,56}

1）先將它調(diào)整為大頂堆：{98,81,34,73,56,12,20,39,65,47}

2）互換"堆頂"和待排序列中

的最后的關(guān)鍵字：{47,81,34,73,56,12,20,39,65,98}

3）在待排序列中舍去最大關(guān)鍵字，將其余部

分重新調(diào)整為堆：{81,73,34,65,56,12,20,39,47}98

4）重復2）和3）直至待排序列中只剩一個關(guān)鍵字為止。

可見，堆排序的兩個關(guān)鍵問題是：

1）如何將一個無序序列調(diào)整為堆？

2）如何在互換堆頂之后重新調(diào)整為堆？"堆排序"也是一種選擇類的排序方法，每一趟從記錄的無序序列中選出一個關(guān)鍵字最大或最小的記錄，和簡單選擇所不同的是，在第一趟選最大或最小關(guān)鍵字記錄時先"建堆"，從而減少之后選擇次大或次小關(guān)鍵字等一系列記錄時所需的比較和移動次數(shù)。

如上所述，已知關(guān)鍵字序列{98,81,34,73,56,12,20,39,65,47}是大頂堆，當將"98"和"47"互換之后，它就不再是個堆。但此時"98"已是選出的最大關(guān)鍵字，不需要再參加排序，由此只要對其余關(guān)鍵字進行排序，如果能將它重新調(diào)整為一個大頂堆，這就等于選出了第二個最大關(guān)鍵字。而此時的關(guān)鍵字序列有下列特點：如圖二叉樹所示，除"根結(jié)點"之外，其"左子樹"和"右子樹"都仍然是堆。由此只要"從上到下"進行"篩選"可將該序列重新調(diào)整為大頂堆。

首先將"47"移至暫存空間R[0]，將"81"和"34"進行比較后得到的"大者"與"47"進行比較，由于81>47，則應將"81"移至根結(jié)點的位置，之后將"73"和"56"進行比較后得到的"大者"與"47"進行比較，同樣因為73>47，將"73"上移，同理需將"65"移至它的雙親位置，而將"47"移至它原來的位置(因為此時已達葉子結(jié)點，無孩子結(jié)點可比較)。由此得到一個新的大頂堆，選出第2個最大關(guān)鍵字"81"，之后類似地在互換"81"和"47"之后，進行從上到下的篩選可選出第3個最大關(guān)鍵字"73"，依次類推直至只剩下一個關(guān)鍵字為止。從上到下的"篩選"算法如下所示：

算法10.13

voidHeapAdjust(SqList&H,ints,intm)

{

//已知H.r[s..m]中記錄的關(guān)鍵字除H.r[s].key之外均滿足堆的定義，

//本函數(shù)依據(jù)關(guān)鍵字的大小對H.r[s]進行調(diào)整，使H.r[s..m]成為一

//個大頂堆（對其中記錄的關(guān)鍵字而言）

H.r[0]=H.r[s];//暫存根結(jié)點的記錄

for(j=2*s;j<=m;j*=2){//沿關(guān)鍵字較大的孩子結(jié)點向下篩選

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

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

if(H.r[0].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]=H.r[0];//回移篩選下來的記錄

}//HeapAdjust

如何"建堆"？

建堆的過程是一個"從下到上"調(diào)整堆的過程。顯然，葉子結(jié)點是個堆，對記錄無序系列中"最后一個"分支結(jié)點而言，滿足篩選的前提，即除根結(jié)點之外，其左、右子樹都是堆，由此可調(diào)用算法10.13將它調(diào)整為一個堆。類似地，"從后往前"看每個記錄都滿足篩選的前提，依次進行調(diào)整直至對以第1個記錄為根的"二叉樹"進行篩選之后，整個記錄序列就是一個大頂堆了。例如右側(cè)動畫所示為對前述記錄無序序列進行建堆的過程。

算法10.14

voidHeapSort(SqList&H)

{

//對順序表H進行堆排序

for(i=H.length/2;i>0;--i)//將H.r[1..H.length]建成大頂堆

HeapAdjust(H,i,H.length);

H.r[1]←→H.r[H.length];//互換"堆頂"和"堆底"的記錄

for(i=H.length-1;i>1;--i){

HeapAdjust(H,1,i);//從根開始調(diào)整，將H.r[1..i]重新調(diào)整為大頂堆

H.r[1]←→H.r[i];

//互換"堆頂"和當前的"堆底"，使已有序的記錄沉積在底部

}//for

}//HeapSort

可以證明，堆排序的時間復雜度為O(nlogn)。和選擇排序雷同，無論待排序列中的記錄是正序還是逆序排列，都不會使堆排序處于"最好"或"最壞"的狀態(tài)。第次課學時授課時間________教學主題歸并排序算法；基數(shù)排序算法；各種內(nèi)排序方法性能分析和應用教學要求1、掌握歸并排序算法，包括二路歸并排序。2、掌握基數(shù)排序算法，包括最低位優(yōu)先和最高位優(yōu)先排序。3、掌握各種內(nèi)排序方法的性能分析和比較。教學重點歸并排序算法；基數(shù)排序算法；各種內(nèi)排序方法性能分析和應用教學難點二路歸并算法；基數(shù)排序算法；各種內(nèi)排序方法性能分析和應用教學方法講授、練習教學手段多媒體、板書、上機實操講授要點1、歸并排序的特點和過程。2、二路歸并排序算法及其性能分析。3、基數(shù)排序的特點和過程。4、基數(shù)排序算法及其性能分析。5、各種內(nèi)排序方法性能分析和應用。作業(yè)參考資料教材：數(shù)據(jù)結(jié)構(gòu)教程（第5版），清華大學出版社，李春葆等2017。參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言），清華大學出版社，嚴蔚敏吳偉民編著。注：本頁為每次課教案首頁教案紙（續(xù)頁）教學內(nèi)容備注與后記2-路歸并排序

歸并排序的基本操作是將兩個或兩個以上的記錄有序序列歸并為一個有序序列。最簡單的情況是，只含一個記錄的序列顯然是個有序序列，經(jīng)過"逐趟歸并"使整個序列中的有序子序列的長度逐趟增大，直至整個記錄序列為有序序列止。

2-路歸并排序則是歸并排序中的一種最簡單的情況，它的基本操作是將兩個相鄰的有序子序列"歸并"為一個有序序列，如右側(cè)所示。這個操作對順序表而言是極其容易實現(xiàn)的，只要依關(guān)鍵字從小到大進行"復制"即可，如下算法所示。

算法10.15

voidMerge(RcdTypeSR[],RcdTypeTR[],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)鍵字從小到大地復制到TR中

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

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

}

while(i<=m)TR[k++]=SR[i++];//將剩余的SR[i..m]復制到TR

while(j<=n)TR[k++]=SR[j++];//將剩余的SR[j..n]復制到TR

}//Merge

容易看出，2-路歸并排序的時間復雜度為O(nlogn)?；鶖?shù)排序多關(guān)鍵字的排序

一般情況下，對多關(guān)鍵字排序的定義為：

假設含有n個記錄的序列為：

(R1,R2….,Rn)

每個記錄Ri中含有d個關(guān)鍵字，則稱該記錄序列對關(guān)鍵字有序是指：對于序列中任意兩個記錄Ri和Rj（1≤i<j≤n）都滿足下列有序關(guān)系：

其中K0被稱作最主位關(guān)鍵字，Kd-1被稱作最次位關(guān)鍵字。

通常實現(xiàn)多關(guān)鍵字排序可以有兩種策略：一是最主位優(yōu)先（MSD法），另一是最次位優(yōu)先（LSD法）。

最主位優(yōu)先的作法是：先對最主位關(guān)鍵字K0進行排序，得到若干子序列，其中每個子序列中的記錄都含相同的K0值，之后分別就每個子序列對關(guān)鍵字K1進行排序，致使K1值相同的記錄構(gòu)成長度更短的子序列，依次重復，直至就當前得到的各個子序列對Kd-2進行排序之后得到的每個子序列中都具有相同的關(guān)鍵字，分別對這些子序列按Kd-1從小到大進行排序，最后由這些子序列依次相連所得序列便是排序的最后結(jié)果，即對關(guān)鍵字有序。最次位優(yōu)先的作法是，在繼續(xù)對"前一位"排序時不需要將當前所得對其后一位有序的序列分割成若干子序列進行，而是整個序列依次對Kd-1、對Kd-2直至對K0進行排序即可.基數(shù)排序的兩種實現(xiàn)方法

實現(xiàn)基數(shù)排序可以有兩種不同算法。

一、鏈式基數(shù)排序

類似于表插入排序，附設指針數(shù)組將順序表視作一個"靜態(tài)鏈表"，利用"修改指針"實現(xiàn)分配和收集。同時設置rd個隊列的頭指針和尾指針，分別指示各隊列的"頭結(jié)點"和"尾結(jié)點"在鏈表中的位置。

首先初始化空隊列，即將每個隊列的頭指針front[i]和尾指針rear[i]均設為"0"；"分配"時將記錄"插入"隊列，若隊列為空，則僅需修改隊列的頭、尾指針，令它們指向該插入記錄，否則在修改隊列的尾指針的同時尚需修改當前隊尾記錄的指針；"收集"時依次頭尾相接地鏈接各非空隊列所指記錄，即改變各非空隊列尾指針所指記錄的指針，令它們指向"下一"非空隊列頭指針所指記錄，最后一個非空隊列尾指針所指記錄的指針應為"空"。

在描述基數(shù)排序的算法之前，尚需重新定義記錄和順序表類型：

constMAX_NUM_OF_KEY=8;

//關(guān)鍵字項數(shù)的最大值，暫定為8

constRADIX=10;

//關(guān)鍵字基數(shù)，此為十進制整數(shù)的基數(shù)

typedefstruct{

KeysTypekeys[MAX_NUM_OF_KEY];//關(guān)鍵字

InfoTypeotheritems;//其它數(shù)據(jù)項

}RcdType;//基數(shù)排序中的記錄類型

typedefstruct{

RcdTyper[MAXSIZE+1];

intlength;//順序表長度

intbitsnum;//關(guān)鍵字位數(shù)

}SqList;//順序表類型

分析鏈式基數(shù)排序的時間復雜度：假設n為記錄個數(shù)，rd為基數(shù)值，d為構(gòu)成邏輯關(guān)鍵字的關(guān)鍵字位數(shù)。由于每一趟的"分配"都是對全部記錄處理一遍，因此它的時間復雜度是O(n)，而每一趟的"收集"只是巡查一遍隊列，依次將各非空隊列的隊尾指針所指結(jié)點鏈接到下一個非空隊列的隊頭指針所指結(jié)點，因此它的時間復雜度是O(rd)，因此一趟分配和收集的時間復雜度為O(n+rd)，對每一位關(guān)鍵字進行一趟分配和收集，因此總的時間復雜度為O(d(n+rd))，一般情況下，相比n而言，rd要小得多，因此可簡寫為O(dn)。換句話說，當待排序序列中的記錄數(shù)量很大，而邏輯關(guān)鍵字的"位數(shù)"較小，此時用基數(shù)排序法進行排序?qū)⒈瓤焖倥判虻男矢?。二、利?計數(shù)"和"復制"的方法實現(xiàn)的基數(shù)排序算法

由于在排序的過程中利用了"計數(shù)"策略，故在此稱它為"計數(shù)基數(shù)排序"，其算法如下所示。

算法10.21

voidRadixSort(SqList&L)

{

//對順序表L進行基數(shù)排序

RcdTypeC[L.length+1];//開設同等大小的輔助空間用于復制數(shù)據(jù)

i=bitsnum-1;

while(i>=0){

RadixPass(L.r,C,L.length,i);

//對L.r進行一趟基數(shù)排序，排序結(jié)果存入C

i--;

if(i>=0){

RadixPass(C,L.r,L.length,i);

//對C進行一趟基數(shù)排序，排序結(jié)果存入L.r

i--;

}//if

else

for(j=1;j<=L.l