T19-基于樹的排序算法

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

8462357755143598第一次：{14}62357755843598

第二次：{1435}627755843598

第三次：{143535}7755846298

第四次：

{143535

55}77846298

第五次：{143535

5562}847798

第六次：{143535

556277}8498第七次：{143535

55627784}98第八次：{143535

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

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

log2n

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

log2n

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

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

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

一個(gè)任意序列看成是對(duì)應(yīng)的完全二叉樹由于葉結(jié)點(diǎn)可以視為單元素的堆，因而可以反復(fù)利用“篩選”法，自底向上逐層把所有子樹調(diào)整為堆，直到將整個(gè)完全二叉樹調(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｝，要求將其篩選為一個(gè)大根堆。選擇排序——堆排序問(wèn)題4：如何利用堆進(jìn)行排序？①將待排序記錄按照堆的定義建初堆，并輸出堆頂元素；②調(diào)整剩余的記錄序列，利用篩選法將前n-i個(gè)元素重新篩選建成為一個(gè)新堆，再輸出堆頂元素；③重復(fù)執(zhí)行步驟②n-1次進(jìn)行篩選,新篩選成的堆會(huì)越來(lái)越小，而新堆后面的有序關(guān)鍵字會(huì)越來(lái)越多，最后使待排序記錄序列成為一個(gè)有序的序列，這個(gè)過(guò)程稱之為堆排序。選擇排序——堆排序比較小根堆排序與大根堆排序的區(qū)別利用小根堆進(jìn)行排序：已知關(guān)鍵字序列(40，55，73，12，98，27)選擇排序——堆排序第一步：先調(diào)整成為堆（若調(diào)整成為小根堆）401298275573401298735527405598731227125598734027完成選擇排序——堆排序第二步：輸出堆頂元素，并將剩余元素重新篩選成為堆，重復(fù)此步驟，直至完成排序。407312559827735598124027篩選985527124073篩選275598124073409827125573輸出堆頂元素輸出堆頂元素選擇排序——堆排序篩選409827125573984027125573554027129873734027129855734027129855篩選輸出堆頂元素輸出堆頂元素選擇排序——堆排序987355402712984027127355輸出堆頂元素734027129855完成選擇排序——堆排序比較小根堆排序與大根堆排序的區(qū)別利用大根堆進(jìn)行排序已知關(guān)鍵字序列(40，55，73，12，98，27)選擇排序——堆排序第一步：先調(diào)整成為堆（若調(diào)整成為大根堆）完成401298275573401298275573401255279873981240275573選擇排序——堆排序第二步：輸出堆頂元素，并將剩余元素重新篩選成為堆，重復(fù)此步驟，直至完成排序。552798124073271240985573篩選401273985527篩選731240985527551273984027輸出堆頂元素輸出堆頂元素選擇排序——堆排序篩選551273984027125573984027405573981227275573981240275573981240篩選輸出堆頂元素輸出堆頂元素選擇排序——堆排序122740557398125573982740275573981240輸出堆頂元素完成選擇排序——堆排序堆排序的算法分析：堆排序是一種不穩(wěn)定的排序方法它不適用于待排序記錄個(gè)數(shù)n較少的情況，但對(duì)于n較大的文件還是很有效的。在最壞情況下，其時(shí)間復(fù)雜度也為O(nlog2n)，這是堆排序的最大優(yōu)點(diǎn)。各種排序方法的綜合比較首先從算法的平均時(shí)間復(fù)雜度、最壞時(shí)間復(fù)雜度、以及算法所需的輔助存儲(chǔ)空間三方面，對(duì)各種排序方法加以比較分類方法時(shí)間復(fù)雜度空間復(fù)雜度穩(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)定選擇排序簡(jiǎ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)定各種排序方法的綜合比較通過(guò)分析和比較，可以得出以下結(jié)論：從排序的穩(wěn)定性來(lái)看，簡(jiǎn)單排序是穩(wěn)定的，除了簡(jiǎn)單選擇排序，其它各種簡(jiǎn)單排序法也是穩(wěn)定的。多數(shù)情況下，排序是按記錄的主關(guān)鍵字進(jìn)行的，此時(shí)不用考慮排序方法的穩(wěn)定性。如果排序是按記錄的次關(guān)鍵字進(jìn)行的，則應(yīng)充分考慮排序方法的穩(wěn)定性。為避免順序存儲(chǔ)時(shí)大量移動(dòng)記錄的時(shí)間開(kāi)銷，可考慮用鏈表作為存儲(chǔ)結(jié)構(gòu)：直接插入排序、歸并排序、基數(shù)排序，不宜采用鏈表作為存儲(chǔ)結(jié)構(gòu)的折半插入排序、希爾排序、快速排序、堆排序各種排序方法的綜合比較通過(guò)分析和比較，可以得出以下結(jié)論：n較大時(shí)分布隨機(jī)，穩(wěn)定性不做要求，則采用快速排序內(nèi)存允許，要求排序穩(wěn)定時(shí)，則采用歸并排序可能會(huì)出現(xiàn)正序或逆序，穩(wěn)定性不做要求，則采用堆排序或歸并排序n較小時(shí)基本有序，則采用直接插入排序分布隨機(jī)，則采用簡(jiǎn)單選擇排序，若排序碼不接近逆序，也可以采用直接插入排序提高排序方法選擇：①設(shè)有10000個(gè)無(wú)序元素，僅要求找出前10個(gè)最小元素，在下列排序方法中（歸并排序、簡(jiǎn)單排序、快速排序、堆排序、插入排序）哪一種方法最好，為什么？待排序元素1萬(wàn)，僅需找出前10個(gè)最小元素，因此并不需要整個(gè)排序；在所給