插入排序與交換排序

1、第第9 9章章 內(nèi)部排序內(nèi)部排序選擇排序 (直接排序、堆排序)概述插入排序 (直接排序、折半排序、希爾排序)交換排序 (冒泡排序、快速排序)通過例子消化概念通過例子消化概念v 在排序問題中，通常將在排序問題中，通常將數(shù)據(jù)元素?cái)?shù)據(jù)元素稱為稱為記錄記錄。 顯然輸入的是一個(gè)記錄集合，排序后輸出的也是一個(gè)顯然輸入的是一個(gè)記錄集合，排序后輸出的也是一個(gè)記錄集合。記錄集合。 所以可以將排序看成是線性表的一種操作。所以可以將排序看成是線性表的一種操作。v 排序的依據(jù)是關(guān)鍵字之間的大小關(guān)系，那么對同一記錄集排序的依據(jù)是關(guān)鍵字之間的大小關(guān)系，那么對同一記錄集合，針對不同的關(guān)鍵字進(jìn)行排序，可以得到不同序列。合，針

2、對不同的關(guān)鍵字進(jìn)行排序，可以得到不同序列。v 請看例子：排序演示請看例子：排序演示.xls.xls9.1 概述概述排序的穩(wěn)定性排序的穩(wěn)定性通過例子消化概念通過例子消化概念編號編號姓名姓名總分總分1 1小賈小賈7312 2小劉小劉6593 3小張小張7254 4小王小王7315 5小胡小胡726編號編號姓名姓名總分總分1 1小賈小賈7314 4小王小王7315 5小胡小胡7263 3小張小張7252 2小劉小劉659編號編號姓名姓名總分總分4 4小王小王7311 1小賈小賈7315 5小胡小胡7263 3小張小張7252 2小劉小劉659穩(wěn)定排序不穩(wěn)定排序9.1 概述概述插入排序插入排序v插入排

3、序插入排序9.2 插入排序插入排序直接插入排序 初始狀態(tài)4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7 R8 i =2 i =3 3849659776132749 i =4 3849659776132749 i =5 384965769713274976i =6 384965769713274913i =7 384965769713274927i =8 3849657697132749494938659776132749 3849387 趟 排序 1 趟 排序 2 趟 排序 排序過程：排序過程：先將序列中第 1 個(gè)記錄看成是一個(gè)有序子序列， 然后從第 2 個(gè)記

4、錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序。 v直接插入排序直接插入排序9.2 插入排序插入排序void InsertSort ( SqList &L ) / 對順序表 L 作直接插入排序。 for ( i = 2; i = L.length; + i ) /將 L.ri 插入有序子表 if (L.ri.key L.ri -1.key) / InsertSort 在 r1. i-1中查找 ri 的插入位置; 對于在查找過程中找到的那些關(guān)鍵字 不小于 ri.key 的記錄，在查找的同 時(shí)實(shí)現(xiàn)記錄向后移動(dòng)； 插入 ri ;L.r0 = L.ri; / 復(fù)制為監(jiān)視哨 L.ri = L.ri -1

5、; for ( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 記錄后移 L.r j + 1 = L.r0; / 插入到正確位置 v直接插入排序性能分析直接插入排序性能分析 9.2 插入排序插入排序211nin2(2)(1)2ninni2(4)(1)(1)2ninni比較次數(shù)： 移動(dòng)次數(shù)： 0 最好的情況：待排序記錄按關(guān)鍵字從小到大排列（正序） 比較次數(shù)： 移動(dòng)次數(shù)： 最壞的情況：待排序記錄按關(guān)鍵字從大到小排列（逆序） v直接插入排序性能分析直接插入排序性能分析 9.2 插入排序插入排序 由于待排記錄序列是隨機(jī)的，取上

6、述二值的平均值。所以直接插入排序的時(shí)間復(fù)雜度為O(n2)。 直接插入排序是“穩(wěn)定的”：關(guān)鍵碼相同的兩個(gè)記錄，在整個(gè)排序過程中，不會(huì)通過比較而相互交換。v折半插入排序折半插入排序9.2 插入排序插入排序(1) 基本思想 考慮到 L.r1,.,i-1 是按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)“L.r1,i-1中查找 L.ri 的插入位置”如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉＠河欣河?個(gè)記錄，前個(gè)記錄，前5個(gè)已排序的基礎(chǔ)上，對第個(gè)已排序的基礎(chǔ)上，對第6個(gè)記錄排序。個(gè)記錄排序。 15 27 36 53 69 42 15 27 36 53 69 42 15 27 36 53 69 42 15

7、27 36 42 53 69 9.2 插入排序插入排序(high36 )( 4253 ) high mid lowlow highmid high low折半插入排序在尋找插入位置時(shí)，不是逐個(gè)比較而是利用折半查找的原理尋找插入位置。待排序元素越多，改進(jìn)效果越明顯。v折半插入排序算法折半插入排序算法9.2 插入排序插入排序void BinsertSort(SqList &L) / 折半插入排序 int i,low,high,mid; for(i=2; i= L.length; +i) L.r0=L.ri; /將L.r i 暫存到L.r0 low=1; high=i-1; While(lo

8、w=high) /比較，折半查找插入位置 mid=(low+high)/2; / 折半 if (L.r0.key=low; j ) L.rj+1=L.rj; / 記錄后移 L.rlow=L.r0; / 插入 / BInsertSortL.r1,i- -1v折半插入排序算法分析折半插入排序算法分析9.2 插入排序插入排序 折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。 折半插入排序減少了關(guān)鍵字的比較次數(shù)，但記錄的移動(dòng)次數(shù)不變，其時(shí)間復(fù)雜度與直接插入排序相同。 在插入第 i 個(gè)對象時(shí)，需要經(jīng)過 log2i +1 次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。 折半插入排序是一個(gè)穩(wěn)

9、定的排序方法。9.2 插入排序插入排序1.我們都能理解，優(yōu)秀排序算法的首要條件就是2.于是人們想了許許多多的排序辦法，目的就是為了提高排序的速度。3.而在很長的時(shí)間里，眾人發(fā)現(xiàn)盡管各種排序算法花樣繁多，但時(shí)間復(fù)雜度都是O(n2)，似乎沒法超越了。4.計(jì)算機(jī)學(xué)術(shù)界充斥著“排序算法不可能突破O(n2)”的聲音？速度9.2 插入排序插入排序 終于有一天，當(dāng)一位科學(xué)家發(fā)布超越了O(n2)新排序算法后，緊接著就出現(xiàn)了好幾種可以超越O(n2)的排序算法，并把內(nèi)排序算法的時(shí)間復(fù)雜度提升到了O(nlog2n)?！安豢赡艹絆(n2) ”徹底成為了歷史。v希爾排序希爾排序9.2 插入排序插入排序基本思想：先將整

10、個(gè)待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直接插入排序。技巧：子序列的構(gòu)成不是簡單地“逐段分割”，而是將相隔某個(gè)增量dk的記錄組成一個(gè)子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk1為止。優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。312345665499725251321234562525136549971123456132525654997123456132525496597增量3增量2增量1希爾排序過程v希爾排序希爾排序9.2 插入排序插入排序38例：關(guān)鍵字

11、序列 T=(49, 38, 65, 97, 76, 13, 27, 49*, 55, 04) 請寫出希爾排序的具體實(shí)現(xiàn)過程。0123456789104938659776132749*5504初 態(tài)第1趟 (dk=5)第2趟 (dk=3)第3趟 (dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 ri算法分析：開始時(shí)dk 的值較大，子序列中的對象較少，排序速度較快；隨著排序進(jìn)展，dk

12、 值逐漸變小，子序列中對象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。v希爾排序算法描述希爾排序算法描述9.2 插入排序插入排序void ShellInsert ( SqList &L, int dk ) /一趟希爾插入排序 /1.前后記錄位置的增量是dk； /2.L.r0只是暫存單元，不是哨兵。當(dāng)j=0時(shí)，插入位置已找到 for ( i=dk+1; i=L.length; +i ) if ( L.ri.key0 & (L.r0.key1; i-) /i表示趟數(shù)，最多n-1趟 flag=0; /開始時(shí)元素未交換 for (int j=2; j=

13、i; j+) if (RjRj-1) /發(fā)生逆序 temp=Rj; Rj=Rj-1; Rj-1=temp; flag=1; if(flag=0) return; / Bubblesortv冒泡排序算法分析冒泡排序算法分析9.3 交換排序交換排序正序： 只需進(jìn)行一趟排序，在排序過程中進(jìn)行n-1次關(guān)鍵字間的比較，且不移動(dòng)記錄；時(shí)間復(fù)雜度為O(n) 。逆序： 需要進(jìn)行n-1趟排序，需要進(jìn)行n(n-1)/2次比較，并作等數(shù)量級的記錄移動(dòng)?？偟臅r(shí)間復(fù)雜度為O(n2) 。 起泡排序方法是穩(wěn)定的。適合于數(shù)據(jù)較少的情況。v快速排序快速排序9.3 交換排序交換排序背景 起泡排序的過程可見，起泡排序是一個(gè)增加有序

14、序列長度的過程，也是一個(gè)縮小無序序列長度的過程，每經(jīng)過一趟起泡，無序序列的長度只縮小1。 試設(shè)想：若能在經(jīng)過一趟排序，使無序序列的長度縮小一半，則必能加快排序的速度。v快速排序快速排序9.3 交換排序交換排序(1) 基本思想 通過一趟排序?qū)⒋判蛄幸詷休S為標(biāo)準(zhǔn)劃分成兩部分，使其中一部分記錄的關(guān)鍵字均比另一部分小，再分別對這兩部分進(jìn)行快速排序，以達(dá)到整個(gè)序列有序。 通常取第一個(gè)記錄的值為基準(zhǔn)值或樞軸。v快速排序快速排序9.3 交換排序交換排序(2) 具體做法 附設(shè)兩個(gè)指針low和high，初值分別指向第一個(gè)記錄和最后一個(gè)記錄，設(shè)樞軸為key； 1.從high 所指位置起向前搜索，找到第一個(gè)不大于

15、基準(zhǔn)值的記錄與樞軸記錄相互交換； 2.從low 所指位置起向后搜索，找到第一個(gè)不小于基準(zhǔn)值的記錄與樞軸記錄相互交換。 3.重復(fù)這兩步直至low=high為止。v快速排序快速排序9.3 交換排序交換排序lowhigh設(shè)Rs=52 為樞軸例： 52 52 49 80 36 14 58 61 97 23 75 high23 lowlow80highhighhighhigh14lowlow52v一趟快速排序算法描述一趟快速排序算法描述9.3 交換排序交換排序int Partition (Elem R , int low, int high) R0 = Rlow; pivotkey = Rlow.key

16、; while (low high) /從兩端交替向中間掃描 while (low = pivotkey) - - high; Rlow = Rhigh; /將比樞軸記錄小的移到低端 while (low high & Rlow.key = pivotkey) + + low; Rhigh = Rlow; /將比樞軸記錄大的移到高端 Rlow = R0; /樞軸記錄到位 return low; /返回樞軸位置 / Partitionv快速排序算法過程快速排序算法過程 9.3 交換排序交換排序無 序 的 記 錄 序 列無序記錄子序列 (1)無序子序列 (2) 樞軸 一次劃分 分別進(jìn)行一趟

17、快速排序 有 序 的 記 錄 序 列 v快速排序算法描述快速排序算法描述9.3 交換排序交換排序void QSort ( Elem R , int low, int high ) /對序列Rlow.high進(jìn)行快速排序 if (low high-1) /長度大于1 pivot = Partition( L,low,high); /將Rlow.high一分為二 QSort(L,low, pivot-1); /對低子表遞歸排序，pivo是樞軸 QSort(L, pivot+1, high); / 對高子表遞歸排序 / QSortvoid QuickSort(Elem R, int n) /對記錄序

18、列進(jìn)行快速排序?qū)τ涗浶蛄羞M(jìn)行快速排序 QSort(R, 1, n); / QuickSort076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742，751，863，937076，129，256，751751，937，863，742，694，301，438076，129，256，438，301，694，742，694，863，937256，301，751，129，937，863，742，694，076，438例：以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行

19、快速算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。原始序列： 256，301，751，129，937，863，742，694，076，438第1趟第2趟第3趟第4趟要求模擬算法實(shí)現(xiàn)步驟256256076076301301129129751751256256751751438438076，129，256，301，438，694，742，751，863，937時(shí)間效率：O(nlog2n) 因?yàn)槊刻舜_定的元素呈指數(shù)增加空間效率：O(log2n)因?yàn)樗惴ǖ倪f歸性，要用到?？臻g穩(wěn) 定 性：不穩(wěn)定 因?yàn)榭蛇x任一元素為支點(diǎn)。v快速排序算法詳細(xì)分析快速排序算法詳細(xì)分析9.3 交換排序交換排序可以證明，函數(shù)Quicksort的平均計(jì)算時(shí)間是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)排序方