數(shù)據(jù)結構第四講

1、9.1 基本排序排序：給定一組記錄的集合r1, r2, , rn，其相應的關鍵字分別為k1, k2, , kn，排序是將這些記錄排列成順序為rs1, rs2, , rsn的一個序列，使得相應的關鍵字滿足ks1ks2ksn（稱為升序）或ks1ks2ksn（稱為降序）。待排序序列中的記錄已按關鍵字排好序。逆序（反序）：待排序序列中記錄的排列順序與排好序的順序正好相反。注: 沒有特別說明,均按遞增順序排序.排序算法的穩(wěn)定性：假定在待排序的記錄集中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，即在原序列中，ki=kj且ki在kj之前，而在排序后的序列中，ki仍在kj之前，則

2、稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。 9.1 基本排序1. 內(nèi)排序在排序過程中的基本操作：比較：關鍵字之間的比較；移動：記錄從一個位置移動到另一個位置。 2. 輔助存儲空間。3.算法本身的復雜程度。 排序算法的性能9.2 插入排序插入排序的基本思想：插入排序有多種具體實現(xiàn)算法： 1) 直接插入排序 2) 希爾排序 每次將一個待排序的記錄，按其關鍵字大小，插入到前面已經(jīng)排好序的文件中的適當位置上，直到全部記錄插入完成為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。9.2.1 直接插入排序新元素插入到哪里？思想:假設待排記錄存于Rn(R1-Rn-1共n-1個元素),若排序的某一時刻

3、R被分為兩個子區(qū): R1Ri-1和RiRn-1關鍵:如何將Ri插入到當前有序區(qū)的適當位置? 假設只有一個記錄的有序表是有序的,在已形成的有序表中進行比較，并在適當位置插入，把原來位置上的元素向后順移。最簡單的排序法！分析:與當前有序區(qū)中最后一個記錄Rj進行比較: 若Ri.key=Rj.key,則j+1為Ri插入位置.9.2.1 直接插入排序例：關鍵字序列T=（13，6，3，31，9，27，5，11）， 請寫出直接插入排序的中間過程序列。 【13】, 6, 3, 31, 9, 27, 5, 11第一趟:【6, 13】, 3, 31, 9, 27, 5, 11第二趟: 【3, 6, 13】, 31

4、, 9, 27, 5, 11第三趟: 【3, 6, 13，31】, 9, 27, 5, 11第四趟: 【3, 6, 9, 13，31】, 27, 5, 11第五趟: 【3, 6, 9, 13，27, 31】, 5, 11第六趟: 【3, 5, 6, 9, 13，27, 31】, 11第七趟: 【3, 5, 6, 9, 11，13，27, 31】 9.2.1 直接插入排序直接插入排序算法性能分析最好情況下（正序）： 12345時間復雜度為O(n)。比較次數(shù)：Cmin=n-1移動次數(shù)：Mmin=2(n-1) 123452123453123454123455最壞情況下（逆序或反序）： 比較次數(shù)：移動

5、次數(shù)：54321453214345213234512123451時間復雜度為O(n2)。 9.2.1 直接插入排序平均時間復雜度為O(n2)?？臻g復雜度:O(1). 若待排序對象序列中出現(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。小結：直接插入排序是一種穩(wěn)定的排序算法。9.2.2 希爾排序（又稱縮小增量排序）基本思想：先取一個正整數(shù)d1n,把全部記錄分成d1個組，所有距離為d1倍數(shù)的記錄放在一組，在各組內(nèi)進行直接插入排序；然后取d2d1，重復上述分組和排序工作，直至取d1=1，即所有記錄放在一組中排序為止。技巧：希爾排序中增量di有多種取法，我們可選取如d1=n/2,di

6、+1=di/2。優(yōu)點：讓關鍵字小的元素很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。9.2.2 希爾排序1 2 3 4 5 6 7 8 94021254925*16初始序列300813d = 44021254925*16300813252125*300849131640d = 21325210825*16304940252125*300813164049d = 10825211325*16304049082513162125*403049希爾排序是一種不穩(wěn)定的排序算法。9.3 交換排序交換排序的基本思想是： 兩兩比較待排序記錄的關鍵字，如果發(fā)生逆序（即排列順序與排序后的

7、次序正好相反），則交換之，直到所有記錄都排好序為止。交換排序的主要算法有： 1) 起泡排序 2) 快速排序9.3.1 起泡排序基本思路：將待排記錄縱向排列,自下而上兩兩比較相鄰記錄關鍵字kj與kj-1的值,若反序則二者交換位置,繼續(xù)比較kj-1與kj-2,直到全部記錄比較一遍，則一趟結束。優(yōu)點：每趟結束時，不僅能使當前最小關鍵字上升到其應該所在位置，還能同時部分理順其他元素。9.3.1 起泡排序起泡排序需多少趟,每趟需比較次數(shù)?第1趟:n-1次第2趟:n-2次(至多)第n-1趟:1次一旦下趟沒有交換發(fā)生，還可以提前結束排序。如何確定何時結束排序？ 設標志位noswap來表示每一趟是否有交換：

8、即：每趟開始之前，設noswap=1，若交換則改noswap=0；只需每趟結束后觀察noswap的值即可。9.3.1 起泡排序冒泡排序的算法分析時間效率：O（n2) 空間效率：O（1）穩(wěn) 定 性： 穩(wěn)定詳細分析：最好情況：初始排列已經(jīng)有序，只執(zhí)行一趟起泡，做 n-1 次關鍵碼比較，不移動對象。O(n)最壞情形：初始排列逆序，算法要執(zhí)行n-1趟起泡，第i趟(1 i n) 做了n- i 次關鍵碼比較，執(zhí)行了n-i 次對象交換。此時的比較總次數(shù)和記錄移動次數(shù)為：O（n2）O（n2）9.3.2 快速排序 假設待排記錄Rl-Rh,任取一個記錄 (通常取無序區(qū)第一個記錄) 作為比較的基準temp，以其關鍵

9、字的值為分界點將全部記錄劃分為兩部分:所有比它小的元素均位于分界點左側(Rl-Ri-1)，所有比它大的元素均位于分界點右側(Ri+1-Rh),則基準temp就位于其最終正確位置Ri;然后再分別對這兩部分無序區(qū)重復上述過程，直到每一部分均只剩一個記錄為止。 (又稱劃分交換排序)基本思想：9.3.2 快速排序解決方法：設待劃分的序列是Rl-Rh，設指針i，j分別指向該區(qū)域左、右兩端的下標l和h，令Rl為基準temp.（1）j向左掃描:j-，找到第一個比基準小的記錄Rj，與Ri交換；（2）i向右掃描:i+，找到第一個比基準大的記錄Ri，與Rj交換；（3）重復上述過程，直到i=j,此時i便為基準最終所

10、在位置。關鍵問題：如何實現(xiàn)一次劃分？快速排序算法分析(了解)9.3.2 快速排序例：49,38,65,97,76,13,27,49的快速排序遞歸樹如下：快速排序的遞歸執(zhí)行過程可以用遞歸樹描述?？焖倥判虻男阅芊治?927769749653838139.3.2 快速排序快速排序算法效率分析：空間復雜度:遞歸調(diào)用時每次的指針,參數(shù)需用棧存放,則與遞歸樹的深度一致. 最好情況:每次劃分將文件均分為兩部分,則O(log2n) 最壞情況:遞歸深度為n,一邊倒,則 O(n)時間復雜度: 最好情況:每次都均等分,則Cmin=O(nlog2n) 最壞情況:一邊倒,每次劃分無序區(qū)記錄只少一個,需進行n-1趟排序,

11、每趟n-i次比較,則Cmax= O(n2) 小結:平均時間復雜度:O(nlog2n) 快速排序是一種不穩(wěn)定的排序算法.9.4 選擇排序選擇排序有多種具體實現(xiàn)算法： 1) 直接選擇排序 2) 堆排序基本思想：每一趟從待排記錄中選取關鍵字最小的記錄,順序放在已排好序的記錄序列后面,直至全部記錄排完為止。9.4.1 直接選擇排序思路簡單：每經(jīng)過一趟比較就找出一個最小值，與待排序列最前面的位置互換即可。首先，在n個記錄中選擇最小者放到R0位置；然后，從剩余的n-1個記錄中選擇最小者放到R1位置；如此進行下去，直到全部有序為止。優(yōu)點：實現(xiàn)簡單缺點：每趟只能確定一個元素，表長為n時需要n-1趟9.4.1

12、直接選擇排序例：關鍵字序列T= （21，25，49，25*，16，08），請給出直接選擇排序的具體實現(xiàn)過程。原始序列： 21，25，49，25*，16，08直接選擇排序第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，49算法的穩(wěn)定性：不穩(wěn)定因為排序時，25*到了25的前面。最小值 08 與R0交換位置9.4.1 直接選擇排序最壞情況(反序)：3(n-1)次直接選擇排序算法的性能分析移動次數(shù)：與文件的初始狀態(tài)有關.最好情況（正序）：

13、0次空間性能：需一個輔助空間,O(1)。穩(wěn)定性：是一種不穩(wěn)定的排序算法。比較次數(shù)：與文件的初始狀態(tài)無關.直接選擇排序的平均時間復雜度為O(n2)。9.4.2 堆排序1. 什么是堆？堆的定義：設有n個元素的序列 k1，k2，kn，當且僅當滿足下述關系之一時，稱之為堆。 ki k2iki k2i+1ki k2iki k2i+1或者i=1, 2, n/2解釋：如果讓滿足以上條件的元素序列 （k1，k2，kn）順次排成一棵完全二叉樹，則此樹的特點是： 樹中所有結點的值均大于（或小于）其左右孩子，此樹的根結點（即堆頂）必最大（或最?。?則稱為大根堆(或小根堆)2. 怎樣建堆？3. 怎樣堆排序？9.4.2

14、 堆排序082546495867234561（大根堆）918566765867234561557例：有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判斷它們是否 “堆”？（小根堆）9.4.2 堆排序步驟：從最后一個非終端結點開始往前逐步調(diào)整，讓每個雙親大于（或小于）子女，直到根結點為止。212525*491608123456例：關鍵字序列T= (21，25，49，25*，16，08），請建大根堆。2. 怎樣建堆？解：為便于理解，先將原始序列畫成完全二叉樹的形式：完全二叉樹的第一個非終端結點編號必為n/2 注：終端

15、結點（即葉子）沒有任何子女，無需單獨調(diào)整。21i=3: 49大于08，不必調(diào)整；i=2: 25大于25*和16，也不必調(diào)整；i=1: 21小于25和49，要調(diào)整！49而且21還應當向下比較！9.4.2 堆排序思想：利用大(小)根堆來選取關鍵字最大(小)記錄.(本書使用大根堆)3. 怎樣堆排序？過程：(1) 初始化堆:將n個元素按關鍵字建成大根堆;(2) 交換:將堆頂元素與當前無序區(qū)中最后一個記錄交換;(3) 重建堆:將剩余n-1個元素重建成大根堆.反復(2)(3) 步,則有后向前形成有序區(qū).9.4.2 堆排序堆排序算法分析：時間效率： O(nlog2n)空間效率：O(1)穩(wěn)定性： 不穩(wěn)定。9.

16、5 歸并排序基本思想：將兩個（或以上）的有序表組成新的有序表。更實際的意義：可以把一個長度為n 的無序序列看成是 n 個長度為 1 的有序子序列 ，首先做兩兩歸并，得到 n / 2 個長度為 2 的子序列 ；再做兩兩歸并，如此重復，直到最后得到一個長度為 n 的有序序列。例：關鍵字序列T= （21，25，49，25*，93，62，72，08，37，16，54），請給出歸并排序的具體實現(xiàn)過程。212525*9362720837165449212525*4962930872163754163754212525*490862729308212525*496272930816212525*374954

17、627293len=1len=2len=4len=8len=161637549.6 分配排序基本思想：分配+收集箱排序：設置若干個箱子,將關鍵字為k的記錄放入第k個箱子,然后在按序號將非空的連接.基數(shù)排序：數(shù)字是有范圍的,均由0-9這十個數(shù)字組成,則只需設置十個箱子,相繼按個、十、百進行排序.基數(shù)排序是一個穩(wěn)定的排序算法.（614，738，921，485，637， 101，215，530，790，306）例:614921485637738101215530790306第一趟分配(按個位排)e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921215637101485530

18、790306第一趟收集5307909211016144852153066377389.6 分配排序第一趟收集的結果：e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306第二趟分配（按十位排 ）第二趟收集5307909211016144852153066377385307909211016144852153066377389.6 分配排序第二趟收集的結果：e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306第三趟分配（按百位排 ）第三趟收集530790921101614485215306637738530790921101614485215306637