數(shù)據(jù)結(jié)構(gòu)第10章排序1插入排序和交換排序ppt課件

1、武漢科技大學(xué)Wuhan University of Science and Technology張 凱計(jì)算機(jī)學(xué)院 軟件工程系2019年3月12日第第1010章章 內(nèi)部排序內(nèi)部排序選擇排序 (直接排序、堆排序)概述插入排序 (直接排序、折半排序、希爾排序)交換排序 (冒泡排序、快速排序)歸并排序基數(shù)排序v概述概述10.1 概述概述排序：將數(shù)據(jù)元素的一個(gè)任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。 例：將關(guān)鍵字序列：52, 49, 80, 36, 14, 58, 61, 23 調(diào)整為：14, 23, 36, 49, 52, 58, 61, 80 若按主關(guān)鍵字排序則結(jié)果惟一若按次關(guān)鍵字排序則結(jié)果可以

2、不惟一(因有相同關(guān)鍵字) v概述概述10.1 概述概述 設(shè) Ki、Kj (1in, 1jn, ij ) 分別為記錄 Ri、Rj 的關(guān)鍵字，且 Ki = Kj ，在排序前的序列中 Ri 領(lǐng)先于 Rj (即 i j )。若在排序后的序列中 Ri 仍領(lǐng)先于 Rj ，則稱所用的排序方法是穩(wěn)定的；反之，則稱所用的排序方法是不穩(wěn)定的。 例：設(shè)排序前的關(guān)鍵字序列為：52, 49, 80, 36, 14, 58, 36, 23 若排序后的關(guān)鍵字序列為：14, 23, 36, 36, 49, 52, 58, 80， 則排序方法是穩(wěn)定的。 若排序后的關(guān)鍵字序列為：14, 23, 36, 36, 49, 52, 5

3、8, 80， 則排序方法是不穩(wěn)定的。 v概述概述10.1 概述概述內(nèi)部排序和外部排序 若整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序； 反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序。 v插入排序插入排序10.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

4、 =7 384965769713274927i =8 3849657697132749494938659776132749 3849387 趟 排序 1 趟 排序 2 趟 排序 排序過程：排序過程：先將序列中第先將序列中第 1 個(gè)記錄看成是一個(gè)有序子序列，個(gè)記錄看成是一個(gè)有序子序列， 然后從第然后從第 2 個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序。個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序。 v直接插入排序直接插入排序10.2 插入排序插入排序void InsertSort ( SqList &L ) / 對順序表對順序表 L 作直接插入排序。作直接插入排序。 for ( i = 2

5、; i = L.length; + i ) 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; 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直接插入排序性能分析直接插入排序性能分析

6、 10.2 插入排序插入排序211nin2(2)(1)2ninni2(4)(1)(1)2ninni比較次數(shù)： 移動(dòng)次數(shù)： 0 最好的情況：待排序記錄按關(guān)鍵字從小到大排列正序） 比較次數(shù)： 移動(dòng)次數(shù)： 最壞的情況：待排序記錄按關(guān)鍵字從大到小排列逆序） v直接插入排序性能分析直接插入排序性能分析 10.2 插入排序插入排序 由于待排記錄序列是隨機(jī)的，取上述二值的平均值。所以直接插入排序的時(shí)間復(fù)雜度為O(n2)。 直接插入排序是“穩(wěn)定的”：關(guān)鍵碼相同的兩個(gè)記錄，在整個(gè)排序過程中，不會(huì)通過比較而相互交換。v折半插入排序折半插入排序10.2 插入排序插入排序(1) 基本思想 考慮到 L.r1,.,i-1

7、 是按關(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 27 36 42 53 69 10.2 插入排序插入排序(high36 )( 4253 ) high mid lowlow highmid high low折半插入排序在尋找插入位置時(shí)，不是逐個(gè)比較而是利用折半查找的原理尋找插入位置。待排序元素越多

8、，改進(jìn)效果越明顯。v折半插入排序算法折半插入排序算法10.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(low=high) /比較，折半查找插入位置比較，折半查找插入位置 mid=(low+high)/2; / 折半折半 if (L.r0.key=low; j ) L.rj+1=L.rj; / 記錄后移記錄后移 L.rlow=L.

9、r0; / 插入插入 / BInsertSortv折半插入排序算法分析折半插入排序算法分析10.2 插入排序插入排序 折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。 折半插入排序減少了關(guān)鍵字的比較次數(shù)，但記錄的移動(dòng)次數(shù)不變，其時(shí)間復(fù)雜度與直接插入排序相同。 在插入第 i 個(gè)對象時(shí)，需要經(jīng)過 log2i +1 次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。 折半插入排序是一個(gè)穩(wěn)定的排序方法。v2-路插入排序路插入排序10.2 插入排序插入排序(1) 基本思想 2-路插入排序是在折半插入排序的基礎(chǔ)上改進(jìn)的，目的是減少排序過程中移動(dòng)記錄的次數(shù)，但為此需要n個(gè)記錄的輔助空間。v2-路

10、插入排序路插入排序10.2 插入排序插入排序(2) 具體做法 另設(shè)一個(gè)和 L.r 同類型的數(shù)組d，首先將 L.r1 賦值給d1 ，并將d1看成是在排好序的序列中處于中間位置的記錄，然后從 L.r中第 2 個(gè)記錄起依次插入到d1之前或之后的有序序列中。先將待插入記錄的關(guān)鍵字和d1 的關(guān)鍵字進(jìn)行比較。 假設(shè) L.rid1.key，則將 L.ri 插入到d1 之前的有序表中。反之，插入到d1 之后的有序表中?！境跏缄P(guān)鍵字】 49 38 65 97 76 13 27 49 排序過程中d 的狀態(tài)如下：i=1: (49) i=2: (49) (38)i=3: (49 65) (38)i=4: (49 65

11、 97) (38)i=5: (49 65 76 97) (38)i=6: (49 65 76 97) (13 38)i=7: (49 65 76 97) (13 27 38)i=8: (49 49 65 76 97) (13 27 38)finalfirst2路插入排序過程示例：firstfinalfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstvoid Path2Insertion(SqList &L, SqList &d) d0 = L1;/L中D的第一個(gè)記錄為d中排好序的記錄。 int first =

12、 0, final = 0;/first、final分別指示d中排好序的記錄的第1個(gè)和最后1個(gè)記錄的位置 for (int i = 2; i = length; +i) /依次將L的第2個(gè)最后一個(gè)記錄插入d中。 if (Li dfinal) /待插入記錄大于d中最小值，插入到dfinal之后 final = final + 1; dfinal = Li; else /待插入記錄大于d中最小值，小于d中最大值，插入到d的中間(需要移動(dòng)d數(shù)組) int j = final +;/移動(dòng)d尾部元素以便按序插入記錄。 while (Li dj) d(j + 1) % length = dj; j = (

13、j - 1 + length) % length; dj + 1 = Li; for (int i = 1; i = length; i +) /循環(huán)把d賦給L。 Li = d(i + first - 1) % length;/線性關(guān)系。 v2-路插入排序路插入排序10.2 插入排序插入排序 2-路插入排序只能減少移動(dòng)記錄的次數(shù)，而不能絕對避免移動(dòng)記錄。 2-路插入排序中，移動(dòng)記錄的次數(shù)約為n2/8 。 當(dāng)L.r1是待排序記錄中關(guān)鍵字最小或最大的記錄時(shí)，2-路插入排序就完全失去了它的優(yōu)越性。v表插入排序表插入排序10.2 插入排序插入排序(1) 基本思想 通過改變排序過程中采用的存儲(chǔ)結(jié)構(gòu)，減少

14、在排序過程中進(jìn)行“挪動(dòng)記錄的操作。利用靜態(tài)鏈表進(jìn)行排序，并在排序完成之后，一次性地調(diào)整各個(gè)記錄相互之間的位置，即將每個(gè)記錄都調(diào)整到它們所應(yīng)該在的位置上。v表插入排序表插入排序10.2 插入排序插入排序#define MAXSIZE 100 /靜態(tài)鏈表容量Typedef struct RcdType rc; /記錄項(xiàng) int next; /指針項(xiàng) SLNode; /表結(jié)點(diǎn)類型Typedef struct SLNode rMAXSIZE+1; /0號(hào)單元為表頭結(jié)點(diǎn) int length; /鏈表當(dāng)前長度 SLinkListType; /靜態(tài)鏈表類型(2) 待排記錄序列的存儲(chǔ)結(jié)構(gòu)v表插入排序表插入排

15、序10.2 插入排序插入排序(3) 具體做法 首先將靜態(tài)鏈表中數(shù)組下標(biāo)為“1的分量(結(jié)點(diǎn))和表頭結(jié)點(diǎn)構(gòu)成一個(gè)循環(huán)鏈表，然后依次將下標(biāo)為“2至“n的分量(結(jié)點(diǎn))按記錄關(guān)鍵字非遞減有序插入到循環(huán)鏈表中。10.2 插入排序插入排序void TableSort(int *a, int n) nexthead = 0 = -1; for (i=1; in; i+) if (ai = ahead) nexti = head; head = i; else p = head; while (nextp!=-1 & anextpai) p = nextp; nexti = nextp; nextp =

16、 i; 初始狀態(tài)012345678MAXINT493865977613274910-i=3012345678MAXINT4938659776132749201-key域next域i=2012345678MAXINT493865977613274910-38123650i=4012345678MAXINT49386597761327492310-9740i=5012345678MAXINT493865977613274923140-i=6012345678MAXINT4938659776132749231504-i=7012345678MAXINT49386597761327496315042-

17、i=8012345678MAXINT493865977613274963150472-7645136227724938v表插入排序表插入排序10.2 插入排序插入排序(4) 表插入排序性能分析 從表插入排序的過程可見，表插入排序的基本操作仍是將一個(gè)記錄插入到已排好序的有序表當(dāng)中。和直接插排序相比，不同之處僅是以修改2n次指針值代替移動(dòng)記錄，排序過程中所需進(jìn)行的關(guān)鍵字間的比較次數(shù)相同。因此表插入排序的時(shí)間復(fù)雜度仍是O(n2)。v表插入排序表插入排序10.2 插入排序插入排序(4) 表插入排序性能分析 表插入排序的結(jié)果只是求得一個(gè)有序鏈表，則只能對它進(jìn)行順序查找，不能進(jìn)行隨機(jī)查找，為了能實(shí)現(xiàn)有序表

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

19、排序插入排序基本思想：先將整個(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希爾排序希爾排序10.2 插入

20、排序插入排序38例：關(guān)鍵字序列 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 的值較大，子序列中的對象較少，排序速

21、度較快；隨著排序進(jìn)展，dk 值逐漸變小，子序列中對象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。v希爾排序算法描述希爾排序算法描述10.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.key L.rj.key);j -= dk) L.rj+dk = L.rj; / 記錄后

22、移，查找插入位置 L.rj+dk = L.r0; / 插入 /ShellInsertv希爾排序算法描述希爾排序算法描述10.2 插入排序插入排序void ShellSort (SqList &L, int dlta , int t) / 按增量序列按增量序列dlta0.t-1對順序表對順序表L作希爾排序作希爾排序 for (k=0; k1; i-) /i表示趟數(shù)，最多表示趟數(shù)，最多n-1趟趟 flag=0; /開始時(shí)元素未交換開始時(shí)元素未交換 for (int j=2; j=i; j+) if (RjRj-1) /發(fā)生逆序發(fā)生逆序 temp=Rj; Rj=Rj-1; Rj-1=temp

23、; flag=1; if(flag=0) return; / Bubblesortv冒泡排序算法分析冒泡排序算法分析10.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快速排序快速排序10.3 交換排序交換排序背景 起泡排序的過程可見，起泡排序是一個(gè)增加有序序列長度的過程，也是一個(gè)縮小無序序列長度的過程，每經(jīng)過一趟起泡，無序序列的長度只縮小1。 試設(shè)想：若

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

25、與樞軸記錄相互交換。 3.重復(fù)這兩步直至low=high為止。v快速排序快速排序10.3 交換排序交換排序lowhigh設(shè)Rs=52 為樞軸例： 52 52 49 80 36 14 58 61 97 23 75 high23 lowlow80highhighhighhigh14lowlow52v一趟快速排序算法描述一趟快速排序算法描述10.3 交換排序交換排序int Partition (Elem R , int low, int high) R0 = Rlow; pivotkey = Rlow.key; while (low high) /從兩端交替向中間掃描從兩端交替向中間掃描 while

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

27、趟快速排序 有 序 的 記 錄 序 列 v快速排序算法描述快速排序算法描述10.3 交換排序交換排序void QSort ( Elem R , int low, int high ) /對序列對序列Rlow.high進(jìn)行快速排序進(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); / 對高子表遞歸排序?qū)Ω咦颖磉f歸排序 /

28、QSortvoid QuickSort(Elem R, int n) /對記錄序列進(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，751，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

29、，129，937，863，742，694，076，438為例，寫出執(zhí)行快速算法的各趟排序結(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歸性，要用到棧空間穩(wěn) 定 性：不穩(wěn)定 因?yàn)榭蛇x任一元素為支點(diǎn)。v快速排序算法詳細(xì)分

30、析快速排序算法詳細(xì)分析10.3 交換排序交換排序可以證明，函數(shù)Quicksort的平均計(jì)算時(shí)間是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個(gè)?？焖倥判蚴沁f歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)(新的low和high)。最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為 log2(n+1) 。因此，要求存儲(chǔ)開銷為 O(log2n)。v快速排序算法詳細(xì)分析快速排序算法詳細(xì)分析10.3 交換排序交換排序最好情況：如果每次劃分對一個(gè)對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個(gè)長度減半的子序列進(jìn)行排序，這是最理

31、想的情況。此時(shí)，快速排序的趟數(shù)最少。最壞情況：即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個(gè)比上一次少一個(gè)對象的子序列。這樣，必須經(jīng)過 n-1 趟才能把所有對象定位，而且第 i 趟需要經(jīng)過 n-i 次關(guān)鍵碼比較才能找到第 i 個(gè)對象的安放位置，總的關(guān)鍵碼比較次數(shù)將達(dá)到n2/2v快速排序是否真的比任何排序算法都快？快速排序是否真的比任何排序算法都快？10.3 交換排序交換排序設(shè)每個(gè)子表的支點(diǎn)都在中間比較均衡），那么：第1趟比較，可以確定1個(gè)元素的位置；第2趟比較2個(gè)子表），可以再確定2個(gè)元素的位置；第3趟比較4個(gè)子表），可以再確定4個(gè)元素的位置；第4趟比較8個(gè)子表），可以再確定8個(gè)元素的位置； 只需log2n 1趟便可排好序?；旧鲜?！因?yàn)槊刻丝梢源_定的數(shù)據(jù)元素是呈指數(shù)增加的！而且，每趟需要比較和移動(dòng)的元素也呈指數(shù)下降，加上編程時(shí)使用了交替逼近技巧，更進(jìn)一步減少了移動(dòng)次數(shù)，所以速度特別快