數(shù)據(jù)結(jié)構(gòu)王紅梅排序技術(shù)學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)王紅梅排序數(shù)據(jù)結(jié)構(gòu)王紅梅排序(pi x)技術(shù)技術(shù)第一頁，共130頁。8.1 概概 述述 p 排序：給定一組記錄的集合排序：給定一組記錄的集合r1, r2, , rn，其相應(yīng)的關(guān)，其相應(yīng)的關(guān)鍵碼分別鍵碼分別(fnbi)為為k1, k2, , kn，排序是將這些記錄排列，排序是將這些記錄排列成順序?yàn)槌身樞驗(yàn)閞s1, rs2, , rsn的一個(gè)序列，使得相應(yīng)的關(guān)鍵碼的一個(gè)序列，使得相應(yīng)的關(guān)鍵碼滿足滿足ks1ks2ksn（稱為升序）或（稱為升序）或ks1ks2ksn（稱為降序）。稱為降序）。p 正序：待排序序列中的記錄已按關(guān)鍵碼排好序。正序：待排序序列中的記錄已按關(guān)鍵碼排好序。p 逆序

2、（反序）：待排序序列中記錄的排列順序與排好序的逆序（反序）：待排序序列中記錄的排列順序與排好序的順序正好相反。順序正好相反。排序排序(pi x)的基本的基本概念概念從操作角度看，排序是線性結(jié)構(gòu)從操作角度看，排序是線性結(jié)構(gòu)(jigu)的一種操作的一種操作 第1頁/共130頁第二頁，共130頁。排序算法的穩(wěn)定性：假定在待排序的記錄集中，存在排序算法的穩(wěn)定性：假定在待排序的記錄集中，存在多個(gè)具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的多個(gè)具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對相對(xingdu)次序仍然保持不變，即在原序列中，次序仍然保持不變，即在原序列中，ki=kj且且ri在在rj之前，而在

3、排序后的序列中，之前，而在排序后的序列中，ri仍在仍在rj之之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。 排序排序(pi x)的基本概的基本概念念學(xué)號學(xué)號姓名姓名高數(shù)高數(shù)英語英語思想品德思想品德0001王王 軍軍85880002李李 明明64920003湯曉影湯曉影85866872788.1 概概 述述 第2頁/共130頁第三頁，共130頁。排序排序(pi x)的基本的基本概念概念單鍵單鍵(dn jin)排序：根據(jù)一個(gè)關(guān)鍵碼進(jìn)行的排序；排序：根據(jù)一個(gè)關(guān)鍵碼進(jìn)行的排序；多鍵排序：根據(jù)多個(gè)關(guān)鍵碼進(jìn)行的排序。多鍵排序：根據(jù)多個(gè)關(guān)鍵碼進(jìn)行的排序。學(xué)號

4、學(xué)號姓名姓名高數(shù)高數(shù)英語英語思想品德思想品德0001王王 軍軍85880002李李 明明64920003湯曉影湯曉影8586687278按學(xué)號排序按學(xué)號排序(pi x)單鍵排序單鍵排序(pi x)按成績（高數(shù)英語思想品德）排序按成績（高數(shù)英語思想品德）排序(pi x)多鍵排序多鍵排序(pi x)8.1 概概 述述 第3頁/共130頁第四頁，共130頁。排序排序(pi x)的基本概的基本概念念多鍵排序多鍵排序單鍵排序單鍵排序8.1 概概 述述 第4頁/共130頁第五頁，共130頁。排序的分類排序的分類1. 內(nèi)排序：在排序的整個(gè)過程中，待排序的所有記錄全內(nèi)排序：在排序的整個(gè)過程中，待排序的所有記錄

5、全部被放置在內(nèi)存中部被放置在內(nèi)存中2. 外排序：由于外排序：由于(yuy)待排序的記錄個(gè)數(shù)太多，不能待排序的記錄個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另同時(shí)放置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另一部分記錄放置在外存上，整個(gè)排序過程需要在內(nèi)外存一部分記錄放置在外存上，整個(gè)排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。排序排序(pi x)的基本概的基本概念念8.1 概概 述述 第5頁/共130頁第六頁，共130頁。排序排序(pi x)的基本的基本概念概念8.1 概概 述述 第6頁/共130頁第七頁，共130頁。1. 基本操作

6、。內(nèi)排序基本操作。內(nèi)排序(pi x)在排序在排序(pi x)過程中的基本操作：過程中的基本操作：比較：關(guān)鍵碼之間的比較；比較：關(guān)鍵碼之間的比較；移動(dòng)：記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。移動(dòng)：記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。 2. 輔助存儲(chǔ)空間。輔助存儲(chǔ)空間。輔助存儲(chǔ)空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存放待排序輔助存儲(chǔ)空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存放待排序(pi x)記錄占用的存儲(chǔ)空間之外，執(zhí)行算法所需要的其他存儲(chǔ)記錄占用的存儲(chǔ)空間之外，執(zhí)行算法所需要的其他存儲(chǔ)空間?？臻g。3. 算法本身的復(fù)雜程度。算法本身的復(fù)雜程度。 排序算法排序算法(sun f)的性能的性能8.1 概概 述述 第7頁

7、/共130頁第八頁，共130頁。排序算法排序算法(sun f)的存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)從操作從操作(cozu)角度看，排序是線性結(jié)構(gòu)的一種操作角度看，排序是線性結(jié)構(gòu)的一種操作(cozu)，待排序記錄可以用順序存儲(chǔ)結(jié)構(gòu)或鏈接存，待排序記錄可以用順序存儲(chǔ)結(jié)構(gòu)或鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。儲(chǔ)結(jié)構(gòu)存儲(chǔ)。假定假定2：將待排序：將待排序(pi x)的記錄序列排序的記錄序列排序(pi x)為升序序列。為升序序列。 int rn+1; /待排序記錄存儲(chǔ)在待排序記錄存儲(chǔ)在r1rn，r0留做他用留做他用假定假定1 1：采用采用順序順序存儲(chǔ)結(jié)構(gòu)，關(guān)鍵碼為存儲(chǔ)結(jié)構(gòu)，關(guān)鍵碼為整型整型，且記錄只有，且記錄只有關(guān)鍵碼關(guān)鍵碼一個(gè)一個(gè)數(shù)據(jù)項(xiàng)

8、。數(shù)據(jù)項(xiàng)。8.1 概概 述述 第8頁/共130頁第九頁，共130頁。8.2 插入排序插入排序插入排序的主要操作是插入，其基本思想是：每插入排序的主要操作是插入，其基本思想是：每次將一個(gè)待排序的記錄按其關(guān)鍵碼的大小次將一個(gè)待排序的記錄按其關(guān)鍵碼的大小(dxio)插入到一個(gè)已經(jīng)排好序的有序序列中，直到全部插入到一個(gè)已經(jīng)排好序的有序序列中，直到全部記錄排好序?yàn)橹埂Ｓ涗浥藕眯驗(yàn)橹?。?頁/共130頁第十頁，共130頁?；舅枷耄涸诓迦牖舅枷耄涸诓迦?ch r)第第 i（i1）個(gè)記錄時(shí)，前面的）個(gè)記錄時(shí)，前面的 i-1個(gè)記錄已經(jīng)排好序。個(gè)記錄已經(jīng)排好序。 直接直接(zhji)插入排序插入排序有序序列有

9、序序列無序序列無序序列12i-1ini+112i-1ini+18.2 插入排序插入排序第10頁/共130頁第十一頁，共130頁。基本思想基本思想(sxing)：在插入第：在插入第 i（i1）個(gè)記錄時(shí)，前面的）個(gè)記錄時(shí)，前面的 i-1個(gè)記錄已經(jīng)排好序。個(gè)記錄已經(jīng)排好序。 （1）如何構(gòu)造初始(ch sh)的有序序列？（2）如何查找待插入記錄的插入位置?直接直接(zhji)插入排序插入排序需解決的關(guān)鍵問題需解決的關(guān)鍵問題?8.2 插入排序插入排序第11頁/共130頁第十二頁，共130頁。r 0 1 2 3 4 5 6i = 2i = 3i = 4i = 6i = 5r0的作用的作用?暫存單元暫存單元

10、(dnyun)監(jiān)視哨監(jiān)視哨8.2 插入排序插入排序第12頁/共130頁第十三頁，共130頁。解決方法：解決方法：將第將第1個(gè)記錄看成是初始有序表，然后從第個(gè)記錄看成是初始有序表，然后從第2個(gè)記錄起依次個(gè)記錄起依次插入插入(ch r)到這個(gè)有序表中，直到將第到這個(gè)有序表中，直到將第n個(gè)記錄插入個(gè)記錄插入(ch r)。關(guān)鍵問題關(guān)鍵問題(1)如何構(gòu)造初始如何構(gòu)造初始(ch sh)的有序序列？的有序序列？算法描述算法描述(mio sh)：for (i=2; i=n; i+) 插入第插入第i個(gè)記錄，即第個(gè)記錄，即第i趟直接插入排序；趟直接插入排序；8.2 插入排序插入排序第13頁/共130頁第十四頁，共

11、130頁。關(guān)鍵問題關(guān)鍵問題(2)如何查找待插入記錄如何查找待插入記錄(jl)的插入位置的插入位置?解決方法：解決方法：在在i-1個(gè)記錄的有序區(qū)個(gè)記錄的有序區(qū)r1 ri-1中插入記錄中插入記錄ri，首先，首先(shuxin)順序查找順序查找ri的正確插入位置，然后將的正確插入位置，然后將ri插入插入到相應(yīng)位置。到相應(yīng)位置。r0有兩個(gè)作用：有兩個(gè)作用：1. 進(jìn)入循環(huán)之前進(jìn)入循環(huán)之前(zhqin)暫存了暫存了ri的值，使得不的值，使得不致于因記錄的后移而丟失致于因記錄的后移而丟失ri的內(nèi)容；的內(nèi)容；2. 在查找插入位置的循環(huán)在查找插入位置的循環(huán)中充當(dāng)哨兵。中充當(dāng)哨兵。算法描述：算法描述：r0=ri;

12、 j=i-1; while (r0rj) rj+1=rj; j-;8.2 插入排序插入排序第14頁/共130頁第十五頁，共130頁。void insertSort (int r , int n) for (i=2; i=n; i+) r0=ri; j=i-1; while (r0=ri-1，內(nèi)層循，內(nèi)層循環(huán)會(huì)出現(xiàn)什么情況環(huán)會(huì)出現(xiàn)什么情況?8.2 插入排序插入排序第15頁/共130頁第十六頁，共130頁。直接直接(zhji)插入排序算法性能分插入排序算法性能分析析最好最好(zu ho)(zu ho)情況下（正序）：情況下（正序）： 時(shí)間時(shí)間(shjin)復(fù)雜度為復(fù)雜度為O(n)。比較次數(shù)：比較次

13、數(shù)：n-1移動(dòng)次數(shù)：移動(dòng)次數(shù)：2(n-1) 8.2 插入排序插入排序第16頁/共130頁第十七頁，共130頁。直接直接(zhji)插入排序算法性能分析插入排序算法性能分析最好最好(zu ho)(zu ho)情況下（正序）：情況下（正序）： 比較次數(shù)：比較次數(shù)：n-1移動(dòng)次數(shù)：移動(dòng)次數(shù)：2(n-1) 最壞情況最壞情況(qngkung)(qngkung)下（逆下（逆序或反序）：序或反序）： 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n2)。比較次數(shù)：比較次數(shù)：移動(dòng)次數(shù)：移動(dòng)次數(shù)：2) 1)(2(2- -+ += = = =nnini2) 1)(4(1- -+ += =+ + nnin2= =i）（時(shí)間復(fù)雜度為時(shí)

14、間復(fù)雜度為O(n)。8.2 插入排序插入排序第17頁/共130頁第十八頁，共130頁。平均情況下（隨機(jī)平均情況下（隨機(jī)(su j)(su j)排列）：排列）： 直接直接(zhji)插入排序算法性能分析插入排序算法性能分析時(shí)間時(shí)間(shjin)復(fù)雜度為復(fù)雜度為O(n2)。比較次數(shù)：比較次數(shù)：移動(dòng)次數(shù)：移動(dòng)次數(shù)：4) 1)(4(- -+ += = nnn2= =i4) 1)(2(2- -+ += = = =nnnii2（21+ +i）8.2 插入排序插入排序第18頁/共130頁第十九頁，共130頁。空間性能：需要一個(gè)空間性能：需要一個(gè)(y )記錄的輔助空間。記錄的輔助空間。直接插入排序算法是一種穩(wěn)

15、定的排序算法。直接插入排序算法是一種穩(wěn)定的排序算法。直接直接(zhji)插入排序算法性能分插入排序算法性能分析析直接插入排序算法簡單、容易直接插入排序算法簡單、容易(rngy)實(shí)現(xiàn)，適實(shí)現(xiàn)，適用于待排序記錄基本有序或待排序記錄較小時(shí)。用于待排序記錄基本有序或待排序記錄較小時(shí)。當(dāng)待排序的記錄個(gè)數(shù)較多時(shí)，大量的比較和移動(dòng)當(dāng)待排序的記錄個(gè)數(shù)較多時(shí)，大量的比較和移動(dòng)操作使直接插入排序算法的效率降低。操作使直接插入排序算法的效率降低。8.2 插入排序插入排序第19頁/共130頁第二十頁，共130頁。如何改進(jìn)直接插入排序如何改進(jìn)直接插入排序?注意到，在插入第注意到，在插入第 i（i1）個(gè)記錄時(shí)，前面的）個(gè)

16、記錄時(shí)，前面的 i-1 個(gè)記錄已個(gè)記錄已經(jīng)經(jīng)(y jing)排好序，則在尋找插入位置時(shí)，可以用折半查找來排好序，則在尋找插入位置時(shí)，可以用折半查找來代替順序查找，從而減少比較次數(shù)。代替順序查找，從而減少比較次數(shù)。請同學(xué)們寫出這個(gè)改進(jìn)的直接插入排序算法請同學(xué)們寫出這個(gè)改進(jìn)的直接插入排序算法(sun f)，并，并分析時(shí)間性能。分析時(shí)間性能。8.2 插入排序插入排序第20頁/共130頁第二十一頁，共130頁。希爾排序希爾排序(pi x)改進(jìn)的著眼點(diǎn)：改進(jìn)的著眼點(diǎn)：（1 1）若待排序記錄按關(guān)鍵碼基本有序時(shí)，直接插入）若待排序記錄按關(guān)鍵碼基本有序時(shí)，直接插入排序的效率可以排序的效率可以(ky)(ky)大

17、大提高；大大提高；（2 2）由于直接插入排序算法簡單，則在待排序記錄）由于直接插入排序算法簡單，則在待排序記錄數(shù)量數(shù)量n n較小時(shí)效率也很高。較小時(shí)效率也很高。 8.2 插入排序插入排序第21頁/共130頁第二十二頁，共130頁。（1 1）應(yīng)如何分割待排序記錄，才能保證整個(gè)序列逐步）應(yīng)如何分割待排序記錄，才能保證整個(gè)序列逐步向基本有序發(fā)展？向基本有序發(fā)展？（2 2）子序列內(nèi)如何進(jìn)行）子序列內(nèi)如何進(jìn)行(jnxng)(jnxng)直接插入排序？直接插入排序？需解決的關(guān)鍵問題需解決的關(guān)鍵問題?基本基本(jbn)(jbn)思想：將整個(gè)待排序記錄分割成若干個(gè)子思想：將整個(gè)待排序記錄分割成若干個(gè)子序列，在

18、子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本中的記錄基本(jbn)(jbn)有序時(shí)，對全體記錄進(jìn)行直接插有序時(shí)，對全體記錄進(jìn)行直接插入排序。入排序。希爾排序希爾排序(pi x)8.2 插入排序插入排序第22頁/共130頁第二十三頁，共130頁。基本有序：接近正序，例如基本有序：接近正序，例如1, 2, 8, 4, 5, 6, 7, 3, 9；局部有序：部分有序，例如局部有序：部分有序，例如6, 7, 8, 9, 1, 2, 3, 4, 5。局部有序不能提高直接插入排序算法局部有序不能提高直接插入排序算法(sun f)的時(shí)間的時(shí)間性能。性能

19、。 希爾排序希爾排序(pi x)分割待排序記錄的目的分割待排序記錄的目的?1. 減少待排序減少待排序(pi x)記錄個(gè)數(shù)；記錄個(gè)數(shù)；2. 使整個(gè)序列向基本有序發(fā)展。使整個(gè)序列向基本有序發(fā)展。 子序列的構(gòu)成不能是簡單地子序列的構(gòu)成不能是簡單地“逐段分割逐段分割”，而是將相距某，而是將相距某個(gè)個(gè)“增量增量”的記錄組成一個(gè)子序列。的記錄組成一個(gè)子序列。 啟示啟示?8.2 插入排序插入排序第23頁/共130頁第二十四頁，共130頁。1 2 3 4 5 6 7 8 9初始初始(ch sh)序列序列d = 4d = 2d = 18.2 插入排序插入排序第24頁/共130頁第二十五頁，共130頁。解決方法：

20、解決方法：將相隔某個(gè)將相隔某個(gè)“增量增量”的記錄組成一個(gè)子序列的記錄組成一個(gè)子序列(xli)。增量應(yīng)如何??？增量應(yīng)如何??？希爾最早提出的方法是希爾最早提出的方法是d1=n/2，di+1=di/2。關(guān)鍵問題關(guān)鍵問題(1)(1)應(yīng)如何分割應(yīng)如何分割(fng)(fng)待排序待排序記錄？記錄？算法描述：算法描述：for (d=n/2; d=1; d=d/2) 以以d為增量為增量(zn lin)，進(jìn)行組內(nèi)直接插入排序，進(jìn)行組內(nèi)直接插入排序；8.2 插入排序插入排序第25頁/共130頁第二十六頁，共130頁。解決方法：解決方法：在插入記錄在插入記錄riri時(shí)，自時(shí)，自ri-dri-d起往前跳躍起往前跳躍

21、(tioyu)(tioyu)式（式（跳躍跳躍(tioyu)(tioyu)幅度為幅度為d d）搜索待插入位置，并且）搜索待插入位置，并且r0r0只是只是暫存單元，不是哨兵。當(dāng)搜索位置暫存單元，不是哨兵。當(dāng)搜索位置0 0，表示插入位置已，表示插入位置已找到。找到。在搜索過程中，記錄后移也是跳躍在搜索過程中，記錄后移也是跳躍(tioyu)d(tioyu)d個(gè)位置。個(gè)位置。在整個(gè)序列中，前在整個(gè)序列中，前d d個(gè)記錄分別是個(gè)記錄分別是d d個(gè)子序列中的第一個(gè)記個(gè)子序列中的第一個(gè)記錄，所以從第錄，所以從第d+1d+1個(gè)記錄開始進(jìn)行插入。個(gè)記錄開始進(jìn)行插入。關(guān)鍵問題關(guān)鍵問題(2)(2)子序列子序列(xli

22、)(xli)內(nèi)如何進(jìn)行直接插入排內(nèi)如何進(jìn)行直接插入排序？序？8.2 插入排序插入排序第26頁/共130頁第二十七頁，共130頁。1 2 3 4 5 6 7 8 9初始初始(ch sh)序列序列d = 4ijj8.2 插入排序插入排序第27頁/共130頁第二十八頁，共130頁。1 2 3 4 5 6 7 8 9初始初始(ch sh)序列序列d = 4ijj8.2 插入排序插入排序第28頁/共130頁第二十九頁，共130頁。1 2 3 4 5 6 7 8 9初始初始(ch sh)序列序列d = 4ijj8.2 插入排序插入排序第29頁/共130頁第三十頁，共130頁。1 2 3 4 5 6 7 8

23、 9初始初始(ch sh)序列序列d = 4ij8.2 插入排序插入排序第30頁/共130頁第三十一頁，共130頁。1 2 3 4 5 6 7 8 9初始初始(ch sh)序列序列d = 4ijjj8.2 插入排序插入排序第31頁/共130頁第三十二頁，共130頁。算法算法(sun f)描述：描述：for (i=d+1; i0 & r0rj+1） rjrj+1； exchange=j； 解決方法：解決方法：設(shè)變量設(shè)變量exchange記載記錄交換的位置，則一趟排序后，記載記錄交換的位置，則一趟排序后，exchange記載的一定是這一趟排序中記錄的最后記載的一定是這一趟排序中記錄的最后(zuhu

24、)一次交換的位置，一次交換的位置，且從此位置以后的所有記錄均已經(jīng)有序。且從此位置以后的所有記錄均已經(jīng)有序。8.3 交換排序交換排序第39頁/共130頁第四十頁，共130頁。解決方法：解決方法：設(shè)設(shè)bound位置的記錄是無序區(qū)的最后一個(gè)記錄，則每趟起位置的記錄是無序區(qū)的最后一個(gè)記錄，則每趟起泡排序的范圍是泡排序的范圍是r1 rbound。在一趟排序后，從在一趟排序后，從exchange位置之后的記錄一定位置之后的記錄一定(ydng)是是有序的，所以有序的，所以bound=exchange。關(guān)鍵問題：如何關(guān)鍵問題：如何(rh)(rh)確定起泡排序的范圍？確定起泡排序的范圍？交換交換交換交換交換交換

25、8.3 交換交換(jiohun)排序排序第40頁/共130頁第四十一頁，共130頁。解決解決(jiju)方法：方法：設(shè)設(shè)bound位置的記錄是無序區(qū)的最后一個(gè)記錄，則每位置的記錄是無序區(qū)的最后一個(gè)記錄，則每趟起泡排序的范圍是趟起泡排序的范圍是r1 rbound。在一趟排序后，從在一趟排序后，從exchange位置之后的記錄一定是有位置之后的記錄一定是有序的，所以序的，所以bound=exchange。關(guān)鍵問題：如何確定關(guān)鍵問題：如何確定(qudng)(qudng)起泡排序的范圍？起泡排序的范圍？算法算法(sun f)描述：描述：bound=exchange; for (j=1; jrj+1）

26、rjrj+1； exchange=j； 8.3 交換排序交換排序第41頁/共130頁第四十二頁，共130頁。解決方法：解決方法：在每一趟起泡排序之前，令在每一趟起泡排序之前，令exchangeexchange的初值為的初值為0 0，在，在以后的排序過程中，只要有記錄交換，以后的排序過程中，只要有記錄交換，exchangeexchange的的值就會(huì)大于值就會(huì)大于0 0。這樣。這樣(zhyng)(zhyng)，在一趟比較完畢，在一趟比較完畢，就可以通過就可以通過exchangeexchange的值是否為的值是否為0 0來判別是否有記錄來判別是否有記錄交換，從而判別整個(gè)起泡排序的結(jié)束。交換，從而判別

27、整個(gè)起泡排序的結(jié)束。關(guān)鍵問題：如何判別起泡關(guān)鍵問題：如何判別起泡(q po)(q po)排序的結(jié)束？排序的結(jié)束？8.3 交換交換(jiohun)排序排序第42頁/共130頁第四十三頁，共130頁。解決方法：解決方法：在每一趟起泡排序之前，令在每一趟起泡排序之前，令exchangeexchange的初值為的初值為0 0，在以后的，在以后的排序過程中，只要有記錄交換，排序過程中，只要有記錄交換，exchangeexchange的值就會(huì)大于的值就會(huì)大于0 0。這樣，在一趟比較完畢，就可以這樣，在一趟比較完畢，就可以(ky)(ky)通過通過exchangeexchange的值是的值是否為否為0 0來判

28、別是否有記錄交換，從而判別整個(gè)起泡排序的結(jié)來判別是否有記錄交換，從而判別整個(gè)起泡排序的結(jié)束。束。關(guān)鍵問題：如何關(guān)鍵問題：如何(rh)(rh)判別起泡排序的結(jié)束？判別起泡排序的結(jié)束？算法描述：算法描述：while (exchange) 執(zhí)行一趟起泡執(zhí)行一趟起泡(q po)排序；排序；8.3 交換排序交換排序第43頁/共130頁第四十四頁，共130頁。void BubbleSort( (int r , int n) ) exchange=n; while ( (exchange) ) bound=exchange; exchange=0； for ( (j=1; jrj+1) ) rjrj+1；

29、exchange=j； 起泡起泡(q po)排序算法排序算法8.3 交換交換(jiohun)排序排序第44頁/共130頁第四十五頁，共130頁。起泡排序的時(shí)間性能起泡排序的時(shí)間性能(xngnng)分析分析最好最好(zu ho)情況（正序）：情況（正序）：比較次數(shù)：比較次數(shù)：n-1移動(dòng)次數(shù)：移動(dòng)次數(shù)：0 時(shí)間時(shí)間(shjin)復(fù)雜度為復(fù)雜度為O(n)。8.3 交換排序交換排序第45頁/共130頁第四十六頁，共130頁。最壞情況最壞情況(qngkung)(qngkung)（反序（反序）：）：起泡起泡(q po)排序的時(shí)間性能分排序的時(shí)間性能分析析最好最好(zu ho)情況（正序）：情況（正序）：比

30、較次數(shù)：比較次數(shù)：n-1移動(dòng)次數(shù)：移動(dòng)次數(shù)：0 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n)；時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n2)。比較次數(shù)：比較次數(shù)：移動(dòng)次數(shù)：移動(dòng)次數(shù)：2) 1(1- -= = = =nn(n-i)n-1i2) 1(1- -= = = =n3n3(n-i)n-1i平均情況：平均情況：時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n2)。8.3 交換排序交換排序第46頁/共130頁第四十七頁，共130頁。快速快速(kui s)(kui s)排序排序改進(jìn)的著眼點(diǎn)：在起泡排序中，記錄的比較和移動(dòng)是在相鄰改進(jìn)的著眼點(diǎn)：在起泡排序中，記錄的比較和移動(dòng)是在相鄰單元中進(jìn)行的，記錄每次交換只能上移或下移一個(gè)單元，因單元中

31、進(jìn)行的，記錄每次交換只能上移或下移一個(gè)單元，因而而(yn r)總的比較次數(shù)和移動(dòng)次數(shù)較多?？偟谋容^次數(shù)和移動(dòng)次數(shù)較多。減少減少(jinsho)總的比較次數(shù)和移動(dòng)次數(shù)總的比較次數(shù)和移動(dòng)次數(shù)增大記錄的比較和移動(dòng)距離增大記錄的比較和移動(dòng)距離較大記錄從前面直接移動(dòng)到后面較大記錄從前面直接移動(dòng)到后面較小記錄從后面直接移動(dòng)到前面較小記錄從后面直接移動(dòng)到前面8.3 交換排序交換排序第47頁/共130頁第四十八頁，共130頁?？焖倥判蚩焖倥判?pi x)的基本思想的基本思想首先選一個(gè)軸值（即比較的基準(zhǔn)），通過一趟排序首先選一個(gè)軸值（即比較的基準(zhǔn)），通過一趟排序(pi x)將將待排序待排序(pi x)記錄分割成

32、獨(dú)立的兩部分，前一部分記錄的關(guān)記錄分割成獨(dú)立的兩部分，前一部分記錄的關(guān)鍵碼均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等鍵碼均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等于軸值，然后分別對這兩部分重復(fù)上述方法，直到整個(gè)序列于軸值，然后分別對這兩部分重復(fù)上述方法，直到整個(gè)序列有序。有序。如何選擇軸值？如何選擇軸值？如何實(shí)現(xiàn)如何實(shí)現(xiàn)(shxin)分割（稱一次劃分）？分割（稱一次劃分）？如何處理分割得到的兩個(gè)待排序子序列？如何處理分割得到的兩個(gè)待排序子序列？如何判別快速排序的結(jié)束？如何判別快速排序的結(jié)束？需解決的關(guān)鍵問題需解決的關(guān)鍵問題?8.3 交換排序交換排序第48頁/共130頁第四十九頁，共

33、130頁。選擇軸值的方法：選擇軸值的方法：1.使用第一個(gè)記錄的關(guān)鍵碼；使用第一個(gè)記錄的關(guān)鍵碼；2.選取序列中間記錄的關(guān)鍵碼；選取序列中間記錄的關(guān)鍵碼；3.比較序列中第一個(gè)記錄、最后一個(gè)記錄和中間記錄比較序列中第一個(gè)記錄、最后一個(gè)記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的關(guān)鍵碼，取關(guān)鍵碼居中(jzhng)的作為軸值并調(diào)換的作為軸值并調(diào)換到第一個(gè)記錄的位置；到第一個(gè)記錄的位置；4.隨機(jī)選取軸值。隨機(jī)選取軸值。關(guān)鍵問題：如何關(guān)鍵問題：如何(rh)(rh)選擇軸值？選擇軸值？選取不同軸值的后果選取不同軸值的后果(hugu)：決定兩個(gè)子序列的長度，子序列的長度最好相等。決定兩個(gè)子序列的長度，子序列的長度最好

34、相等。8.3 交換排序交換排序第49頁/共130頁第五十頁，共130頁。ji關(guān)鍵問題：如何實(shí)現(xiàn)關(guān)鍵問題：如何實(shí)現(xiàn)(shxin)(shxin)一次劃分？一次劃分？jjiiijijjj8.3 交換交換(jiohun)排序排序第50頁/共130頁第五十一頁，共130頁。解決方法：解決方法：設(shè)待劃分的序列是設(shè)待劃分的序列是rs rt，設(shè)參數(shù)，設(shè)參數(shù)i，j分別指向子分別指向子序列左、右兩端的下標(biāo)序列左、右兩端的下標(biāo)s和和t，令，令rs為軸值，為軸值，（1）j從后向前從后向前(xin qin)掃描，直到掃描，直到rjri，將，將rj移動(dòng)到移動(dòng)到ri的位置，使關(guān)鍵碼小（同軸值相比）的的位置，使關(guān)鍵碼?。ㄍS

35、值相比）的記錄移動(dòng)到前面去；記錄移動(dòng)到前面去；（2）i從前向后掃描，直到從前向后掃描，直到rirj，將，將ri移動(dòng)到移動(dòng)到rj的位置，使關(guān)鍵碼大（同軸值比較）的記錄移動(dòng)到后的位置，使關(guān)鍵碼大（同軸值比較）的記錄移動(dòng)到后面去；面去；（3）重復(fù)上述過程，直到）重復(fù)上述過程，直到i=j。關(guān)鍵問題：如何實(shí)現(xiàn)關(guān)鍵問題：如何實(shí)現(xiàn)(shxin)(shxin)一次劃分？一次劃分？8.3 交換交換(jiohun)排序排序第51頁/共130頁第五十二頁，共130頁。關(guān)鍵問題：如何關(guān)鍵問題：如何(rh)(rh)實(shí)現(xiàn)一次劃分？實(shí)現(xiàn)一次劃分？算法算法(sun f)描述：描述：int Partition(int r ,

36、int first, int end) i=first; j=end; /初始化初始化 while (ij) while (ij & ri= rj) j-； /右側(cè)掃描右側(cè)掃描 if (ij) rirj; i+; /將較小記錄交換到前面將較小記錄交換到前面 while (ij & ri= rj) i+； /左側(cè)掃描左側(cè)掃描 if (ij) rjri; j-; /將較大記錄交換到后面將較大記錄交換到后面(hu mian) retutn i; /i為軸值記錄的最終位置為軸值記錄的最終位置8.3 交換排序交換排序第52頁/共130頁第五十三頁，共130頁。解決方法解決方法(fngf)(fngf)：對

37、分割得到的兩個(gè)子序列遞歸地執(zhí)行快速排序。對分割得到的兩個(gè)子序列遞歸地執(zhí)行快速排序。關(guān)鍵問題：如何關(guān)鍵問題：如何(rh)(rh)處理分割得到的兩個(gè)待排序子序列？處理分割得到的兩個(gè)待排序子序列？ ijij8.3 交換交換(jiohun)排序排序第53頁/共130頁第五十四頁，共130頁。算法算法(sun f)(sun f)描述：描述：關(guān)鍵問題：如何關(guān)鍵問題：如何(rh)(rh)處理分割得到的兩個(gè)待排序子序列處理分割得到的兩個(gè)待排序子序列？ void QuickSort (int r , int first, int end ) pivotpos = Partition (r, first, end

38、 ); /一次劃分一次劃分 QuickSort (r, first, pivotpos-1); /對前一個(gè)子序列進(jìn)行快速對前一個(gè)子序列進(jìn)行快速(kui s)排序排序 QuickSort (r, pivotpos+1, end ); /對后一個(gè)子序列進(jìn)行快速對后一個(gè)子序列進(jìn)行快速(kui s)排序排序8.3 交換排序交換排序第54頁/共130頁第五十五頁，共130頁。解決方法：解決方法：若待排序列中只有一個(gè)記錄，顯然已有序，否則進(jìn)行一若待排序列中只有一個(gè)記錄，顯然已有序，否則進(jìn)行一次劃分后，再分別次劃分后，再分別(fnbi)(fnbi)對分割所得的兩個(gè)子序列進(jìn)對分割所得的兩個(gè)子序列進(jìn)行快速排序（

39、即遞歸處理）。行快速排序（即遞歸處理）。 關(guān)鍵問題：如何判別快速關(guān)鍵問題：如何判別快速(kui s)(kui s)排序的結(jié)束？排序的結(jié)束？ 8.3 交換交換(jiohun)排序排序第55頁/共130頁第五十六頁，共130頁。void QuickSort (int r , int first, int end )/在序列在序列 firstend中遞歸地進(jìn)行中遞歸地進(jìn)行(jnxng)快快速排序速排序 if (first end) pivotpos = Partition (r, first, end ); QuickSort (r, first, pivotpos-1); QuickSort (r

40、, pivotpos+1, end ); 算法算法(sun f)(sun f)描述：描述：關(guān)鍵問題：如何關(guān)鍵問題：如何(rh)(rh)判別快速排序的結(jié)束？判別快速排序的結(jié)束？ 8.3 交換排序交換排序第56頁/共130頁第五十七頁，共130頁。例：例：38, 27, 55, 50, 13, 49, 65的快速排序的快速排序(pi x)遞歸遞歸樹如下：樹如下：38135055496527快速快速(kui s)排序的遞歸執(zhí)行過程可以用遞歸樹描述。排序的遞歸執(zhí)行過程可以用遞歸樹描述?？焖倏焖?kui s)排序的時(shí)間性能排序的時(shí)間性能分析分析8.3 交換排序交換排序第57頁/共130頁第五十八頁，共1

41、30頁?？焖倥判蚩焖倥判?pi x)的時(shí)間性能的時(shí)間性能分析分析快速排序的時(shí)間快速排序的時(shí)間(shjin)(shjin)性能性能快速快速(kui s)(kui s)排序遞歸的深度排序遞歸的深度每次劃分軸值的選取每次劃分軸值的選取8.3 交換排序交換排序第58頁/共130頁第五十九頁，共130頁。最好最好(zu ho)情況：情況：每一次劃分對一個(gè)記錄定位后，該記錄的左側(cè)子表與右側(cè)每一次劃分對一個(gè)記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為子表的長度相同，為O(nlog2n)?？焖倥判虻臅r(shí)間性能快速排序的時(shí)間性能(xngnng)分析分析T(n)2T(n/2)n 2(2T(n/4)n/2)n

42、4T(n/4)2n 4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n)8.3 交換交換(jiohun)排序排序第59頁/共130頁第六十頁，共130頁。最壞情況：最壞情況：每次劃分只得到一個(gè)每次劃分只得到一個(gè)(y )比上一次劃分少一個(gè)比上一次劃分少一個(gè)(y )記錄的子序列（另一個(gè)記錄的子序列（另一個(gè)(y )子序列為空），為子序列為空），為 O(n2)。最好情況最好情況(qngkung)：每一次劃分對一個(gè)記錄定位后，該記錄的左側(cè)子表與右側(cè)每一次劃分對一個(gè)記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為子表的長度相同，為O(nlog2n)?？焖倏焖?ku

43、i s)排序的時(shí)間性能分排序的時(shí)間性能分析析平均情況：平均情況：為為O(nlog2n)。)() 1(21211nOnninni= =- -= =- - - -= =）（8.3 交換排序交換排序第60頁/共130頁第六十一頁，共130頁。選擇排序的主要操作選擇排序的主要操作(cozu)(cozu)是選擇，其主要思想是：是選擇，其主要思想是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，添加到有序序列中。添加到有序序列中。 8.4 選擇選擇(xunz)排序排序有序序列有序序列12i-1ink無序序列無序序列ni+112i-1ii交交換換 最小記最小

44、記錄錄第61頁/共130頁第六十二頁，共130頁。簡單簡單(jindn)(jindn)選擇排序選擇排序基本思想：第基本思想：第i i 趟在趟在n-i+1n-i+1（i=1,2,n-1i=1,2,n-1）個(gè)記錄中選取關(guān)）個(gè)記錄中選取關(guān)鍵碼最小的記錄作為鍵碼最小的記錄作為(zuwi)(zuwi)有序序列中的第有序序列中的第i i個(gè)記錄。個(gè)記錄。 需解決的關(guān)鍵問題需解決的關(guān)鍵問題?如何在待排序序列中選出關(guān)鍵碼最小的記錄如何在待排序序列中選出關(guān)鍵碼最小的記錄(jl)(jl)？如何確定待排序序列中關(guān)鍵碼最小的記錄如何確定待排序序列中關(guān)鍵碼最小的記錄(jl)(jl)在有在有序序列中的位置？序序列中的位置？

45、 8.4 選擇排序選擇排序第62頁/共130頁第六十三頁，共130頁。簡單簡單(jindn)選擇排序示選擇排序示例例最小者最小者 08交換交換(jiohun)21,08最小者最小者 16交換交換(jiohun)25,16最小者最小者 21交換交換49,218.4 選擇排序選擇排序第63頁/共130頁第六十四頁，共130頁。最小者最小者 25交換交換(jiohun)25,28最小者最小者 28不交換不交換(jiohun)簡單簡單(jindn)選擇排序示選擇排序示例例無序區(qū)只有無序區(qū)只有一個(gè)記錄一個(gè)記錄8.4 選擇排序選擇排序第64頁/共130頁第六十五頁，共130頁。解決方法解決方法(fngf)

46、：設(shè)置一個(gè)整型變量設(shè)置一個(gè)整型變量index，用于記錄在一趟比較的過程中關(guān)，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。鍵碼最小的記錄位置。 關(guān)鍵問題：如何關(guān)鍵問題：如何(rh)(rh)在無序區(qū)中選出關(guān)鍵碼最小的記錄在無序區(qū)中選出關(guān)鍵碼最小的記錄？indexindexindex8.4 選擇選擇(xunz)排序排序第65頁/共130頁第六十六頁，共130頁。算法算法(sun f)描述：描述：index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j;解決方法解決方法(fngf)：設(shè)置一個(gè)整型變量設(shè)置一個(gè)整型變量index，用于記錄在一趟比較的過程中

47、，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。關(guān)鍵碼最小的記錄位置。 關(guān)鍵問題：如何在無序關(guān)鍵問題：如何在無序(w x)(w x)區(qū)中選出關(guān)鍵碼最小的記區(qū)中選出關(guān)鍵碼最小的記錄？錄？8.4 選擇排序選擇排序第66頁/共130頁第六十七頁，共130頁。解決方法：解決方法：第第i趟簡單選擇排序的待排序區(qū)間是趟簡單選擇排序的待排序區(qū)間是ri rn，則，則ri是無是無序區(qū)第一個(gè)記錄序區(qū)第一個(gè)記錄(jl)，所以，將，所以，將index所記載的關(guān)鍵碼最小所記載的關(guān)鍵碼最小的記錄的記錄(jl)與與ri交換。交換。關(guān)鍵問題：如何關(guān)鍵問題：如何(rh)(rh)確定最小記錄的最終位置？確定最小記錄的最終位置？

48、算法算法(sun f)描述：描述： if (index!=i) ririndex; 8.4 選擇排序選擇排序第67頁/共130頁第六十八頁，共130頁。void selectSort ( int r , int n) for ( i=1; in; i+) index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j; if (index!=i) ri rindex; 簡單簡單(jindn)選擇排序算法選擇排序算法8.4 選擇選擇(xunz)排序排序第68頁/共130頁第六十九頁，共130頁。簡單選擇排序算法簡單選擇排序算法(sun f)的性能分的性能分

49、析析移動(dòng)次數(shù)：移動(dòng)次數(shù)：最好最好(zu ho)情況（正序）：情況（正序）：0次次8.4 選擇選擇(xunz)排序排序第69頁/共130頁第七十頁，共130頁。最壞情況最壞情況(qngkung)：3(n-1)次次簡單選擇排序算法簡單選擇排序算法(sun f)的性能分的性能分析析移動(dòng)次數(shù)：移動(dòng)次數(shù)：最好最好(zu ho)情況（正序）：情況（正序）：0次次空間性能：空間性能：需一個(gè)輔助空間。需一個(gè)輔助空間。穩(wěn)定性：穩(wěn)定性：是一種穩(wěn)定的排序算法。是一種穩(wěn)定的排序算法。比較次數(shù)：比較次數(shù)：)() 1(21211nOnninni= =- -= =- - - -= =）（簡單選擇排序的時(shí)間復(fù)雜度為簡單選擇排

50、序的時(shí)間復(fù)雜度為O(n2)。8.4 選擇排序選擇排序第70頁/共130頁第七十一頁，共130頁。堆排序堆排序改進(jìn)的著眼點(diǎn)：如何減少關(guān)鍵碼間的比較改進(jìn)的著眼點(diǎn)：如何減少關(guān)鍵碼間的比較(bjio)次數(shù)。若次數(shù)。若能利用每趟比較能利用每趟比較(bjio)后的結(jié)果，也就是在找出鍵值最小后的結(jié)果，也就是在找出鍵值最小記錄的同時(shí)，也找出鍵值較小的記錄，則可減少后面的選記錄的同時(shí)，也找出鍵值較小的記錄，則可減少后面的選擇中所用的比較擇中所用的比較(bjio)次數(shù)，從而提高整個(gè)排序過程的效次數(shù)，從而提高整個(gè)排序過程的效率。率。減少減少(jinsho)關(guān)鍵碼間的關(guān)鍵碼間的比較次數(shù)比較次數(shù)查找查找(ch zho)

51、最小值的同時(shí)，找出最小值的同時(shí)，找出較小值較小值8.4 選擇排序選擇排序第71頁/共130頁第七十二頁，共130頁。堆的定義堆的定義(dngy)(dngy)堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子小于或等于其左右孩子(hi zi)(hi zi)結(jié)點(diǎn)的值（稱為小結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子(hi zi)(hi zi)結(jié)點(diǎn)的值（稱為大根堆）。結(jié)點(diǎn)的值（稱為大根堆）。182032364525385040281. 小根堆的根結(jié)點(diǎn)小根堆的根結(jié)點(diǎn)是所有是所有(su

52、yu)結(jié)點(diǎn)結(jié)點(diǎn)的最小者。的最小者。2. 較小結(jié)點(diǎn)靠近根較小結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。結(jié)點(diǎn)，但不絕對。8.4 選擇排序選擇排序第72頁/共130頁第七十三頁，共130頁。堆的定義堆的定義(dngy)(dngy)堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)(ji (ji din)din)的值都小于或等于其左右孩子結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)(ji din)(ji din)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)(ji din)(ji din)的值都的值都大于或等于其左右孩子結(jié)點(diǎn)大于或等于其左右孩子結(jié)點(diǎn)(ji din)(ji din)的值（稱

53、為大的值（稱為大根堆）。根堆）。503845402836322018281. 大根堆的根結(jié)點(diǎn)是所大根堆的根結(jié)點(diǎn)是所有有(suyu)結(jié)點(diǎn)的最大結(jié)點(diǎn)的最大者。者。2. 較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。，但不絕對。8.4 選擇排序選擇排序第73頁/共130頁第七十四頁，共130頁。堆和序列堆和序列(xli)的的關(guān)系關(guān)系將堆用順序存儲(chǔ)結(jié)構(gòu)將堆用順序存儲(chǔ)結(jié)構(gòu)(jigu)來存儲(chǔ)，則堆對應(yīng)一組序列來存儲(chǔ)，則堆對應(yīng)一組序列。5038454028363220182850 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用順序存采用順序存儲(chǔ)儲(chǔ)8.4 選

54、擇選擇(xunz)排序排序第74頁/共130頁第七十五頁，共130頁?；舅枷耄菏紫葘⒋判蚧舅枷耄菏紫葘⒋判?pi x)(pi x)的記錄序列構(gòu)造成一的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，選出了堆中所有記錄的最大者，然后將它個(gè)堆，此時(shí)，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個(gè)記錄。了次小的記錄，以此類推，直到堆中只有一個(gè)記錄。 堆排序堆排序需解決的關(guān)鍵問題需解決的關(guān)鍵問題?如何由一個(gè)無序序列建成一個(gè)堆（即初始建堆）？如何由一個(gè)無序序列建成一個(gè)堆（即初始建堆）？如何處

55、理如何處理(chl)(chl)堆頂記錄？堆頂記錄？如何調(diào)整剩余記錄，成為一個(gè)新堆（即重建堆）？如何調(diào)整剩余記錄，成為一個(gè)新堆（即重建堆）？ 8.4 選擇選擇(xunz)排序排序第75頁/共130頁第七十六頁，共130頁。堆調(diào)整堆調(diào)整(tiozhng)(tiozhng)堆調(diào)整：在一棵完全二叉樹中，根結(jié)點(diǎn)的左右子樹均是堆，堆調(diào)整：在一棵完全二叉樹中，根結(jié)點(diǎn)的左右子樹均是堆，如何調(diào)整根結(jié)點(diǎn)，使整個(gè)完全二叉樹成為如何調(diào)整根結(jié)點(diǎn)，使整個(gè)完全二叉樹成為(chngwi)(chngwi)一個(gè)一個(gè)堆？堆？2836321618253216182536288.4 選擇選擇(xunz)排序排序第76頁/共130頁第七

56、十七頁，共130頁。void sift ( int r , int k, int m )/要篩選要篩選(shixun)結(jié)點(diǎn)的編號為結(jié)點(diǎn)的編號為k，堆中最后一個(gè)結(jié)點(diǎn)的編，堆中最后一個(gè)結(jié)點(diǎn)的編號為號為m i=k; j=2*i; while (j=m ) /篩選篩選(shixun)還沒有進(jìn)行到葉子還沒有進(jìn)行到葉子 if (jm & rjrj) break; else ri rj; i=j; j=2*i; 堆調(diào)整堆調(diào)整(tiozhng)(tiozhng)算法描述：算法描述：8.4 選擇選擇(xunz)排序排序第77頁/共130頁第七十八頁，共130頁。關(guān)鍵問題：如何由一個(gè)無序關(guān)鍵問題：如何由一個(gè)無序(

57、w x)(w x)序列建成一個(gè)堆？序列建成一個(gè)堆？2825163218361632162825183625321628183625283236281618258.4 選擇選擇(xunz)排序排序第78頁/共130頁第七十九頁，共130頁。算法算法(sun f)描述：描述：for (i=n/2; i=1; i-) sift(r, i, n) ; 關(guān)鍵問題：如何由一個(gè)關(guān)鍵問題：如何由一個(gè)(y )(y )無序序列建成一個(gè)無序序列建成一個(gè)(y )(y )堆？堆？最后一個(gè)最后一個(gè)(y )結(jié)點(diǎn)（葉子）的序號是結(jié)點(diǎn)（葉子）的序號是n，則最后一，則最后一個(gè)個(gè)(y )分支結(jié)點(diǎn)即為結(jié)點(diǎn)分支結(jié)點(diǎn)即為結(jié)點(diǎn)n的雙親，其

58、序號是的雙親，其序號是n/2。8.4 選擇排序選擇排序第79頁/共130頁第八十頁，共130頁。關(guān)鍵問題：如何處理關(guān)鍵問題：如何處理(chl)(chl)堆頂記錄？堆頂記錄？32362816182536 28 32 25 18 161 2 3 4 5 6對對應(yīng)應(yīng)交交換換16 28 32 25 18 361 2 3 4 5 6對對應(yīng)應(yīng)3216283618258.4 選擇選擇(xunz)排序排序第80頁/共130頁第八十一頁，共130頁。算法算法(sun f)描述：描述：r1rn-i+1; 關(guān)鍵問題：如何處理關(guān)鍵問題：如何處理(chl)(chl)堆頂記錄？堆頂記錄？解決方法：解決方法：第第 i 次處

59、理次處理(chl)堆頂是將堆頂記錄堆頂是將堆頂記錄r1與序列中第與序列中第n-i+1個(gè)記錄個(gè)記錄rn-i+1交換。交換。8.4 選擇排序選擇排序第81頁/共130頁第八十二頁，共130頁。321628361825關(guān)鍵問題：如何調(diào)整剩余記錄關(guān)鍵問題：如何調(diào)整剩余記錄(jl)(jl)，成為一個(gè)新堆？，成為一個(gè)新堆？163216323618258.4 選擇選擇(xunz)排序排序第82頁/共130頁第八十三頁，共130頁。解決方法：解決方法：第第 i 次調(diào)整次調(diào)整(tiozhng)剩余記錄，此時(shí)，剩余記錄有剩余記錄，此時(shí)，剩余記錄有n-i個(gè)，個(gè)，調(diào)整調(diào)整(tiozhng)根結(jié)點(diǎn)至第根結(jié)點(diǎn)至第n-i個(gè)

60、記錄。個(gè)記錄。關(guān)鍵問題：如何調(diào)整剩余記錄關(guān)鍵問題：如何調(diào)整剩余記錄(jl)(jl)，成為一個(gè)新，成為一個(gè)新堆？堆？算法算法(sun f)描述：描述：sift(r, 1, n-i);8.4 選擇排序選擇排序第83頁/共130頁第八十四頁，共130頁。堆排序算法堆排序算法(sun f)void HeapSort ( int r, int n) for (i=n/2; i=1; i-) /初建堆初建堆 sift(r, i, n) ; for (i=1; in; i+ ) r1rn-i+1; /移走堆頂移走堆頂 sift(r, 1, n-i); /重建重建(zhn jin)堆堆 8.4 選擇選擇(xu