T13-基于線性表的排序算法

基于線性表的排序算法第七章主講：周翔回顧請簡述索引順序查找的算法思想。請思考如何處理哈希沖突。預習檢查請描述一下冒泡排序的算法思想。請描述一下堆排序的算法思想。本章目標3磁盤排序重點了解掌握2歸并排序基數(shù)排序交換排序插入排序選擇排序1排序的基本概念什么是排序：排序的定義：對于計算機中存儲的數(shù)據(jù)來說，排序就是將一組“無序”的記錄，通過一定的方式，按照某種關(guān)鍵字順序排列調(diào)整為“有序”的記錄，從而提高數(shù)據(jù)查找的效率。概括：將一組雜亂無章的數(shù)據(jù)按一定規(guī)律順次排列起來。排序的目的是什么？便于查找！排序的基本概念排序的分類：根據(jù)數(shù)據(jù)存儲位置的不同，排序可分為內(nèi)部排序和外部排序：若所有需要排序的數(shù)據(jù)都存放在內(nèi)存中，在內(nèi)存中調(diào)整數(shù)據(jù)的存儲順序，這樣的排序稱為內(nèi)部排序；若待排序記錄數(shù)據(jù)量較大，排序時只有部分數(shù)據(jù)被調(diào)入內(nèi)存，排序過程中存在多次內(nèi)、外存之間的交換，這樣的排序稱為外部排序。注：外部排序時，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時放入外存，顯然外部排序要復雜得多。排序的基本概念在排序過程中，一般進行兩種基本操作：比較兩個關(guān)鍵字的大??；將記錄從一個位置移動到另一個位置。對于第二種操作，需要采用適當?shù)卮鎯Ψ绞剑喉樞蚪Y(jié)構(gòu)鏈表結(jié)構(gòu)記錄順序與地址順序結(jié)合的表示方法我們重點來討論在順序存儲結(jié)構(gòu)上各種排序方法的實現(xiàn)。排序的基本概念排序算法的好壞如何衡量？

空間效率占內(nèi)存輔助空間的大小穩(wěn)定性A和B的關(guān)鍵字相等，排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。時間效率排序速度（比較次數(shù)與移動次數(shù)）排序的基本概念假設Ki是Ri的主關(guān)鍵字，Kj是Rj的主關(guān)鍵字穩(wěn)定排序：若Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，在排序前的序列中Ri領(lǐng)先于Rj(即i<j)，經(jīng)過排序后得到的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；不穩(wěn)定排序：反之，當相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中發(fā)生變化者，則稱所用的排序方法是不穩(wěn)定的?！璦i…aj…排序后…ai…aj…穩(wěn)定排序…aj…ai…排序后…ai…aj…不穩(wěn)定排序插入排序插入排序（insertionsort）可以視為兩步操作，一步是插入，一步是排序。插入排序的基本思想就是將一條記錄插入到一組已經(jīng)有序的序列中，繼而得到一個有序的、數(shù)據(jù)個數(shù)加一的新的序列。插入排序不同的具體實現(xiàn)方法導致不同的算法描述：直接插入排序（基于順序查找）折半插入排序（基于折半查找）希爾排序（基于逐趟縮小增量）插入排序——直接插入排序有序序列R[1..i-1]R[i]

無序序列R[i..n]有序序列R[1..i]無序序列R[i+1..n]插入排序——直接插入排序21254925*16080123456012345

6214925*1608i=20123456212525*1608i=3無序數(shù)組＞49＞監(jiān)視哨25插入排序——直接插入排序25*2125491608012345

6012345621254925*08i=5012345621254925*16i=6i=4<=<<1608插入排序——直接插入排序直接插入排序算法{48}62357755143598{4862}357755143598{354862}7755143598{35486277}55143598{3548556277}143598{143548556277}3598{14353548556277}98{1435354855627798}

穩(wěn)定的排序方法插入排序——直接插入排序算法描述：步驟1：在R[1..i-1]中查找R[i]的插入位置，

R[1..j].keyR[i].key<R[j+1..i-1].key步驟2：將R[j+1..i-1]中的所有記錄均后移一個位置

步驟3：將R[i]插入到R[j+1]的位置上插入排序——直接插入排序直接插入排序算法的要點是：使用監(jiān)視哨r[0]臨時保存待插入的記錄。從后往前查找應插入的位置。查找與移動用同一循環(huán)完成。直接插入排序算法分析：從空間角度來看，它只需要一個輔助空間r[0]。從時間角度來看，主要時間耗費在關(guān)鍵字比較和移動元素上。比較次數(shù)和移動次數(shù)與初始排列有關(guān)

插入排序——直接插入排序最好的情況：總的比較次數(shù)：總的移動次數(shù)：最壞的情況：總的比較次數(shù)：總的移動次數(shù)：順序排列逆序排列n-1次2(n-1)次

插入排序——直接插入排序直接插入排序算法分析：若出現(xiàn)各種可能排列的概率相同，則可取最好情況和最壞情況的平均情況，則平均情況比較次數(shù)和移動次數(shù)為n2/4時間復雜度為O(n2)空間復雜度為O(1)是一種穩(wěn)定的排序方法插入排序——直接插入排序折半插入排序直接插入排序減少關(guān)鍵字間的比較次數(shù)在插入r[i]時，利用折半查找法尋找r[i]的插入位置插入排序——折半插入排序折半插入排序（binaryinsertionsort）是對直接插入排序的改進。在直接插入排序中，主要的時間消耗在數(shù)據(jù)的比較和移動上，那么可以在前半部分有序序列中采用折半查找的方法來提高查找速度。插入排序——折半插入排序i=2插入排序——折半插入排序i=3插入排序——折半插入排序i=4插入排序——折半插入排序i=5插入排序——折半插入排序i=6插入排序——折半插入排序算法分析：折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。

它所需要的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān)，僅依賴于對象個數(shù)。在插入第i個對象時，需要經(jīng)過

log2i

+1次關(guān)鍵碼比較，才能確定它應插入的位置。當n較大時，總關(guān)鍵碼比較次數(shù)比直接插入排序的最壞情況要好得多，但比其最好情況要差在對象的初始排列已經(jīng)按關(guān)鍵碼排好序或接近有序時，直接插入排序比折半插入排序執(zhí)行的關(guān)鍵碼比較次數(shù)要少折半插入排序的對象移動次數(shù)與直接插入排序相同，依賴于對象的初始排列插入排序——折半插入排序算法分析：減少了比較次數(shù)，但沒有減少移動次數(shù)平均性能優(yōu)于直接插入排序空間復雜度為O(1)是一種穩(wěn)定的排序方法時間復雜度為O(n2)插入排序——希爾排序

又稱縮小增量排序法利用直接插入排序的最佳性質(zhì)：在基本有序時，效率較高在待排序的記錄個數(shù)較少時，效率較高希爾排序的基本思想是：先將整個待排記錄序列分割成若干子序列，分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。插入排序——希爾排序例：關(guān)鍵字序列T=(49，38，65，97,76,13,27,49*，55,04）：380123456789104938659776132749*5504初態(tài)：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*9755760427386549*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697r[i]dk

值較大，子序列中對象較少，速度較快；dk

值逐漸變小，子序列中對象變多，但大多數(shù)對象已基本有序，所以排序速度仍然很快。插入排序——希爾排序算法分析：技巧：子序列的構(gòu)成不是簡單地“逐段分割”將相隔某個增量dk的記錄組成一個子序列讓增量dk逐趟縮短（例如依次取5,3,1）直到dk＝1為止。優(yōu)點：小元素跳躍式前移最后一趟增量為1時，序列已基本有序平均性能優(yōu)于直接插入排序時間復雜度是n和d的函數(shù)：O(n1.25）～O（1.6n1.25）—經(jīng)驗公式空間復雜度為O(1)是一種不穩(wěn)定的排序方法遺留問題：如何選擇最佳序列，目前尚未解決最后一個增量值必須為1，無除1以外的公因子不宜在鏈式存儲結(jié)構(gòu)上實現(xiàn)交換排序交換排序（swapsorting）的核心思想：是根據(jù)序列中兩條記錄鍵值的比較結(jié)果，判斷是否需要交換記錄在序列中的位置。其特點是將鍵值較大（或較小）的記錄向序列的前端移動，將鍵值較?。ɑ蜉^大）的記錄向序列的后端移動。交換排序基本思想：通過交換逆序無素進行排序的方法。冒泡排序快速排序交換排序——冒泡排序（相鄰比序法）基本思想：反復掃描待排序記錄序列，在掃描的過程中順次比較相鄰的兩個元素的大小，若逆序則交換位置。將待排序的記錄看成堅著排列的“氣泡”，鍵值較重的記錄比較重,從而往下沉。交換排序——冒泡排序（相鄰比序法）以升序為例第一趟i=121254925*1608012345

6j=5j=4j=3j=2j=121<2525<4949>25*49<1649<08第一趟掃描結(jié)束：關(guān)鍵字最大的記錄沉到最底下?。╪的位置）交換排序——冒泡排序（相鄰比序法）第二趟i=221<2525=25*25*<1625*<08212525*1608012345

6j=4j=3j=2j=149第二趟掃描結(jié)束：關(guān)鍵字次大的記錄沉到n-1位置！交換排序——冒泡排序（相鄰比序法）第三趟i=321<2525>1625>08第三趟掃描結(jié)束：記錄沉到n-2位置！j=3j=2j=121251608012345

64925*交換排序——冒泡排序（相鄰比序法）第四趟i=421>16第四趟掃描結(jié)束：記錄沉到n-3位置！21>08j=2j=1211608012345

64925*25交換排序——冒泡排序（相鄰比序法）第五趟i=516>08第五趟掃描結(jié)束：記錄沉到n-4位置！j=11608012345

64925*2521最后一個元素一定是關(guān)鍵字最小的元素：交換排序——冒泡排序（相鄰比序法）254925*160801234521所以，n個記錄，需掃描n-1趟，即可完成排序最好的情況：總的比較次數(shù)：總的移動次數(shù)：最壞的情況：總的比較次數(shù)：總的移動次數(shù)：順序排列逆序排列n-1次O(n)交換排序——冒泡排序（相鄰比序法）

交換排序——冒泡排序（相鄰比序法）算法分析：時間復雜度為O(n2)空間復雜度為O(1)是一種穩(wěn)定的排序方法算法思想：任取一個元素(如第一個)為中心所有比它小的元素一律前放，比它大的元素一律后放，形成左右兩個子表；對各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個子表的元素只剩一個交換排序——快速排序21254925*16080123452125*1625160849pivotkey0821pivotkeypivotkey25*2549交換排序——快速排序49081625*2521081625*212549pivotkey交換排序——快速排序012345678493838656597977676131327274949highlow49界點交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序38659776132749highlow49界點0123456784938659776132749交換排序——快速排序交換排序——快速排序?qū)σ韵聦嵗M行快速排序（以第一個元素作基準）：

4862357755143598第一次劃分：{35

1435}48{5577

62

98}第二次劃分：{14}35{35}4855{77

62

98}第三次劃分：1435354855{62}77{98}交換排序——快速排序快速排序也可以以最后一個元素作為基準，對以下實例進行快速排序（以最后一個元素作基準）：

4862357755143598第一次劃分：{14}35{3577556248}

98第二次劃分：1435{35}48{5562

77}98第三次劃分：14353548{5562}7798第四次劃分：14353548{55}627798算法分析：每一趟的子表的形成是采用從兩頭向中間交替式逼近法由于每趟中對各子表的操作都相似，可采用遞歸算法可以證明，平均計算時間是O(nlog2n)實驗結(jié)果表明：就平均計算時間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個快速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時參數(shù)（新的low和hi