北京理工大學數(shù)據(jù)結構排序課件

1、第十章 排序1 第十章 排 序 10.1 概述 10.2 插入排序 10.3 快速排序 10.4 選擇排序 2 10.1 概述 設R1 R2 R3 Rn 是n個記錄，k1,k2, k3 kn為它們的關鍵字，排序就是將記錄按關鍵字遞增（或遞減）的次序排列起來。 主要操作 比較關鍵字 移動記錄3 1、排序的分類按記錄的存放位置分類有 內部排序 外部排序按排序原則分類（內部排序） 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序4 2、排序方法的穩(wěn)定性 在待排記錄序列中，任何兩個關鍵字相同的記錄，用某種排序方法排序后相對位置不變，則稱這種排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的。待排序列： 49, 38,

2、 65, 97, 76, 13, 27, 49 排序后: 13, 27, 38, 49, 49, 65, 76, 97 穩(wěn)定排序后: 13, 27, 38, 49, 49, 65, 76, 97不穩(wěn)定5待排記錄的存儲順序關鍵字類型定義 typedef int KeyType; 記錄類型定義 typedef struct KeyType key; /關鍵字域 /其它域 RedType; 3、待排記錄的存儲6順序表類型定義 typedef struct RedType rMAXSIZE+1; int length; SqList 0 1 2 3 4 5 6 7 8 9 10 m-1 45 61 1

3、2 3 37 24 90 53 98 787 10.2 插入排序基本思想 依次將待排記錄插入到有序子表中，并使其插入后子表仍保持有序，直到全部記錄插入完畢；初始時，有序子表中只有一個元素。 例 49 38 65 97 76 13 27 49 55 048 1、直接插入排序 例： 49 38 65 97 76 13 27 49 （49）38 65 97 76 13 27 49 （38 49）65 97 76 13 27 49 （38 49 65）97 76 13 27 49 （38 49 65 97）76 13 27 49 （38 49 65 76 97）13 27 49 （13 38 49 6

4、5 76 97）27 49 （13 27 38 49 65 76 97）49 （13 27 38 49 49 65 76 97）9void InsertSort(SqList &L) /對順序表L作直接插入排序（非遞減）。 for (i=2; i=L. length; +i) if (L.ri.key L.ri-1.key) /將L.ri插入有序子表 L.r0=L.ri; /將L.ri復制為哨兵 for(j=i-1; L.r0.keyL.rj.key; -j ) L.rj+1=L.rj; /記錄后移 L.rj+1=L.r0; /插入正確位置 0 1 2 3 4 5 6 7 8 m-1 49 3

5、8 65 76 97 13 27 4910 如果 R1, ., i-1 是一個按關鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“在R1, , i-1中查找Ri的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。2、折半插入排序1114 36 49 52 8058 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入 位置插入 位置L.rL.r插入位置：high + 1，其中的關鍵字是有序子表中大于待插入記錄的最小的一個。12low = 1; high = i-1;whil

6、e (low=high) m = (low+high)/2; / 折半if (L.r0.key L.rm.key) high = m-1; / 插入點在低半?yún)^(qū)else low = m+1; / 插入點在高半?yún)^(qū)/在 L.r1.i-1中折半查找插入位置；13void BiInsertionSort ( SqList &L ) / BInsertSort /在 L.r1.i-1中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 記錄后移L.rhigh+1 = L.r0; / 插入折半插入排序僅減少了比較次數(shù)，但是記錄的移動次數(shù)沒變！1410.3

7、交換排序基本思想： 將待排記錄中兩兩記錄的關鍵字進行比較，若逆序則交換位置。 例：49 38 65 97 76 13 27 49 起泡排序 49 38 65 97 76 13 27 49 38 49 65 76 13 27 49 9715 快速排序選定一記錄R，將所有其他記錄關鍵字k與該記錄關鍵字k比較, 若 kk 則將記錄換至R之后; 繼續(xù)對R前后兩部分記錄分別進行快速排序，直至排序范圍為1; 例 49 38 65 97 76 13 27 49 55 0416 49 38 65 97 76 13 27 49 一趟快速排序jjii 27 38 65 97 76 13 49 49ijj 27 3

8、8 49 97 76 13 65 49jiiij 27 38 13 97 76 49 65 49jji 27 38 13 49 76 97 65 49(2749)(9749)(1349)(i=j)i即low; j即high17int Partition(SqList &L, int low, int high) /一趟快速排序pivotkey=L.rlow.key; while(lowhigh) /從表的兩端交替地向中間掃描 while(low=pivotkey) -high; L.rlowL.rhigh; while (lowhigh & L.rlow. Key=pivotkey) +low

9、; L.rhigh L.rlow; return low; /返回樞軸位置/Partition18 49 38 65 97 76 13 27 49 49一趟快速排序jjii 27 38 65 97 76 13 27 49ijj 27 38 65 97 76 13 65 49jiiij 27 38 13 97 76 13 65 49jji 27 38 13 97 76 97 65 49(2749)(9749)(1349)(i=j)i即low; j即highji 27 38 13 49 76 97 65 4919int Partition(SqList &L, int low, int high)

10、 /一趟快速排序L.r0=L.rlow; /用子表的第一個記錄作樞軸記錄pivotkey=L.rlow.key; while(lowhigh) /從表的兩端交替地向中間掃描 while(low=pivotkey) -high; L.rlow=L.rhigh; while (lowhigh & L.rlow. Key=pivotkey) +low; L.rhigh=L.rlow; L.rlow=L.r0; /將樞軸記錄放到樞紐位置 return low; /返回樞軸位置/Partition20 27 38 13 49 76 97 65 49快速排序 13 27 38 49 49 65 76 97

11、13 27 38 49 49 65 76 971趟快速排序后：分別快速排序后： 49 38 65 97 76 13 27 49 待排序：完成快速排序后：21void Qsort(SqList &L, int low, int high) /對順序表L中的子序列L.rlow. high作快速排序 if (lowhigh) pivotloc=Partition(L, low, high); QSort(L, low, pivotloc-1); Qsort(L, pivotloc+1, high); void QuickSort(SqList &L ) /對順序表L快速排序 QSort(L, 1,

12、L.length); 就平均時間而言，快速排序被認為是目前最好的一種內部排序。22 10.4 選擇排序基本思想在待排記錄中依次選擇關鍵字最小的記錄，逐漸縮小范圍直至全部記錄選擇完畢。 例 49 38 65 97 76 13 27 49 23 一 簡單選擇排序 49 38 65 97 76 13 27 49 1338 65 97 76 49 27 49 13 2765 97 76 49 38 49 13 27 3865 97 76 49 49 13 27 38 4965 97 76 49 13 27 38 49 4965 97 76 13 27 38 49 49 6597 76 13 27 38

13、 49 49 65 76 9724void SelectSort(SqList &K) /簡單選擇排序 for (i=1; iL.length; +i) /在L.ri.L.length 中選擇key最小的記錄 k=i; for( j=i+1;j= L.length ; j+) if ( L.rj.key L.rk.key) k=j; if(k!=i)L.riL.rj; 49 38 65 97 76 13 27 49 13 38 65 97 76 49 27 49 kjjjjj25 二 堆排序一顆完全二叉樹，如果滿足下面的條件，則稱其為堆：根結點關鍵字 左、右孩子結點的關鍵字；左、右子樹也是堆。

14、 816 9 1 6 2 1110 5 416 9 810 6 2 11 1 5 4大根堆不是堆26小根堆 1 6 811 916 2 10 4 5 1 9 810 616 2 11 5 4不是堆27堆的另一定義 對于一個關鍵碼序列K1,K2,Kn，如果滿足KiK2i而且KiK2i+1, (i=1, 2, , n/2)，則稱其為堆（大根堆）。 816 9 1 6 2 1110 5 428 篩選操作(FilterDown)： 1 9 8 10 6 2 16 11 5 4為了形成堆進行的自堆頂至葉子結點的調整過程。29 篩選操作(FilterDown)16 9 8 10 6 2 1 11 5 4為

15、了形成堆進行的自堆頂至葉子結點的調整過程。30 篩選操作(FilterDown)16 9 8 10 6 2 11 1 5 4為了形成堆進行的自堆頂至葉子結點的調整過程。31 篩選操作(FilterDown)16 9 8 1 6 2 1110 5 4為了形成堆進行的自堆頂至葉子結點的調整過程。32 建堆從堆的最后一個分支結點（第n/2個元素）開始到根結點 ，依次進行篩選，最終將之調整為堆。 1 9 8 10 616 2 11 4 533 建堆從堆的最后一個分支結點（第n/2個元素）開始到根結點 ，依次進行篩選，最終將之調整為堆。 1 9 8 10 616 2 11 5 434 建堆從堆的最后一個

16、分支結點（第n/2個元素）開始到根結點 ，依次進行篩選，最終將之調整為堆。 1 9 8 10 6 11 2 16 5 435 建堆從堆的最后一個分支結點（第n/2個元素）開始到根結點 ，依次進行篩選，最終將之調整為堆。 1 9 8 10 6 11 2 16 5 436 建堆從堆的最后一個分支結點（第n/2個元素）開始到根結點 ，依次進行篩選，最終將之調整為堆。 1 9 8 10 6 1116 2 5 437 建堆從堆的最后一個分支結點（第n/2個元素）開始到根結點 ，依次進行篩選，最終將之調整為堆。 1 9 8 10 6 216 11 5 438 建堆從堆的最后一個分支結點（第n/2個元素）開

17、始到根結點 ，依次進行篩選，最終將之調整為堆。16 9 8 10 6 2 1 11 5 439 建堆從堆的最后一個分支結點（第n/2個元素）開始到根結點 ，依次進行篩選，最終將之調整為堆。16 9 8 10 6 2 11 1 5 440 建堆從堆的最后一個分支結點（第n/2個元素）開始到根結點 ，依次進行篩選，最終將之調整為堆。16 9 8 1 6 2 11 10 5 441 堆排序建堆循環(huán)，直到堆為空： 將堆頂元素與堆最后的元素互換； 輸出堆最后的元素； 將其余的元素重新篩選成堆；4216 9 8 1 6 2 11 10 5 4 1 9 8 10 616 2 11 4 5建堆4316 9 8 1 6 2 11 10 5 4 4 9 8 1 6 2 11 10 516循環(huán)，直到堆為空： 將堆頂元素與堆最后的元素交換；將其余