數(shù)據(jù)結(jié)構(gòu)第十章

數(shù)據(jù)結(jié)構(gòu)第十章數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)第十章排序：將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新

排列成一個(gè)按關(guān)鍵字有序的序列內(nèi)部排序：將待排記錄存放在計(jì)算機(jī)隨機(jī)存儲器重進(jìn)

行的排序過程。外部排序：由于待排記錄的數(shù)量很大，以至內(nèi)存一次

不能容納全部記錄，在排序過程中尚需要

對外存進(jìn)行訪問的排序過程。2第十章內(nèi)部排序數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第2頁。數(shù)據(jù)結(jié)構(gòu)第十章第10章內(nèi)部排序310.1概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)第十章410.1概述1、排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“按關(guān)鍵字有序”的記錄序列。52，49，80，36，14，58，61，23，97，7514，23，36，49，52，58，61，75，80，97一般情況下，假設(shè)含n個(gè)記錄的序列為{R1，R2，……，Rn}其相應(yīng)的關(guān)鍵字序列為{K1，K2，……，Kn}這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在這樣一個(gè)關(guān)系：Kp1<=Kp2<=…<=Kpn按此固有關(guān)系將上式記錄序列重新排列為{Rp1,Rp2,…,Rpn}的操作稱作排序數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第4頁。數(shù)據(jù)結(jié)構(gòu)第十章52、關(guān)鍵字?jǐn)?shù)據(jù)對象有多個(gè)屬性域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可以用來區(qū)分對象，作為排序依據(jù)，稱為關(guān)鍵字。關(guān)鍵字與記錄之間是一對一的關(guān)系稱主關(guān)鍵字關(guān)鍵字與記錄之間是一對多的關(guān)系稱次關(guān)鍵字?jǐn)?shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第5頁。數(shù)據(jù)結(jié)構(gòu)第十章63、排序的目的是什么？——便于查找4、排序算法的好壞如何衡量？

時(shí)間效率——排序速度（即排序所花費(fèi)的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性——若兩個(gè)記錄A和B的關(guān)鍵字相等，但排序后A，

B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)第十章75、什么叫內(nèi)部排序？什么叫外部排序——

若待排序記錄都在內(nèi)存中，稱內(nèi)部排序——

若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。注：外部排序時(shí)，要將數(shù)據(jù)分批掉入內(nèi)存來排序，中間結(jié)果還要及時(shí)放入內(nèi)存，顯然外部排序要復(fù)雜得的多。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第7頁。數(shù)據(jù)結(jié)構(gòu)第十章86、待排序記錄在內(nèi)存中怎樣存儲和處理（1）順序排序——

排序時(shí)直接移動(dòng)記錄；（2）鏈表排序——

排序時(shí)只移動(dòng)指針；（3）地址排序——

排序時(shí)先移動(dòng)地址，最后再移動(dòng)記錄。注：地址排序中可以增設(shè)一維數(shù)組來專門存放記錄的地址。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第8頁。數(shù)據(jù)結(jié)構(gòu)第十章96.順序存儲（順序表）的抽象數(shù)據(jù)類型如何表示？注：大多數(shù)排序算法都是針對順序表結(jié)構(gòu)的(便于直接移動(dòng)元素)Typedefstruct{//定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu)

KeyTypekey;//關(guān)鍵字

InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RecordType;Typedefstruct{//定義順序表的結(jié)構(gòu)

RecordTyper[MAXSIZE+1];//存儲順序表的向量

//r[0]一般作哨兵或緩沖區(qū)

intlength;//順序表的長度}SqList;#defineMAXSIZE20//設(shè)記錄不超過20個(gè)typedefintKeyType;//設(shè)關(guān)鍵字為整型量（int型）數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第9頁。數(shù)據(jù)結(jié)構(gòu)第十章7.內(nèi)部排序的算法有哪些？10——按排序的規(guī)則不同，可分為5類：插入排序交換排序（重點(diǎn)是快速排序）選擇排序歸并排序基數(shù)排序d＝關(guān)鍵字的位數(shù)(長度)——按排序算法的時(shí)間復(fù)雜度不同，可分為3類：簡單的排序算法：時(shí)間效率低，O(n2)先進(jìn)的排序算法:時(shí)間效率高，O(nlog2n)基數(shù)排序算算法：時(shí)間效率高，O(d×n)數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第10頁。數(shù)據(jù)結(jié)構(gòu)第十章1110.2插入排序插入排序的基本思想是：插入排序有多種具體實(shí)現(xiàn)算法：

1)直接插入排序

2)折半插入排序

3)表插入排序

4)希爾排序

每步將一個(gè)待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第11頁。數(shù)據(jù)結(jié)構(gòu)第十章12（1）直接插入排序基本思想：假定前面m個(gè)元素已經(jīng)排序；取第(m+1)個(gè)元素，插入到前面的適當(dāng)位置；一直重復(fù)，到m=n為止。（初始情況下，m=1）數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第12頁。數(shù)據(jù)結(jié)構(gòu)第十章13例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請寫出直接插入排序的中間過程序列?！?3】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,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】數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第13頁。數(shù)據(jù)結(jié)構(gòu)第十章14voidInsertSort(SqList&L){

//對順序表L作直接插入排序。

inti,j;

for(i=2;i<=L.length;++i)

if(LT(L.r[i].key,L.r[i-1].key)){

//"<"時(shí)，需將L.r[i]插入有序子表

L.r[0]=L.r[i];//復(fù)制為哨兵

for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)

L.r[j+1]=L.r[j];//記錄后移

L.r[j+1]=L.r[0];//插入到正確位置

}}//InsertSort數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第14頁。數(shù)據(jù)結(jié)構(gòu)第十章15例2：關(guān)鍵字序列T=（21，25，49，25*，16，08），

請寫出直接插入排序的具體實(shí)現(xiàn)過程。*表示后一個(gè)25i=121254925*16080123456暫存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假設(shè)該序列已存入一維數(shù)組V[7]中，將V[0]作為緩沖或暫存單元（Temp）。則程序執(zhí)行過程為：21254925*21初態(tài)：164925*25211608完成!時(shí)間效率：O(n2)——因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（0＋2＋…＋n)→O(n2)。其他情況下還要加上移動(dòng)元素的次數(shù)?？臻g效率：O（1）——因?yàn)閮H占用1個(gè)緩沖單元算法的穩(wěn)定性：穩(wěn)定——因?yàn)?5*排序后仍然在25的后面。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第15頁。數(shù)據(jù)結(jié)構(gòu)第十章特點(diǎn)：因?yàn)镽[1…i-1]是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)在R[1…i-1]中查找R[i]的插入位置，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判?。限制：必須采用順序存儲方式?62）折半插入排序數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第16頁。數(shù)據(jù)結(jié)構(gòu)第十章17例：有6個(gè)記錄，前5個(gè)已排序的基礎(chǔ)上，對第6個(gè)記錄排序。[1527365369]42

lowmidhigh

[1527365369]42

lowhigh

mid

[1527365369]42

highlow[152736425369](high<low，查找結(jié)束，插入位置為low或high+1)(42>36)(42<53)數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第17頁。數(shù)據(jù)結(jié)構(gòu)第十章182）折半插入排序優(yōu)點(diǎn)：比較的次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。時(shí)間效率：雖然比較次數(shù)大大減少，可惜移動(dòng)次數(shù)并未減少，所以排序效率仍為O(n2)?？臻g效率：O（1）穩(wěn)定性：穩(wěn)定討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？答：直接插入不僅可行，而且還無需移動(dòng)元素，時(shí)間效率更高！但鏈表無法“折半”！數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第18頁。數(shù)據(jù)結(jié)構(gòu)第十章19

設(shè)待排序的關(guān)鍵碼分別為28，13，72，85，39，41，6，20。按二分法插入排序算法已使前七個(gè)記錄有序，中間結(jié)果如下:試在此基礎(chǔ)上，沿用上述表達(dá)方式，給出繼續(xù)采用二分法插入第八個(gè)記錄的比較過程。在一些特殊情況下，二分法插入排序比直接插入排序要執(zhí)行更多的比較。這句話對嗎？613283941728520r=7i=1m=4數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第19頁。數(shù)據(jù)結(jié)構(gòu)第十章3）希爾（shell）排序（又稱縮小增量排序）20基本思想：先將整個(gè)待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直接插入排序。技巧：子序列的構(gòu)成不是簡單地“逐段分割”，而是將相隔某個(gè)增量dk的記錄組成一個(gè)子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第20頁。數(shù)據(jù)結(jié)構(gòu)第十章例：關(guān)鍵字序列T=(49，38，65，97,76,13,27,49*，55,04），請寫出希爾排序的具體實(shí)現(xiàn)過程。21380123456789104938659776132749*5504初態(tài)：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*9755760427386549*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697算法分析：開始時(shí)dk

的值較大，子序列中的對象較少，排序速度較快；隨著排序進(jìn)展，dk

值逐漸變小，子序列中對象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。r[i]數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第21頁。數(shù)據(jù)結(jié)構(gòu)第十章時(shí)間效率：22空間效率：O（1）——因?yàn)閮H占用1個(gè)緩沖單元算法的穩(wěn)定性：不穩(wěn)定——因?yàn)?9*排序后卻到了49的前面O(n）～O（n）——經(jīng)驗(yàn)公式數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第22頁。數(shù)據(jù)結(jié)構(gòu)第十章23寫出采用SHELL排序算法排序的每一趟的結(jié)果，并標(biāo)出數(shù)據(jù)移動(dòng)情況。（125，11，22，34，15，44，76，100，8，14，20，2，5）數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第23頁。數(shù)據(jù)結(jié)構(gòu)第十章9.3交換排序24

兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序?yàn)橹?。交換排序的主要算法有：

1)冒泡排序

2)快速排序交換排序的基本思想是：數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第24頁。數(shù)據(jù)結(jié)構(gòu)第十章1)冒泡排序25基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。前提：順序存儲結(jié)構(gòu)例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出冒泡排序的具體實(shí)現(xiàn)過程。21，25，49，25*，16，0821，25，25*，16，08，4921，25，16，08，25*，4921，16，08，25，25*，4916，08，21，25，25*，4908，16，21，25，25*，49初態(tài)：第1趟第2趟第3趟第4趟第5趟數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第25頁。數(shù)據(jù)結(jié)構(gòu)第十章冒泡排序的算法分析26時(shí)間效率：O（n2)—因?yàn)橐紤]最壞情況空間效率：O（1）—只在交換時(shí)用到一個(gè)緩沖單元穩(wěn)定性：穩(wěn)定—25和25*在排序前后的次序未改變數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第26頁。數(shù)據(jù)結(jié)構(gòu)第十章2）快速排序27

從待排序列中任取一個(gè)元素(例如取第一個(gè))作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個(gè)子表；然后再對各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。此時(shí)便為有序序列了?；舅枷耄簝?yōu)點(diǎn)：因?yàn)槊刻丝梢源_定不止一個(gè)元素的位置，而且呈指數(shù)增加，所以特別快！前提：順序存儲結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第27頁。數(shù)據(jù)結(jié)構(gòu)第十章28

一趟快速排序采用從兩頭向中間掃描的辦法。假設(shè)原始數(shù)據(jù)已存于一個(gè)一維數(shù)組r中，具體的做法是：設(shè)兩個(gè)指示器i和j，初始時(shí)i指向數(shù)組中的第一個(gè)數(shù)據(jù)，j指向最末一個(gè)數(shù)據(jù)。i先不動(dòng)使j逐步前移，每次對二者所指的數(shù)據(jù)進(jìn)行比較，當(dāng)遇到r[i]大于r[j]的情況時(shí)，就將二者對調(diào)位置；然后令j固定使i逐步后移做數(shù)據(jù)比較，當(dāng)遇到r[i]大于r[j]時(shí)，又進(jìn)行位置對調(diào)；然后又是i不動(dòng)使j前移作數(shù)據(jù)比較；……；如此反復(fù)進(jìn)行，直至i與j兩者相遇為止。具體過程數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第28頁。數(shù)據(jù)結(jié)構(gòu)第十章2023/6/142925*跑到了前面，不穩(wěn)定！Low=high=3，本趟停止，將支點(diǎn)定位并返回位置信息10.3.2快速排序r[i]0123456初態(tài)21254925*1608第1趟highlow210825164925*321pivotkey=2108251649(08，16）21（25*，49，25）lowlowhighhighhigh例1：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出快速排序的算法步驟。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第29頁。數(shù)據(jù)結(jié)構(gòu)第十章例1：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出快速排序的算法步驟。30()，設(shè)以首元素為樞軸中心21，25，49，25*，16，08初態(tài)：第1趟：第2趟：第3趟：08，16，21，25，25*，(49)2116，08，()25，25*，49(08)，16，21，25，(25*，49)數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第30頁。數(shù)據(jù)結(jié)構(gòu)第十章例3：以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行快速算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。31原始序列：256，301，751，129，937，863，742，694，076，438快速排序第1趟第2趟第3趟第4趟256，301，751，129，937，863，742，694，076，438076，129，256，751，937，863，742，694，301，438要求模擬算法實(shí)現(xiàn)步驟256076301129751256076，129，256，438，301，694，742，694，863，937751076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742，751，863，937438076，129，256，301，438，694，742，751，863，937數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第31頁。數(shù)據(jù)結(jié)構(gòu)第十章9.4選擇排序32選擇排序有多種具體實(shí)現(xiàn)算法：

1)簡單選擇排序

2)堆排序選擇排序的基本思想是：每一趟在后面n-i

個(gè)待排記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個(gè)記錄。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第32頁。數(shù)據(jù)結(jié)構(gòu)第十章1）簡單選擇排序33思路簡單：每經(jīng)過一趟比較就找出一個(gè)最小值，與待排序列最前面的位置互換即可?！紫龋趎個(gè)記錄中選擇最小者放到r[1]位置；然后，從剩余的n-1個(gè)記錄中選擇最小者放到r[2]位置；…如此進(jìn)行下去，直到全部有序?yàn)橹埂?yōu)點(diǎn)：實(shí)現(xiàn)簡單缺點(diǎn)：每趟只能確定一個(gè)元素，表長為n時(shí)需要n-1趟前提：順序存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第33頁。數(shù)據(jù)結(jié)構(gòu)第十章例：關(guān)鍵字序列T=（21，25，49，25*，16，08），請給出簡單選擇排序的具體實(shí)現(xiàn)過程。34原始序列：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時(shí)間效率：O(n2)——雖移動(dòng)次數(shù)較少，但比較次數(shù)仍多?？臻g效率：O（1）——無需任何附加單元！算法的穩(wěn)定性：不穩(wěn)定——因?yàn)榕判驎r(shí)，25*到了25的前面。最小值08與r[1]交換位置數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第34頁。數(shù)據(jù)結(jié)構(gòu)第十章2）錦標(biāo)賽排序(又稱樹形選擇排序)35基本思想：與體育比賽時(shí)的淘汰賽類似。

首先對n

個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，得到n/2

個(gè)優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來。然后在這n/2

個(gè)較小者之間再進(jìn)行兩兩比較，…，如此重復(fù)，直到選出最小關(guān)鍵字的記錄為止。優(yōu)點(diǎn)：減少比較次數(shù)，加快排序速度缺點(diǎn)：空間效率低例：關(guān)鍵字序列T=（21，25，49，25*，16，08，63），請給出錦標(biāo)賽排序的具體實(shí)現(xiàn)過程。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第35頁。數(shù)據(jù)結(jié)構(gòu)第十章3636Winner(勝者)r[1]注：為便于自動(dòng)處理，建議每個(gè)記錄多開兩個(gè)特殊分量：keyotherinfoIndex(結(jié)點(diǎn)位置編號）Tag（是否參加比較）初態(tài)：補(bǔ)足2k(k=log2n)個(gè)葉子結(jié)點(diǎn)勝者樹第一趟：數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第36頁。數(shù)據(jù)結(jié)構(gòu)第十章3737第二趟：161616r[2]Winner(勝者)求次小值16時(shí),只需比較2次，即只比較log2n-1次。令其Tag＝0,不參與比較數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第37頁。數(shù)據(jù)結(jié)構(gòu)第十章38令其Tag＝0,不參與比較第三趟：162116166325*2121254925*160863r[3]Winner(勝者)6321數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第38頁。數(shù)據(jù)結(jié)構(gòu)第十章082108086325*2121254925*1608636321第四趟：r[4]Winner(勝者)252525數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第39頁。數(shù)據(jù)結(jié)構(gòu)第十章40082108086325*2121254925*1608631616166321252525第五趟：r[5]Winner(勝者)25*25*數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第40頁。數(shù)據(jù)結(jié)構(gòu)第十章41082108086325*2121254925*160863161616632125252525*25*第六趟：r[6]Winner(勝者)494949數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第41頁。數(shù)據(jù)結(jié)構(gòu)第十章42082108086325*2121254925*160863161616632125252525*25*494949第七趟：r[7]Winner(勝者)63數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第42頁。數(shù)據(jù)結(jié)構(gòu)第十章2）堆排序431.什么是堆？堆的定義：設(shè)有n個(gè)元素的序列k1，k2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆。ki≤

k2iki≤

k2i+1ki≥

k2iki≥

k2i+1或者i=1,2,…n/22.怎樣建堆？3.怎樣堆排序？解釋：如果讓滿足以上條件的元素序列（k1，k2，…，kn）順次排成一棵完全二叉樹，則此樹的特點(diǎn)是：樹中所有結(jié)點(diǎn)的值均大于（或小于）其左右孩子，此樹的根結(jié)點(diǎn)（即堆頂）必最大（或最小）。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第43頁。數(shù)據(jù)結(jié)構(gòu)第十章44123456789注意：對于結(jié)點(diǎn)i，i>n/2時(shí)，表示結(jié)點(diǎn)i為葉子結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第44頁。數(shù)據(jù)結(jié)構(gòu)第十章例：45（大根堆）918566765867234561557有序列T1=（08,25,49,46,58,67）和序列T2=（91,85,76,66,58,67,55）,判斷它們是否“堆”？√（小根堆）√（小頂堆）（最小堆）（大頂堆）（最大堆）數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第45頁。數(shù)據(jù)結(jié)構(gòu)第十章2.怎樣建堆？46步驟：從最后一個(gè)非終端結(jié)點(diǎn)開始往前逐步調(diào)整，讓每個(gè)雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請建大根堆。解：為便于理解，先將原始序列畫成完全二叉樹的形式：完全二叉樹的第一個(gè)非終端結(jié)點(diǎn)編號必為n/2

?。?性質(zhì)5)注：終端結(jié)點(diǎn)（即葉子）沒有任何子女，無需單獨(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)向下比較！！數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第46頁。數(shù)據(jù)結(jié)構(gòu)第十章3.怎樣進(jìn)行堆排序？47關(guān)鍵：將堆的當(dāng)前頂點(diǎn)輸出后，如何將剩余序列重新調(diào)整為堆？方法：將當(dāng)前頂點(diǎn)與堆尾記錄交換，然后仿建堆動(dòng)作重新調(diào)整，如此反復(fù)直至排序結(jié)束。數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第47頁。數(shù)據(jù)結(jié)構(gòu)第十章例：對剛才建好的大頂堆進(jìn)行排序：4808252125*1649交換1號與6號記錄492525*21160812345649252125*1608初始最大堆2525*16211365420849數(shù)據(jù)結(jié)構(gòu)第十章全文共55頁，當(dāng)前為第48頁。數(shù)據(jù)結(jié)構(gòu)第十章491625*21082549交換1號與5號記錄08252125*1649從1號到5號重新調(diào)整為最大堆082525*2116491234561625*08252149136542082525*2508