數據結構教案第九章

1、精選文檔課程名稱數據結構教學對象新華軟工專業(yè)教 材數據結構（C語言）授課內容第九章 排序 課 時2教學目的與要求深刻理解排序的定義和各種方法的特點，并加以靈活應用。了解各種方法的排序過程及其依據的原則?；凇瓣P鍵字間的比較”進行排序的方法可以按排序過程所依據的不同原則分為插入排序、交換排序、選擇排序、歸并排序。掌握各種排序方法的時間復雜度的分析方法。重點、難點重點，難點：希爾排序、快速排序、歸并排序、基數排序各種內部排序方法的比較討論。 課 型電腦理論教學方法投影、討論、版書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）任務一、排序的基本概念 前言計算機在進行數據處理工作時，

2、排序是其最基本的運算之一。在當今的計算機系統(tǒng)中，系統(tǒng)的運行時間很大比例花費在排序上。有資料表明，一些商用計算機在排序上的CPU時間達到20%至60%。為了提高計算機的工作效率，人們提出了各種各樣的排序方法和算法。因此，對于計算機專業(yè)人員來說，本章介紹的內容是十分重要的，主要內容有插入排序、冒泡排序、快速排序、直接排序、堆排序和歸并排序的基本思想、步驟及方法一、排序介紹 排序（Sorting）是數據處理中一種很重要的運算，同時也是很常用的運算，一般數據處理工作25%的時間都在進行排序。簡單地說，排序就是把一組記錄（元素）按照某個域的值的遞增（即由小到大）或遞減（即由大到?。┑拇涡蛑匦屡帕械倪^程安

3、徽新華電腦專修學院課堂教學教案（電腦應用課使用）表9-1 學生檔案表學號姓名年齡性別99001王曉佳18男99002林一鵬19男99003謝寧17女99004張麗娟18女99005周濤20男99006李小燕16女例如，在表9-1中，若以每個記錄的學號為關鍵字，按排序碼年齡的遞增（由小到大）排序，則所有記錄的排序結果可簡記為：（99006，16），（99003，17），（99001，18），（99004，18），（99002，19），（99005，20）；也可能為：（99006，16），（99003，17），（99004，18），（99001，18），（99002，19），（99005，20）；

4、這兩個結果都是表9-1按年齡的遞增排序結果。若按排序碼姓名來進行遞增排序，則得到的排序結果為：（99006，李小燕），（99002，林一鵬），（99001，王曉佳），（99003，謝寧），（99004，張麗娟），（99005，周濤）當然，我們還可以按排序碼性別來進行遞增排序，在此不再作進一步的分析。二、基本概念1排序碼（Sort Key） 作為排序依據的記錄中的一個屬性。它可以是任何一種可比的有序數據類型，它可以是記錄的關鍵字，也可以是任何非關鍵字。如上例中的學生年齡。在此我們認為對任何一種記錄都可找到一個取得它排序碼的函數Skey(一個或多個關鍵字的組合)。 2有序表與無序表一組記錄按排序碼

5、的遞增或遞減次序排列得到的結果被稱之為有序表，相應地，把排序前的狀態(tài)稱為無序表。3正序表與逆序表若有序表是按排序碼升序排列的，則稱為升序表或正序表，否則稱為降序表或逆序表。不失普遍性，我們一般只討論正序表。4排序定義若給定一組記錄序列r1 ，r2 ，rn，其排序碼分別為s1，s2 ，sn ，將這些記錄排成順序為rk1 ，rk2 ，rkn的一個序列R，滿足條件sk1sk2 skn，獲得這些記錄排成順序為rp1 ，rp2 ，rpn的一個序列R”，滿足條件sp1sp2 spn的過程稱為排序。也可以說，將一組記錄按某排序碼遞增或遞減排列的過程，稱為排序。 5穩(wěn)定與不穩(wěn)定因為排序碼可以不是記錄的關鍵字，

6、同一排序碼值可能對應多個記錄。對于具有同一排序碼的多個記錄來說，若采用的排序方法使排序后記錄的相對次序不變，則稱此排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的。在上例中（見表9-1，按年齡排序），如果一種排序方法使排序后的結果必為前一個結果，則稱此方法是穩(wěn)定的；若一種排序方法使排序后的結果可能為后一個結果，則稱此方法是不穩(wěn)定的。 6內排序與外排序按照排序過程中使用內外存的不同將排序方法分為內排序和外排序。若排序過程全部在內存中進行，則稱為內排序；若排序過程需要不斷地進行內存和外存之間的數據交換，則稱為外排序。內排序大致可分為五類：插入排序、交換排序、選擇排序、歸并排序和分配排序。本章僅討論內排序。7排序

7、的時間復雜性排序過程主要是對記錄的排序碼進行比較和記錄的移動過程。因此排序的時間復雜性可以算法執(zhí)行中的數據比較次數及數據移動次數來衡量。當一種排序方法使排序過程在最壞或平均情況下所進行的比較和移動次數越少，則認為該方法的時間復雜性就越好，分析一種排序方法，不僅要分析它的時間復雜性，而且要分析它的空間復雜性、穩(wěn)定性和簡單性等。為了以后討論方便，我們直接將排序碼寫成一個一維數組的形式，并且在沒有聲明的情形下，所有排序都按排序碼的值遞增排列。 排序 插入排序（直插排序、二分排序、希爾排序） 交換排序（冒泡排序、快速排序） 選擇排序 （直選排序、樹型排序、堆排序） 歸并排序（二路歸并排序、多路歸并排序

8、） 分配排序 （多關鍵字排序、基數排序）復習思考題作 業(yè)上機任務案例分析： 對于一個學生信息表，我們可以給學生成績進行排序，還有年齡，姓名等等。參考文獻課后記（或歸納小結）本次課程就介紹這里結束，總結本次的內容；課后學生要好好把這次上的內容好好復習一下，然后預習下一次的內容，下一次我們介紹以上所述關系的具體描述。 課程名稱數據結構教學對象新華軟工專業(yè)教 材數據結構（C語言）授課內容第九章 排序 課 時2教學目的與要求深刻理解排序的定義和各種方法的特點，并加以靈活應用。了解各種方法的排序過程及其依據的原則?；凇瓣P鍵字間的比較”進行排序的方法可以按排序過程所依據的不同原則分為插入排序、交換排序、

9、選擇排序、歸并排序。掌握各種排序方法的時間復雜度的分析方法。重點、難點重點，難點：希爾排序、快速排序、歸并排序、基數排序各種內部排序方法的比較討論。 課 型電腦理論教學方法投影、討論、版書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）復習上一次的內容：1、 排序的概念：2、 排序的分類：3、 排序的概念和分類：要求學生回答（接上一次課的序號）任務二：插入排序一、直接插入排序1直接插入排序的基本思想 直接插入排序（Straight Insertion Sorting）的基本思想是：把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1

10、個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。安徽新華電腦專修學院課堂教學教案（電腦應用課使用）2直接插入的算法實現 void sort(NODE array,int n)/待排序元素用一個數組array 表示，數組有n個元素 int i, j; NODE x; / x 為中間結點變量 for ( i=1; i=0)& ( x.keyarrayj.key) arrayj+1=arrayj; j-; / 順序比較和移動 arrayj+1=x; 例如，n=6，數組R的六個排序碼分別為：17，3，25，

11、14，20，9。它的直接插入排序的執(zhí)行過程如圖9-1所示。3直接插入排序的效率分析從上面的敘述可以看出，直接插入排序算法十分簡單。那么它的效率如何呢？首先從空間來看，它只需要一個元素的輔助空間，用于元素的位置交換。從時間分析，首先外層循環(huán)要進行n-1次插入，每次插入最少比較一次（正序），移動兩次；最多比較i次，移動i2次（逆序）（i=1，2，n-1）。因此，直接插入排序的時間復雜度為O（n2）。直接插入算法的元素移動是順序的，該方法是穩(wěn)定的。二、希爾排序1希爾排序的基本思想希爾排序, 又稱為“縮小增量排序”。是1959年由D.L.Shell提出來的。該方法的基本思想是：先將整個待排元素序列分割

12、成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，待整個序列中的元素基本有序（增量足夠?。r，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。2希爾排序的效率分析雖然我們給出的算法是三層循環(huán)，最外層循環(huán)為log2n數量級，中間的for循環(huán)是n數量級的，內循環(huán)遠遠低于n數量級，因為當分組較多時，組內元素較少；此循環(huán)次數少；當分組較少時，組內元素增多，但已接近有序，循環(huán)次數并不增加。因此，希爾排序的時間復雜性在O（nlog2n）和O（n2 ）之間，大致為O（n1. 3）。例如

13、，n=8，數組array 的八個元素分別為：91，67，35，62，29，72，46，57。下面用圖9-2給出希爾排序算法的執(zhí)行過程。2冒泡排序的算法實現void Bubblesort( NODE array,int n) int i, j, flag; /當flag為0則停止排序 NODE temp; for ( i=1; i=i; j-) if (arrayj.keyarrayj-1.key) /發(fā)生逆序 temp=arrayj;arrayj=arrayj-1;arrayj-1=temp; flag=1; /交換，并標記發(fā)生了交換 if(flag=0) break; 例如，n=6，數組R的

14、六個排序碼分別為：17，3，25，14，20，9。下面用圖9-3給出冒泡排序算法的執(zhí)行過程。3冒泡排序的效率分析從上面的例子可以看出，當進行完第三趟排序時，數組已經有序，所以第四趟排序的交換標志為0，即沒進行交換，所以不必進行第四趟排序。從冒泡排序的算法可以看出，若待排序的元素為正序，則只需進行一趟排序，比較次數為（n-1）次，移動元素次數為0；若待排序的元素為逆序，則需進行n-1趟排序，比較次數為(n2-n)/2，移動次數為3(n2-n )/2，因此冒泡排序算法的時間復雜度為O（n2）。由于其中的元素移動較多，所以屬于內排序中速度較慢的一種。因為冒泡排序算法只進行元素間的順序移動，所以是一個

15、穩(wěn)定的算法。9.3.2 快速排序1快速排序的基本思想快速排序（Quick Sorting）是迄今為止所有內排序算法中速度最快的一種。它的基本思想是：任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列有序?？焖倥判蚴菍γ芭菖判虻囊环N改進方法，算法中元素的比較和交換是從兩端向中間進行的，排序碼較大的元素一次就能夠交換到后面單元，排序碼較小的記錄一次就能夠交換到前面單元，記錄每次移動的距離較遠，因而總的比較和移動次數

16、較少。 快速排序的過程為：把待排序區(qū)間按照第一個元素（即基準元素）的排序碼分為左右兩個子序列的過程叫做一次劃分。設待排序序列為arraystartarrayend，其中start為下限，end為上限，startend，mid=arraystart為該序列的基準元素，為了實現一次劃分，令i,j的初值分別為start和end。在劃分過程中，首先讓j從它的初值開始，依次向前取值，并將每一元素arrayj的排序碼同mid的排序碼進行比較，直到arrayj.key=end) return; i=start;j=end;mid=arrayi; while (ij) while (imid.key) j-;

17、 if (ij) arrayi=arrayj; i+; while (ij & arrayi.key=mid.key) i+; if (ij) arrayj=arrayi; j-; /一次劃分得到基準值的正確位置 arrayi=mid; quicksort(array,start,i-1); /遞歸調用左子區(qū)間 quicksort(array,i+1,end); /遞歸調用右子區(qū)間3快速排序的效率分析若快速排序出現最好的情形（左、右子區(qū)間的長度大致相等），則結點數n與二叉樹深度h應滿足log2nhlog2n+1 ，所以總的比較次數不會超過(n+1) log2n。因此，快速排序的最好時間復雜度應

18、為O（nlog2n）。而且在理論上已經證明，快速排序的平均時間復雜度也為O（nlog2n）。若快速排序出現最壞的情形（每次能劃分成兩個子區(qū)間，但其中一個是空），則這時得到的二叉樹是一棵單分枝樹，得到的非空子區(qū)間包含有n-i個(i代表二叉樹的層數（1in）元素，每層劃分需要比較n-i+2次，所以總的比較次數為（n2+3n-4）/2。因此，快速排序的最壞時間復雜度為O(n2)?？焖倥判蛩加玫妮o助空間為棧的深度，故最好的空間復雜度為O（log2n），最壞的空間復雜度為O(n)?？焖倥判蚴且环N不穩(wěn)定的排序方法。 復習思考題作 業(yè)上機任務案例分析： 對于一個學生信息表，我們可以給學生成績進行排序，還有

19、年齡，姓名等等。參考文獻課后記（或歸納小結）本次課程就介紹這里結束，總結本次的內容；課后學生要好好把這次上的內容好好復習一下，然后預習下一次的內容，下一次我們介紹以上所述關系的具體描述。 課程名稱數據結構教學對象新華軟工專業(yè)教 材數據結構（C語言）授課內容第九章 排序課 時2教學目的與要求本節(jié)主要掌握選擇排序、樹形選擇排序重點、難點重難點：選擇排序、樹形選擇排序 課 型電腦理論教學方法投影、討論、版書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）任務三、選擇排序 復習上一次的內容：4、 排序的基本概念：5、 插入排序、希爾排序、交換排序、冒泡排序、快速排序：6、 幾種排序的基

20、本思想和算法：要求學生回答一、直接選擇排序1直接選擇排序的基本思想直接選擇排序也是一種簡單的排序方法。它的基本思想是：第一次從array0arrayn-1中選取最小值，與array0交換，第二次從array1arrayn-1中選取最小值，與array1交換，第三次從array2arrayn-1中選取最小值，與array2交換，第i次從arrayi-1arrayn-1中選取最小值，與arrayi-1交換，, 第n-1次從arrayn-2arrayn-1中選取最小值，與arrayn-2交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列。例如，給定n=8，數組R中的8個元素的排序碼為：（

21、8，3，2，1，7，4，6，5），則直接選擇排序過程如圖9-5所示。安徽新華電腦專修學院課堂教學教案（電腦應用課使用）教學過程設計(續(xù)表)3直接選擇排序的效率分析在直接選擇排序中，共需要進行n-1次選擇和交換，每次選擇需要進行n-i次比較（1in-1），而每次交換最多需3次移動，因此，總的比較次數C= =(n2-n)/2，總的移動次數M= =3(n-1)。由此可知，直接選擇排序的時間復雜度為O(n2)數量級，所以當記錄占用的字節(jié)數較多時，通常比直接插入排序的執(zhí)行速度要快一些。由于在直接選擇排序中存在著不相鄰元素之間的互換，因此，直接選擇排序是一種不穩(wěn)定的排序方法。例如，給定排序碼為3，7，3，

22、2，1，排序后的結果為1，2，3，3，7。二、樹形選擇排序從直接選擇排序可知，在n個排序碼中，找出最小值需n-1次比較，找出第二小值需n-2次比較，找出第三小值需n-3次比較，其余依此類推。所以，總的比較次數為：(n-1)+(n-2)+3+2+1= (n2-n)/2，那么，能否對直接選擇排序算法加以改進，使總的比較次數比 (n2-n)/2小呢？顯然，在n個排序碼中選出最小值，至少進行n-1次比較，但是，繼續(xù)在剩下的n-1個關鍵字中選第二小的值，就并非一定要進行n-2次比較，若能利用前面n-1次比較所得信息，則可以減少以后各趟選擇排序中所用的比較次數，比如8個運動員中決出前三名，不需要7+6+5

23、=18場比賽（前提是，若甲勝乙，而乙勝丙，則認為甲勝丙），最多需要11場比賽即可（通過7場比賽產生冠軍后，第二名只能在輸給冠軍的三個對中產生，需 2場比賽，而第三名只能在輸給亞軍的三個對中產生，也需2場比賽，總共11場比賽）。具體見圖9-6所示。教學過程設計(續(xù)表)從圖9-6（a）可知，8個隊經過4場比賽，獲勝的4個隊進入半決賽，再經過2場半決賽和1場決賽即可知道冠軍屬誰（共7場比賽）按照錦標賽的傳遞關糸，亞軍只能產生于分別在決賽，半決賽和第一輪比賽中輸給冠軍的選取手中，于是亞軍只能在b、c、e這3個隊中產生（見圖9-6（b），即進行2場比賽（e 與c一場，e與c的勝隊與b一場）后，即可知道亞

24、軍屬誰。同理，第三名只需在c、f、g這3個隊產生（見圖9-6（c）即進2場比賽（f與g一場，f與g的勝隊與c一場）即可知道第三名屬誰。 樹形選擇排序，又稱錦標賽排序，是一種按照錦標賽的思想進行選擇排序的方法。首先對n個記錄的排序碼進行兩兩比較，然后在其中n/2 個較小者之間再進行兩兩比較，如此重復，直到選出最小排序碼為止。 例如，給定排序碼頭 50，37，66，98，75，12，26，49，樹形選擇排序過程見圖9-7。 教學過程設計(續(xù)表)復習思考題作 業(yè)上機任務案例分析：學生成績排序表家族樹參考文獻課后記（或歸納小結）總結一下今天所上的內容，然后結合上兩一次所上的內容就可以所學知識連貫一下，

25、最后要求學生課后把所上內容好好看一下，本書內容到此結束，希望同學們回去好好復習一下。課程名稱數據結構教學對象新華軟工專業(yè)教 材數據結構（C語言）授課內容第九章 排序課 時2教學目的與要求本節(jié)主要掌握選擇排序、樹形選擇排序、堆排序重點、難點重難點：堆排序課 型電腦理論教學方法投影、討論、版書教學過程設計（包括講授知識、演示內容及案例、提問及學生演示內容）復習上一次的內容：選擇排序、樹形選擇排序基本思想和算法：要求學生回答（接上一次課的序號）任務五、 堆排序數形選擇排序的速度比直接選擇排序有了很大的提高，但是在比較過程中要使用多一倍的輔助空間來保存比較結果，并且每次還要與已經有序（即用）替代了）的

26、關鍵字比較。為了克服樹形選擇排序的這一缺點，威洛姆斯（J.Willioms）和弗洛伊德（Flogd）在1964年對樹形選擇排序提出了改進，使其比較次數達到樹形選擇水平，同時又不增加存儲開銷。這種方法稱為堆排序（heap sort）1 堆的定義 若有n個元素的排序碼k1，k2，k3，kn，當滿足如下條件： kik2i kik2i（1） （2） kik2i+1 或 kik2i+1 安徽新華電腦專修學院課堂教學教案（電腦應用課使用）教學過程設計(續(xù)表)其中i=1,2,n/2則稱此n個元素的排序碼k1，k2，k3，kn為一個堆。若將此排序碼按順序組成一棵完全二叉樹，則（1）稱為小根堆（二叉樹的所有根結

27、點值小于或等于左右孩子的值），（2）稱為大根堆（二叉樹的所有根結點值大于或等于左右孩子的值）。若n個元素的排序碼k1，k2，k3，kn滿足堆，且讓結點按1、2、3、n順序編號，根據完全二叉樹的性質（若i為根結點，則左孩子為2i，右孩子為2i+1）可知，堆排序實際與一棵完全二叉樹有關。若將排序碼初始序列組成一棵完全二叉樹，則堆排序可以包含建立初始堆（使排序碼變成能符合堆的定義的完全二叉樹）和利用堆進行排序兩個階段。2堆排序的基本思想將排序碼k1，k2，k3，kn表示成一棵完全二叉樹，然后從第n/2 個排序碼(即樹的最后一個非終端結點)開始篩選，使由該結點作根結點組成的子二叉樹符合堆的定義，然后從

28、第n/2 -1個排序碼重復剛才操作，直到第一個排序碼止。這時候，該二叉樹符合堆的定義，初始堆已經建立。 接著，可以按如下方法進行堆排序：將堆中第一個結點（二叉樹根結點）和最后一個結點的數據進行交換（k1與kn），再將k1kn-1重新建堆，然后k1和kn-1交換，再將k1kn-2重新建堆，然后k1和kn-2交換，如此重復下去，每次重新建堆的元素個數不斷減1，直到重新建堆的元素個數僅剩一個為止。這時堆排序已經完成，則排序碼k1，k2，k3，kn已排成一個有序序列。例如，給定排序碼49，38，65，97，76，13，27，49，建立初始堆的過程如圖9-8所示。建成如圖9-8(e)所示的堆后，堆排序過

29、程如圖9-9所示。4堆排序的效率分析在整個堆排序中，共需要進行n+n/2 -1次篩選運算，每次篩選運算進行雙親和孩子或兄弟結點的排序碼的比較和移動次數都不會超過完全二叉樹的深度，所以，每次篩選運算的時間復雜度為O(log2n)，故整個堆排序過程的時間復雜度為O(nlog2n)。堆排序占用的輔助空間為1（供交換元素用），故它的空間復雜度為O（1）。堆排序是一種不穩(wěn)定的排序方法，例如，給定排序碼：2，1，2，它的排序結果為：1，2，2。一、二路歸并排序二路歸并排序的基本思想 二路歸并排序的基本思想是：將兩個有序子區(qū)間（有序表）合并成一個有序子區(qū)間，一次合并完成后，有序子區(qū)間的數目減少一半，而區(qū)間的長度增加一倍，當區(qū)間長度從1增加到n（元素個數）時，整個區(qū)間變?yōu)橐粋€，則該區(qū)間中的有序序列即為我們所需的排序結果。例如，給定排序碼46，55，13，42，94，05，17，70，二路歸并