北京理工大學(xué)數(shù)據(jù)結(jié)構(gòu)排序課件

1、第十章 排序1 第十章 排 序 10.1 概述 10.2 插入排序 10.3 快速排序 10.4 選擇排序 2 10.1 概述 設(shè)R1 R2 R3 Rn 是n個(gè)記錄，k1,k2, k3 kn為它們的關(guān)鍵字，排序就是將記錄按關(guān)鍵字遞增（或遞減）的次序排列起來(lái)。 主要操作 比較關(guān)鍵字 移動(dòng)記錄3 1、排序的分類按記錄的存放位置分類有 內(nèi)部排序 外部排序按排序原則分類（內(nèi)部排序） 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序4 2、排序方法的穩(wěn)定性 在待排記錄序列中，任何兩個(gè)關(guān)鍵字相同的記錄，用某種排序方法排序后相對(duì)位置不變，則稱這種排序方法是穩(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待排記錄的存儲(chǔ)順序關(guān)鍵字類型定義 typedef int KeyType; 記錄類型定義 typedef struct KeyType key; /關(guān)鍵字域 /其它域 RedType; 3、待排記錄的存儲(chǔ)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 插入排序基本思想 依次將待排記錄插入到有序子表中，并使其插入后子表仍保持有序，直到全部記錄插入完畢；初始時(shí)，有序子表中只有一個(gè)元素。 例 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) /對(duì)順序表L作直接插入排序（非遞減）。 for (i=2; i=L. length; +i) if (L.ri.key L.ri-1.key) /將L.ri插入有序子表 L.r0=L.ri; /將L.ri復(fù)制為哨兵 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 是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“在R1, , i-1中查找Ri的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉?、折半插入排序1114 36 49 52 8058 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入 位置插入 位置L.rL.r插入位置：high + 1，其中的關(guān)鍵字是有序子表中大于待插入記錄的最小的一個(gè)。12low = 1; high = i-1;whil

6、e (low=high) m = (low+high)/2; / 折半if (L.r0.key L.rm.key) high = m-1; / 插入點(diǎn)在低半?yún)^(qū)else low = m+1; / 插入點(diǎn)在高半?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ù)，但是記錄的移動(dòng)次數(shù)沒變！1410.3

7、交換排序基本思想： 將待排記錄中兩兩記錄的關(guān)鍵字進(jìn)行比較，若逆序則交換位置。 例：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，將所有其他記錄關(guān)鍵字k與該記錄關(guān)鍵字k比較, 若 kk 則將記錄換至R之后; 繼續(xù)對(duì)R前后兩部分記錄分別進(jìn)行快速排序，直至排序范圍為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; /用子表的第一個(gè)記錄作樞軸記錄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) /對(duì)順序表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 ) /對(duì)順序表L快速排序 QSort(L, 1,

12、L.length); 就平均時(shí)間而言，快速排序被認(rèn)為是目前最好的一種內(nèi)部排序。22 10.4 選擇排序基本思想在待排記錄中依次選擇關(guān)鍵字最小的記錄，逐漸縮小范圍直至全部記錄選擇完畢。 例 49 38 65 97 76 13 27 49 23 一 簡(jiǎn)單選擇排序 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) /簡(jiǎn)單選擇排序 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 二 堆排序一顆完全二叉樹，如果滿足下面的條件，則稱其為堆：根結(jié)點(diǎn)關(guān)鍵字 左、右孩子結(jié)點(diǎn)的關(guān)鍵字；左、右子樹也是堆。

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堆的另一定義 對(duì)于一個(gè)關(guān)鍵碼序列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為了形成堆進(jìn)行的自堆頂至葉子結(jié)點(diǎn)的調(diào)整過(guò)程。29 篩選操作(FilterDown)16 9 8 10 6 2 1 11 5 4為

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

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

17、始到根結(jié)點(diǎn) ，依次進(jìn)行篩選，最終將之調(diào)整為堆。16 9 8 10 6 2 1 11 5 439 建堆從堆的最后一個(gè)分支結(jié)點(diǎn)（第n/2個(gè)元素）開始到根結(jié)點(diǎn) ，依次進(jìn)行篩選，最終將之調(diào)整為堆。16 9 8 10 6 2 11 1 5 440 建堆從堆的最后一個(gè)分支結(jié)點(diǎn)（第n/2個(gè)元素）開始到根結(jié)點(diǎn) ，依次進(jìn)行篩選，最終將之調(diào)整為堆。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)，直到堆為空： 將堆頂元素與堆最后的元素交換；將其余