數(shù)據(jù)結(jié)構(gòu)第四講

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

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

3、R被分為兩個(gè)子區(qū): R1Ri-1和RiRn-1關(guān)鍵:如何將Ri插入到當(dāng)前有序區(qū)的適當(dāng)位置? 假設(shè)只有一個(gè)記錄的有序表是有序的,在已形成的有序表中進(jìn)行比較，并在適當(dāng)位置插入，把原來(lái)位置上的元素向后順移。最簡(jiǎn)單的排序法！分析:與當(dāng)前有序區(qū)中最后一個(gè)記錄Rj進(jìn)行比較: 若Ri.key=Rj.key,則j+1為Ri插入位置.9.2.1 直接插入排序例：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11）， 請(qǐng)寫出直接插入排序的中間過(guò)程序列。 【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時(shí)間復(fù)雜度為O(n)。比較次數(shù)：Cmin=n-1移動(dòng)次數(shù)：Mmin=2(n-1) 123452123453123454123455最壞情況下（逆序或反序）： 比較次數(shù)：移動(dòng)

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

6、+1=di/2。優(yōu)點(diǎn)：讓關(guān)鍵字小的元素很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。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 交換排序交換排序的基本思想是： 兩兩比較待排序記錄的關(guān)鍵字，如果發(fā)生逆序（即排列順序與排序后的

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

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

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

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

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

12、直接選擇排序例：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)給出直接選擇排序的具體實(shí)現(xiàn)過(guò)程。原始序列： 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)定因?yàn)榕判驎r(shí)，25*到了25的前面。最小值 08 與R0交換位置9.4.1 直接選擇排序最壞情況(反序)：3(n-1)次直接選擇排序算法的性能分析移動(dòng)次數(shù)：與文件的初始狀態(tài)有關(guān).最好情況（正序）：

13、0次空間性能：需一個(gè)輔助空間,O(1)。穩(wěn)定性：是一種不穩(wěn)定的排序算法。比較次數(shù)：與文件的初始狀態(tài)無(wú)關(guān).直接選擇排序的平均時(shí)間復(fù)雜度為O(n2)。9.4.2 堆排序1. 什么是堆？堆的定義：設(shè)有n個(gè)元素的序列 k1，k2，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆。 ki k2iki k2i+1ki k2iki k2i+1或者i=1, 2, n/2解釋：如果讓滿足以上條件的元素序列 （k1，k2，kn）順次排成一棵完全二叉樹，則此樹的特點(diǎn)是： 樹中所有結(jié)點(diǎn)的值均大于（或小于）其左右孩子，此樹的根結(jié)點(diǎn)（即堆頂）必最大（或最?。?則稱為大根堆(或小根堆)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 堆排序步驟：從最后一個(gè)非終端結(jié)點(diǎn)開始往前逐步調(diào)整，讓每個(gè)雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。212525*491608123456例：關(guān)鍵字序列T= (21，25，49，25*，16，08），請(qǐng)建大根堆。2. 怎樣建堆？解：為便于理解，先將原始序列畫成完全二叉樹的形式：完全二叉樹的第一個(gè)非終端結(jié)點(diǎn)編號(hào)必為n/2 注：終端

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

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

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

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