數(shù)據結構課件：第10章 排序1插入排序和交換排序

1、第10章 內部排序選擇排序 (直接排序、堆排序)概述插入排序 (直接排序、折半排序、希爾排序)交換排序 (冒泡排序、快速排序)歸并排序基數(shù)排序概述10.1 概述排序：將數(shù)據元素的一個任意序列，重新排列成一個按關鍵字有序的序列。 例：將關鍵字序列：52, 49, 80, 36, 14, 58, 61, 23 調整為：14, 23, 36, 49, 52, 58, 61, 80 若按主關鍵字排序則結果惟一若按次關鍵字排序則結果可以不惟一(因有相同關鍵字) 概述10.1 概述 設 Ki、Kj (1in, 1jn, ij ) 分別為記錄 Ri、Rj 的關鍵字，且 Ki = Kj ，在排序前的序列中 R

2、i 領先于 Rj (即 i j )。若在排序后的序列中 Ri 仍領先于 Rj ，則稱所用的排序方法是穩(wěn)定的；反之，則稱所用的排序方法是不穩(wěn)定的。 例：設排序前的關鍵字序列為：52, 49, 80, 36, 14, 58, 36, 23 若排序后的關鍵字序列為：14, 23, 36, 36, 49, 52, 58, 80， 則排序方法是穩(wěn)定的。 若排序后的關鍵字序列為：14, 23, 36, 36, 49, 52, 58, 80， 則排序方法是不穩(wěn)定的。 概述10.1 概述內部排序和外部排序 若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內部排序； 反之，若參加排序的記錄數(shù)量很大，整個

3、序列的排序過程不可能在內存中完成，則稱此類排序問題為外部排序。 插入排序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 =7 384965769713274927i =8 3849657697132749494938659776132749 3849387 趟 排序 1 趟 排序 2 趟 排序 排序過程：先將序列中第 1 個

4、記錄看成是一個有序子序列， 然后從第 2 個記錄開始，逐個進行插入，直至整個序列有序。 直接插入排序10.2 插入排序void InsertSort ( SqList &L ) / 對順序表 L 作直接插入排序。 for ( i = 2; i = L.length; + i ) if (L.ri.key L.ri -1.key) / InsertSort 在 r1. i-1中查找 ri 的插入位置; 對于在查找過程中找到的那些關鍵字 不小于 ri.key 的記錄，在查找的同 時實現(xiàn)記錄向后移動； 插入 ri ;L.r0 = L.ri; / 復制為監(jiān)視哨 L.ri = L.ri -1; for

5、( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 記錄后移 L.r j + 1 = L.r0; / 插入到正確位置 直接插入排序性能分析 10.2 插入排序比較次數(shù)： 移動次數(shù)： 0 最好的情況：待排序記錄按關鍵字從小到大排列（正序） 比較次數(shù)： 移動次數(shù)： 最壞的情況：待排序記錄按關鍵字從大到小排列（逆序） 直接插入排序性能分析 10.2 插入排序 由于待排記錄序列是隨機的，取上述二值的平均值。所以直接插入排序的時間復雜度為O(n2)。 直接插入排序是“穩(wěn)定的”：關鍵碼相同的兩個記錄，在整個排序過程中，不會通過比較

6、而相互交換。折半插入排序10.2 插入排序(1) 基本思想 考慮到 L.r1,.,i-1 是按關鍵字有序的有序序列，則可以利用折半查找實現(xiàn)“L.r1,i-1中查找 L.ri 的插入位置”如此實現(xiàn)的插入排序為折半插入排序。例：有6個記錄，前5個已排序的基礎上，對第6個記錄排序。 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折半插入排序在尋找插入位置時，不是逐個比較而是利用折半查找的

7、原理尋找插入位置。待排序元素越多，改進效果越明顯。折半插入排序算法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.r0; / 插入 / BInsertSort折半插入排序

8、算法分析10.2 插入排序 折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。 折半插入排序減少了關鍵字的比較次數(shù)，但記錄的移動次數(shù)不變，其時間復雜度與直接插入排序相同。 在插入第 i 個對象時，需要經過 log2i +1 次關鍵碼比較，才能確定它應插入的位置。 折半插入排序是一個穩(wěn)定的排序方法。2-路插入排序10.2 插入排序(1) 基本思想 2-路插入排序是在折半插入排序的基礎上改進的，目的是減少排序過程中移動記錄的次數(shù)，但為此需要n個記錄的輔助空間。2-路插入排序10.2 插入排序(2) 具體做法 另設一個和 L.r 同類型的數(shù)組d，首先將 L.r1 賦值給d1 ，

9、并將d1看成是在排好序的序列中處于中間位置的記錄，然后從 L.r中第 2 個記錄起依次插入到d1之前或之后的有序序列中。先將待插入記錄的關鍵字和d1 的關鍵字進行比較。 若 L.rid1.key，則將 L.ri 插入到d1 之前的有序表中。反之，插入到d1 之后的有序表中?！境跏缄P鍵字】 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 97) (38)i=5: (49 65 76 97) (38)i=6: (49 65 76 97) (13 38)i=7: (49

10、 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的第一個記錄為d中排好序的記錄。 int first = 0, final = 0;/first、final分別指示d中排好序的記錄的第1個和最后1個記錄的位置 for (int i = 2; i = l

11、ength; +i) /依次將L的第2個最后一個記錄插入d中。 if (Li dfinal) /待插入記錄大于d中最小值，插入到dfinal之后 final = final + 1; dfinal = Li; else /待插入記錄大于d中最小值，小于d中最大值，插入到d的中間(需要移動d數(shù)組) int j = final +;/移動d尾部元素以便按序插入記錄。 while (Li dj) d(j + 1) % length = dj; j = (j - 1 + length) % length; dj + 1 = Li; for (int i = 1; i = length; i +) /循

12、環(huán)把d賦給L。 Li = d(i + first - 1) % length;/線性關系。 2-路插入排序10.2 插入排序 2-路插入排序只能減少移動記錄的次數(shù)，而不能絕對避免移動記錄。 2-路插入排序中，移動記錄的次數(shù)約為n2/8 。 當L.r1是待排序記錄中關鍵字最小或最大的記錄時，2-路插入排序就完全失去了它的優(yōu)越性。表插入排序10.2 插入排序(1) 基本思想 通過改變排序過程中采用的存儲結構，減少在排序過程中進行“移動”記錄的操作。利用靜態(tài)鏈表進行排序，并在排序完成之后，一次性地調整各個記錄相互之間的位置，即將每個記錄都調整到它們所應該在的位置上。表插入排序10.2 插入排序#de

13、fine MAXSIZE 100 /靜態(tài)鏈表容量Typedef struct RcdType rc; /記錄項 int next; /指針項 SLNode; /表結點類型Typedef struct SLNode rMAXSIZE+1; /0號單元為表頭結點 int length; /鏈表當前長度 SLinkListType; /靜態(tài)鏈表類型(2) 待排記錄序列的存儲結構表插入排序10.2 插入排序(3) 具體做法 首先將靜態(tài)鏈表中數(shù)組下標為“1”的分量(結點)和表頭結點構成一個循環(huán)鏈表，然后依次將下標為“2”至“n”的分量(結點)按記錄關鍵字非遞減有序插入到循環(huán)鏈表中。10.2 插入排序vo

14、idTableSort(int*a,intn) 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=i; 初始狀態(tài)012345678MAXINT493865977613274910-i=3012345678MAXINT4938659776132749201-key域next域i=2012345678MAXINT493865977613274910-38123650i=4012345678M

15、AXINT49386597761327492310-9740i=5012345678MAXINT493865977613274923140-i=6012345678MAXINT4938659776132749231504-i=7012345678MAXINT49386597761327496315042-i=8012345678MAXINT493865977613274963150472-7645136227724938表插入排序10.2 插入排序(4) 表插入排序性能分析 從表插入排序的過程可見，表插入排序的基本操作仍是將一個記錄插入到已排好序的有序表當中。和直接插排序相比，不同之處僅是以修

16、改2n次指針值代替移動記錄，排序過程中所需進行的關鍵字間的比較次數(shù)相同。因此表插入排序的時間復雜度仍是O(n2)。表插入排序10.2 插入排序(4) 表插入排序性能分析 表插入排序的結果只是求得一個有序鏈表，則只能對它進行順序查找，不能進行隨機查找，為了能實現(xiàn)有序表的折半查找，尚需對記錄進行重新排列。10.2 插入排序1.我們都能理解，優(yōu)秀排序算法的首要條件就是2.于是人們想了許許多多的排序辦法，目的就是為了提高排序的速度。3.而在很長的時間里，眾人發(fā)現(xiàn)盡管各種排序算法花樣繁多，但時間復雜度都是O(n2)，似乎沒法超越了。4.計算機學術界充斥著“排序算法不可能突破O(n2)”的聲音？速度10.

17、2 插入排序 終于有一天，當一位科學家發(fā)布超越了O(n2)新排序算法后，緊接著就出現(xiàn)了好幾種可以超越O(n2)的排序算法，并把內排序算法的時間復雜度提升到了O(nlog2n)?！安豢赡艹絆(n2) ”徹底成為了歷史。希爾排序10.2 插入排序基本思想：先將整個待排記錄序列分割成若干子序列,分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。技巧：子序列的構成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk1為止。優(yōu)點：讓關鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序

18、處理，時間效率會高很多。312345665499725251321234562525136549971123456132525654997123456132525496597增量3增量2增量1希爾排序過程希爾排序10.2 插入排序38例：關鍵字序列 T=(49, 38, 65, 97, 76, 13, 27, 49*, 55, 04) 請寫出希爾排序的具體實現(xiàn)過程。0123456789104938659776132749*5504初 態(tài)第1趟 (dk=5)第2趟 (dk=3)第3趟 (dk=1)4913134938276549*975576042738 65 49*97551355760455

19、13270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 ri算法分析：開始時dk 的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，dk 值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎，大多數(shù)對象已基本有序，所以排序速度仍然很快。希爾排序算法描述10.2 插入排序void ShellInsert ( SqList &L, int dk ) /一趟希爾插入排序 /1.前后記錄位置的增量是dk； /2.L.r0只是暫存單元，不是哨兵。當j=0時，插入位置已找到 for ( i=dk

20、+1; i=L.length; +i ) if ( L.ri.key0 & (L.r0.key L.rj.key);j -= dk) L.rj+dk = L.rj; / 記錄后移，查找插入位置 L.rj+dk = L.r0; / 插入 /ShellInsert希爾排序算法描述10.2 插入排序void ShellSort (SqList &L, int dlta , int t) / 按增量序列dlta0.t-1對順序表L作希爾排序 for (k=0; k1; i-) /i表示趟數(shù)，最多n-1趟 flag=0; /開始時元素未交換 for (int j=2; j=i; j+) if (RjRj

21、-1) /發(fā)生逆序 temp=Rj; Rj=Rj-1; Rj-1=temp; flag=1; if(flag=0) return; / Bubblesort冒泡排序算法分析10.3 交換排序正序： 只需進行一趟排序，在排序過程中進行n-1次關鍵字間的比較，且不移動記錄；時間復雜度為O(n) 。逆序： 需要進行n-1趟排序，需要進行n(n-1)/2次比較，并作等數(shù)量級的記錄移動?？偟臅r間復雜度為O(n2) 。 起泡排序方法是穩(wěn)定的。適合于數(shù)據較少的情況?？焖倥判?0.3 交換排序背景 起泡排序的過程可見，起泡排序是一個增加有序序列長度的過程，也是一個縮小無序序列長度的過程，每經過一趟起泡，無序序

22、列的長度只縮小1。 試設想：若能在經過一趟排序，使無序序列的長度縮小一半，則必能加快排序的速度?？焖倥判?0.3 交換排序(1) 基本思想 通過一趟排序將待排序列以樞軸為標準劃分成兩部分，使其中一部分記錄的關鍵字均比另一部分小，再分別對這兩部分進行快速排序，以達到整個序列有序。 通常取第一個記錄的值為基準值或樞軸?？焖倥判?0.3 交換排序(2) 具體做法 附設兩個指針low和high，初值分別指向第一個記錄和最后一個記錄，設樞軸為key； 1.從high 所指位置起向前搜索，找到第一個不大于基準值的記錄與樞軸記錄相互交換； 2.從low 所指位置起向后搜索，找到第一個不小于基準值的記錄與樞軸

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

24、igh; /將比樞軸記錄小的移到低端 while (low high & Rlow.key = pivotkey) + + low; Rhigh = Rlow; /將比樞軸記錄大的移到高端 Rlow = R0; /樞軸記錄到位 return low; /返回樞軸位置 / Partition快速排序算法過程 10.3 交換排序無 序 的 記 錄 序 列無序記錄子序列 (1)無序子序列 (2) 樞軸 一次劃分 分別進行一趟快速排序 有 序 的 記 錄 序 列 快速排序算法描述10.3 交換排序void QSort ( Elem R , int low, int high ) /對序列Rlow.hi

25、gh進行快速排序 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) /對記錄序列進行快速排序 QSort(R, 1, n); / QuickSort076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742

26、，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例：以關鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行快速算法的各趟排序結束時，關鍵字序列的狀態(tài)。原始序列： 256，301，751，129，937，863，742，694，076，438第1趟第2趟第3趟第4趟要求模擬算法實現(xiàn)步驟25607630112975125675143807

27、6，129，256，301，438，694，742，751，863，937時間效率：O(nlog2n) 因為每趟確定的元素呈指數(shù)增加空間效率：O(log2n)因為算法的遞歸性，要用到棧空間穩(wěn) 定 性：不穩(wěn)定 因為可選任一元素為支點?？焖倥判蛩惴ㄔ敿毞治?0.3 交換排序可以證明，函數(shù)Quicksort的平均計算時間是O(nlog2n)。實驗結果表明：就平均計算時間而言，快速排序是我們所討論的所有內排序方法中最好的一個。快速排序是遞歸的，需要有一個棧存放每層遞歸調用時的指針和參數(shù)(新的low和high)。最大遞歸調用層次數(shù)與遞歸樹的深度一致，理想情況為 log2(n+1) 。因此，要求存儲開銷為

28、 O(log2n)?？焖倥判蛩惴ㄔ敿毞治?0.3 交換排序最好情況：如果每次劃分對一個對象定位后，該對象的左側子序列與右側子序列的長度相同，則下一步將是對兩個長度減半的子序列進行排序，這是最理想的情況。此時，快速排序的趟數(shù)最少。最壞情況：即待排序對象序列已經按其關鍵碼從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列。這樣，必須經過 n-1 趟才能把所有對象定位，而且第 i 趟需要經過 n-i 次關鍵碼比較才能找到第 i 個對象的安放位置，總的關鍵碼比較次數(shù)將達到n2/2快速排序是否真的比任何排序算法都快？10.3 交換排序設每個子表的支點都在中間（比較均衡），則：第1趟比較，可以確定1個元素的位置；第2趟比較（2個子表），可以再確定2個元素的位置；第3趟比較（4個子表），可以再確定4個元素的位置；第4趟比較（8個子表），可以再確定8個元素的位置； 只需log2n 1趟便可排好序?；旧鲜?！因為每