T19-基于樹的排序算法

基于樹的排序算法第十章主講：周翔選擇排序選擇排序（selectionsort）的基本思想是：從待排序的序列中選出最大值（或最小值），交換該元素與待排序序列頭部元素，直到所有待排序的數(shù)據(jù)元素排序完畢為止。選擇排序基本思想：每一趟在n-i+1（i=1，2，…n-1）個記錄中選取關(guān)鍵字最小的記錄作為有序序列中第i個記錄。簡單選擇排序樹型選擇排序堆排序選擇排序——簡單選擇排序算法思想：第i趟簡單選擇排序是指通過n-i次關(guān)鍵字的比較，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i個記錄進行交換。共需進行i-1趟比較，直到所有記錄排序完成為止。2125*i=125164908最小者08交換21,0825160825*4921i=2最小者16交換25,1649i=3081625*2521最小者21交換49,21選擇排序——簡單選擇排序4925*012345i=408162521最小者25*無交換25*i=549最小者25無交換2521160825160825*4921結(jié)果各趟排序后的結(jié)果選擇排序——簡單選擇排序選擇排序——簡單選擇排序?qū)σ韵聦嵗M行簡單選擇排序：

8462357755143598第一次：{14}62357755843598

第二次：{1435}627755843598

第三次：{143535}7755846298

第四次：

{143535

55}77846298

第五次：{143535

5562}847798

第六次：{143535

556277}8498第七次：{143535

55627784}98第八次：{143535

5562778498｝選擇排序——簡單選擇排序算法分析：在簡單選擇排序過程中，所需移動記錄的次數(shù)比較少。最好情況下，即待排序記錄初始狀態(tài)就已經(jīng)是正序排列了，則不需要移動記錄。最壞情況下，即待排序記錄初始狀態(tài)是按逆序排列的，則需要移動記錄的次數(shù)最多為3(n-1)。進行比較操作的時間復雜度為O(n2)。選擇排序——簡單選擇排序算法分析：時間復雜度：O(n2)空間復雜度：O(1)穩(wěn)定

選擇排序——樹形選擇排序算法思想：樹型選擇排序也稱作錦標賽排序。錦標賽的比賽過程很簡單：首先所有參加比賽的選手兩兩分組，每組產(chǎn)生一個勝利者；其次這些勝利者再兩兩分組進行比賽，每組產(chǎn)生一個勝利者；之后重復執(zhí)行上一步驟，直到最后只有一個勝者產(chǎn)生為止。選擇排序——樹形選擇排序改進：簡單選擇排序沒有利用上次選擇的結(jié)果，是造成速度慢的重要原因。如果，能夠加以改進，將會提高排序的速度381376276549974938651327133813選出最小者13選擇排序——樹形選擇排序選出次最小者，應(yīng)利用上次比較的結(jié)果。從被13打敗的結(jié)點27、76、38中加以確定。381376276549974938651327273827選出次最小者27選擇排序——樹形選擇排序算法分析：在樹型選擇排序中，被選中的關(guān)鍵字都是走了一條由葉子結(jié)點到根結(jié)點的比較的過程由于含有n個葉子節(jié)點的完全二叉數(shù)的深度為

log2n

+1，則在樹型選擇排序中，每選擇一個小關(guān)鍵字需要進行

log2n

次比較，因此其時間復雜度為O(nlog2n)。移動記錄次數(shù)不超過比較次數(shù)，故總的算法時間復雜度為O(nlog2n)。選擇排序——堆排序算法思想：堆排序是對樹型選擇排序的進一步改進。采用堆排序時，只需要一個記錄大小的輔助空間。堆排序是在排序過程中，將向量中存儲的數(shù)據(jù)看成一棵完全二叉樹，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇關(guān)鍵字最小的記錄利用樹的結(jié)構(gòu)特征來描述堆，所以樹只是作為堆的描述工具，堆實際是存放在線形空間中的選擇排序——堆排序完全二叉樹的組織存儲形式：12348567910AHIJDEFGBCKL1211ABCDEFGHIJKL123456789101112選擇排序——堆排序如果完全二叉樹各層次結(jié)點從1開始編號：1,2,3,…,n，則有以下關(guān)系：①僅當i=1時，結(jié)點i為根結(jié)點②當i>1時，結(jié)點i的父結(jié)點為i/2③結(jié)點i的左兒子結(jié)點為2i④結(jié)點i的右兒子結(jié)點為2i+112348567910AHIJDEFGBCKL1211選擇排序——堆排序問題1：什么是堆？問題2：當堆頂元素改變時，如何重建堆?問題3：如何由一個任意序列建初堆？問題4：如何利用堆進行排序？選擇排序——堆排序問題1：什么是堆？大根堆：滿足以下兩個條件是完全二叉樹任意結(jié)點的關(guān)鍵字大于或者等于其左孩子和右孩子的關(guān)鍵字1006688455048553028選擇排序——堆排序問題1：什么是堆？小根堆：滿足以下兩個條件是完全二叉樹任意結(jié)點的關(guān)鍵字小于或者等于其左孩子和右孩子的關(guān)鍵字101535455020253028選擇排序——堆排序關(guān)鍵字序列(10，15，56，25，30，70)101556253070101556253070123456小根堆邏輯結(jié)構(gòu)存儲結(jié)構(gòu)選擇排序——堆排序關(guān)鍵字序列

(70，56，30，25，15，10)大根堆邏輯結(jié)構(gòu)存儲結(jié)構(gòu)705630251510705630251510123456選擇排序——堆排序問題2：當堆頂元素改變時，如何重建堆?

以小根堆為例：首先將完全二叉樹根結(jié)點中的記錄移出，此時根結(jié)點相當于空結(jié)點。從空結(jié)點的左、右子中選出一個關(guān)鍵字較小的記錄，如果該記錄的關(guān)鍵字小于待調(diào)整記錄的關(guān)鍵字，則將該記錄上移至空結(jié)點中。此時，原來那個關(guān)鍵字較小的子結(jié)點相當于空結(jié)點。重復上述移動過程，直到空結(jié)點左、右子的關(guān)鍵字均不小于待調(diào)整記錄的關(guān)鍵字。上述調(diào)整方法相當于把待調(diào)整記錄逐步向下“篩”的過程，所以一般稱為“篩選”法。選擇排序——堆排序刪除一下樹中的10：102515302025405055選擇排序——堆排序102515302025405055551525153020254050刪除10選擇排序——堆排序刪除15551525153020254050152520302025405055選擇排序——堆排序刪除205515252030202540505515252030254050選擇排序——堆排序問題3：如何由一個任意序列建初堆？

一個任意序列看成是對應(yīng)的完全二叉樹由于葉結(jié)點可以視為單元素的堆，因而可以反復利用“篩選”法，自底向上逐層把所有子樹調(diào)整為堆，直到將整個完全二叉樹調(diào)整為堆。選擇排序——堆排序5353171778780923456587i0923456587i=4i=3i自下向上逐步調(diào)整為小根堆選擇排序——堆排序5353171778780923456587i0923456587i=2i選擇排序——堆排序53171778780923456587i0923456587i=1i53選擇排序——堆排序53171778780923456587i0923456587i53選擇排序——堆排序?qū)⒁韵峦耆鏄浜Y選成為大根堆102515302025405055401025153020255550選擇排序——堆排序102515302025555040401025301520255550選擇排序——堆排序102530152025555040401055301520252550401055301520255025選擇排序——堆排序105530152025502540405510301520255025選擇排序——堆排序405550301520251025105550301520254025選擇排序——堆排序已知關(guān)鍵字序列：｛48，62，35，77，55，14，35，98，10｝，要求將其篩選為一個大根堆。選擇排序——堆排序問題4：如何利用堆進行排序？①將待排序記錄按照堆的定義建初堆，并輸出堆頂元素；②調(diào)整剩余的記錄序列，利用篩選法將前n-i個元素重新篩選建成為一個新堆，再輸出堆頂元素；③重復執(zhí)行步驟②n-1次進行篩選,新篩選成的堆會越來越小，而新堆后面的有序關(guān)鍵字會越來越多，最后使待排序記錄序列成為一個有序的序列，這個過程稱之為堆排序。選擇排序——堆排序比較小根堆排序與大根堆排序的區(qū)別利用小根堆進行排序：已知關(guān)鍵字序列(40，55，73，12，98，27)選擇排序——堆排序第一步：先調(diào)整成為堆（若調(diào)整成為小根堆）401298275573401298735527405598731227125598734027完成選擇排序——堆排序第二步：輸出堆頂元素，并將剩余元素重新篩選成為堆，重復此步驟，直至完成排序。407312559827735598124027篩選985527124073篩選275598124073409827125573輸出堆頂元素輸出堆頂元素選擇排序——堆排序篩選409827125573984027125573554027129873734027129855734027129855篩選輸出堆頂元素輸出堆頂元素選擇排序——堆排序987355402712984027127355輸出堆頂元素734027129855完成選擇排序——堆排序比較小根堆排序與大根堆排序的區(qū)別利用大根堆進行排序已知關(guān)鍵字序列(40，55，73，12，98，27)選擇排序——堆排序第一步：先調(diào)整成為堆（若調(diào)整成為大根堆）完成401298275573401298275573401255279873981240275573選擇排序——堆排序第二步：輸出堆頂元素，并將剩余元素重新篩選成為堆，重復此步驟，直至完成排序。552798124073271240985573篩選401273985527篩選731240985527551273984027輸出堆頂元素輸出堆頂元素選擇排序——堆排序篩選551273984027125573984027405573981227275573981240275573981240篩選輸出堆頂元素輸出堆頂元素選擇排序——堆排序122740557398125573982740275573981240輸出堆頂元素完成選擇排序——堆排序堆排序的算法分析：堆排序是一種不穩(wěn)定的排序方法它不適用于待排序記錄個數(shù)n較少的情況，但對于n較大的文件還是很有效的。在最壞情況下，其時間復雜度也為O(nlog2n)，這是堆排序的最大優(yōu)點。各種排序方法的綜合比較首先從算法的平均時間復雜度、最壞時間復雜度、以及算法所需的輔助存儲空間三方面，對各種排序方法加以比較分類方法時間復雜度空間復雜度穩(wěn)定性最好最壞平均交換排序冒泡排序O(n)O(n2)O(n2)O(1)穩(wěn)定快速排序O(nlog2n)O(n2)O(nlog2n)O(nlog2n)不穩(wěn)定插入排序直接插入排序O(n)O(n2)O(n2)O(1)穩(wěn)定希爾排序

O(n1.3)O(1)不穩(wěn)定選擇排序簡單選擇排序O(n2)O(n2)O(n2)O(1)不穩(wěn)定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不穩(wěn)定其它歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)穩(wěn)定基數(shù)排序O(d(r+n))O(d(r+n))O(d(r+n))O(r)穩(wěn)定各種排序方法的綜合比較通過分析和比較，可以得出以下結(jié)論：從排序的穩(wěn)定性來看，簡單排序是穩(wěn)定的，除了簡單選擇排序，其它各種簡單排序法也是穩(wěn)定的。多數(shù)情況下，排序是按記錄的主關(guān)鍵字進行的，此時不用考慮排序方法的穩(wěn)定性。如果排序是按記錄的次關(guān)鍵字進行的，則應(yīng)充分考慮排序方法的穩(wěn)定性。為避免順序存儲時大量移動記錄的時間開銷，可考慮用鏈表作為存儲結(jié)構(gòu)：直接插入排序、歸并排序、基數(shù)排序，不宜采用鏈表作為存儲結(jié)構(gòu)的折半插入排序、希爾排序、快速排序、堆排序各種排序方法的綜合比較通過分析和比較，可以得出以下結(jié)論：n較大時分布隨機，穩(wěn)定性不做要求，則采用快速排序內(nèi)存允許，要求排序穩(wěn)定時，則采用歸并排序可能會出現(xiàn)正序或逆序，穩(wěn)定性不做要求，則采用堆排序或歸并排序n較小時基本有序，則采用直接插入排序分布隨機，則采用簡單選擇排序，若排序碼不接近逆序，也可以采用直接插入排序提高排序方法選擇：①設(shè)有10000個無序元素，僅要求找出前10個最小元素，在下列排序方法中（歸并排序、簡單排序、快速排序、堆排序、插入排序）哪一種方法最好，為什么？待排序元素1萬，僅需找出前10個最小元素，因此并不需要整個排序；在所給