數(shù)據(jù)結(jié)構(gòu)排序技術(shù)

1、第八章 排序技術(shù)本章的基本內(nèi)容是：排序的基本概念插入排序交換排序選擇排序概 述 排序：給定一組記錄的集合r1, r2, , rn，其相應(yīng)的關(guān)鍵碼分別為k1, k2, , kn，排序是將這些記錄排列成順序?yàn)閞s1, rs2, , rsn的一個(gè)序列，使得相應(yīng)的關(guān)鍵碼滿足ks1ks2ksn（稱為升序）或ks1ks2ksn（稱為降序）。正序：待排序序列中的記錄已按關(guān)鍵碼排好序。逆序（反序）：待排序序列中記錄的排列順序與排好序的順序正好相反。排序的基本概念排序算法的穩(wěn)定性：假定在待排序的記錄集中，存在多個(gè)具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，即在原序列中，ki=kj且ri在rj

2、之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。 概 述 排序的基本概念學(xué)號(hào)姓名高數(shù)英語思想品德0001王 軍85880002李 明64920003湯曉影8586687278概 述 排序的基本概念單鍵排序：根據(jù)一個(gè)關(guān)鍵碼進(jìn)行的排序；多鍵排序：根據(jù)多個(gè)關(guān)鍵碼進(jìn)行的排序。學(xué)號(hào)姓名高數(shù)英語思想品德0001王 軍85880002李 明64920003湯曉影8586687278按學(xué)號(hào)排序單鍵排序按成績（高數(shù)英語思想品德）排序多鍵排序概 述 排序的基本概念設(shè)關(guān)鍵碼分別為k1, k2, , km，多鍵排序有兩種方法： 依次對記錄進(jìn)行m次排序，第一次按k1排序，第二次按

3、k2排序，依此類推。這種方法要求各趟排序所用的算法是穩(wěn)定的； 將關(guān)鍵碼k1, k2, , km分別視為字符串依次首尾連接在一起，形成一個(gè)新的字符串，然后，對記錄序列按新形成的字符串排序。多鍵排序單鍵排序排序的分類1. 內(nèi)排序：在排序的整個(gè)過程中，待排序的所有記錄全部被放置在內(nèi)存中2. 外排序：由于待排序的記錄個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另一部分記錄放置在外存上，整個(gè)排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。概 述 排序的基本概念排序的分類1. 基于比較：基本操作關(guān)鍵碼的比較和記錄的移動(dòng)，其最差時(shí)間下限已經(jīng)被證明為（nlog2n）。 2. 不基于比較

4、：根據(jù)關(guān)鍵碼的分布特征。概 述 排序的基本概念基于比較的內(nèi)排序1. 插入排序2. 交換排序3. 選擇排序4. 歸并排序1. 基本操作。內(nèi)排序在排序過程中的基本操作：比較：關(guān)鍵碼之間的比較；移動(dòng)：記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。 2. 輔助存儲(chǔ)空間。輔助存儲(chǔ)空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存放待排序記錄占用的存儲(chǔ)空間之外，執(zhí)行算法所需要的其他存儲(chǔ)空間。3.算法本身的復(fù)雜程度。 排序算法的性能概 述 排序算法的存儲(chǔ)結(jié)構(gòu)概 述 從操作角度看，排序是線性結(jié)構(gòu)的一種操作，待排序記錄可以用順序存儲(chǔ)結(jié)構(gòu)或鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。假定2：將待排序的記錄序列排序?yàn)樯蛐蛄小?int rn+1; /待排序記錄存儲(chǔ)在

5、r1rn，r0留做他用假定1：采用順序存儲(chǔ)結(jié)構(gòu)，關(guān)鍵碼為整型，且記錄只有關(guān)鍵碼一個(gè)數(shù)據(jù)項(xiàng)。插入排序插入排序的主要操作是插入，其基本思想是：每次將一個(gè)待排序的記錄按其關(guān)鍵碼的大小插入到一個(gè)已經(jīng)排好序的有序序列中，直到全部記錄排好序?yàn)橹??；舅枷耄涸诓迦氲?i（i1）個(gè)記錄時(shí)，前面的 i-1個(gè)記錄已經(jīng)排好序。 直接插入排序插入排序有序序列無序序列r1r2ri-1rirnri+1r1r2ri-1rirnri+1基本思想：在插入第 i（i1）個(gè)記錄時(shí)，前面的 i-1個(gè)記錄已經(jīng)排好序。 （1）如何構(gòu)造初始的有序序列？（2）如何查找待插入記錄的插入位置?直接插入排序插入排序需解決的關(guān)鍵問題?直接插入排序過

6、程示例 r 0 1 2 3 4 5 6211825221025*212125插入排序i = 218221025*25i = 318221025*2225222110252115102525*2521151025*252118151018181025*i = 418i = 61825*i = 5r0的作用?暫存單元監(jiān)視哨解決方法：將第1個(gè)記錄看成是初始有序表，然后從第2個(gè)記錄起依次插入到這個(gè)有序表中，直到將第n個(gè)記錄插入。插入排序關(guān)鍵問題(1)如何構(gòu)造初始的有序序列？算法描述：for (i=2; i=n; i+) 插入第i個(gè)記錄，即第i趟直接插入排序；關(guān)鍵問題(2)如何查找待插入記錄的插入位置?

7、解決方法：在i-1個(gè)記錄的有序區(qū)r1 ri-1中插入記錄ri，首先順序查找ri的正確插入位置，然后將ri插入到相應(yīng)位置。r0有兩個(gè)作用：1. 進(jìn)入循環(huán)之前暫存了ri的值，使得不致于因記錄的后移而丟失ri的內(nèi)容；2. 在查找插入位置的循環(huán)中充當(dāng)哨兵。插入排序算法描述：r0=ri; j=i-1; while (r0rj) rj+1=rj; j-;void insertSort (int r , int n) for (i=2; i=n; i+) r0=ri; j=i-1; while (r0=ri-1，內(nèi)層循環(huán)會(huì)出現(xiàn)什么情況?直接插入排序算法性能分析最好情況下（正序）： 插入排序12345時(shí)間復(fù)雜

8、度為O(n)。比較次數(shù)：n-1移動(dòng)次數(shù)：2(n-1) 123451234512345123452345直接插入排序算法性能分析插入排序最好情況下（正序）： 比較次數(shù)：n-1移動(dòng)次數(shù)：2(n-1) 最壞情況下（逆序或反序）： 時(shí)間復(fù)雜度為O(n2)。54321453213452123451123454321比較次數(shù)：移動(dòng)次數(shù)：2)1)(2(2-+=nnini2)1)(4(1-+=+nnin2=i）（時(shí)間復(fù)雜度為O(n)。平均情況下（隨機(jī)排列）： 直接插入排序算法性能分析插入排序時(shí)間復(fù)雜度為O(n2)。比較次數(shù)：移動(dòng)次數(shù)：4)1)(4(-+=nnn2=i4)1)(2(2-+=nnnii2（21+i

9、）空間性能：需要一個(gè)記錄的輔助空間。直接插入排序算法是一種穩(wěn)定的排序算法。直接插入排序算法性能分析插入排序直接插入排序算法簡單、容易實(shí)現(xiàn)，適用于待排序記錄基本有序或待排序記錄較小時(shí)。當(dāng)待排序的記錄個(gè)數(shù)較多時(shí)，大量的比較和移動(dòng)操作使直接插入排序算法的效率降低。插入排序如何改進(jìn)直接插入排序?注意到，在插入第 i（i1）個(gè)記錄時(shí)，前面的 i-1 個(gè)記錄已經(jīng)排好序，則在尋找插入位置時(shí)，可以用折半查找來代替順序查找，從而較少比較次數(shù)。請同學(xué)們寫出這個(gè)改進(jìn)的直接插入排序算法，并分析時(shí)間性能。希爾排序改進(jìn)的著眼點(diǎn)：（1）若待排序記錄按關(guān)鍵碼基本有序時(shí)，直接插入排序的效率可以大大提高；（2）由于直接插入排序算

10、法簡單，則在待排序記錄數(shù)量n較小時(shí)效率也很高。 插入排序（1）應(yīng)如何分割待排序記錄，才能保證整個(gè)序列逐步向基本有序發(fā)展？（2）子序列內(nèi)如何進(jìn)行直接插入排序？插入排序需解決的關(guān)鍵問題?基本思想：將整個(gè)待排序記錄分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，對全體記錄進(jìn)行直接插入排序。希爾排序基本有序：接近正序，例如1, 2, 8, 4, 5, 6, 7, 3, 9；局部有序：部分有序，例如6, 7, 8, 9, 1, 2, 3, 4, 5。局部有序不能提高直接插入排序算法的時(shí)間性能。 插入排序希爾排序分割待排序記錄的目的?1. 減少待排序記錄個(gè)數(shù)；2. 使整個(gè)

11、序列向基本有序發(fā)展。 子序列的構(gòu)成不能是簡單地“逐段分割”，而是將相距某個(gè)“增量”的記錄組成一個(gè)子序列。 啟示?希爾插入排序過程示例 1 2 3 4 5 6 7 8 94021254925*16初始序列插入排序300813d = 44021254925*16300813252125*300849131640d = 21325210825*16304940252125*300813164049d = 10825211325*16304049082513162125*403049解決方法：將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。增量應(yīng)如何??？希爾最早提出的方法是d1=n/2，di+1=di/2。關(guān)

12、鍵問題(1)應(yīng)如何分割待排序記錄？插入排序算法描述：for (d=n/2; d=1; d=d/2) 以d為增量，進(jìn)行組內(nèi)直接插入排序；解決方法：在插入記錄ri時(shí)，自ri-d起往前跳躍式（跳躍幅度為d）搜索待插入位置，并且r0只是暫存單元，不是哨兵。當(dāng)搜索位置0，表示插入位置已找到。在搜索過程中，記錄后移也是跳躍d個(gè)位置。在整個(gè)序列中，前d個(gè)記錄分別是d個(gè)子序列中的第一個(gè)記錄，所以從第d+1個(gè)記錄開始進(jìn)行插入。插入排序關(guān)鍵問題(2)子序列內(nèi)如何進(jìn)行直接插入排序？算法描述：for (i=d+1; i0 & r0rj) rj+d=rj; /記錄后移d個(gè)位置 j=j-d; /比較同一子序列的前一個(gè)記錄

13、 rj+d=r0; 插入排序關(guān)鍵問題(2)子序列內(nèi)如何進(jìn)行直接插入排序？希爾排序算法的時(shí)間性能希爾排序算法的時(shí)間性能是所取增量的函數(shù)，而到目前為止尚未有人求得一種最好的增量序列。研究表明，希爾排序的時(shí)間性能在O(n2)和O(nlog2n)之間。當(dāng)n在某個(gè)特定范圍內(nèi)，希爾排序所需的比較次數(shù)和記錄的移動(dòng)次數(shù)約為O(n1.3 ) 。 插入排序希爾排序開始時(shí)增量較大，每個(gè)子序列中的記錄個(gè)數(shù)較少，從而排序速度較快；當(dāng)增量較小時(shí)，雖然每個(gè)子序列中記錄個(gè)數(shù)較多，但整個(gè)序列已基本有序，排序速度也較快。 課堂練習(xí)：1. 欲將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按

14、字母升序重排，則初始步長為4的希爾排序一趟的結(jié)果是？答：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后：2. 以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，分別寫出執(zhí)行以下算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)，并說明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實(shí)現(xiàn)？ 直接插入排序 希爾排序（取dk=5,3,1）P,Q,R,A,D,H,C,F,M,S,X ,Y答：顯然，直接插入排序方法易于在鏈表上實(shí)現(xiàn)；但希爾排序方法因?yàn)槭前丛隽窟x擇記錄，不易于在鏈表上實(shí)現(xiàn)。 交換排序的主要

15、操作是交換，其主要思想是：在待排序列中選兩個(gè)記錄，將它們的關(guān)鍵碼相比較，如果反序（即排列順序與排序后的次序正好相反），則交換它們的存儲(chǔ)位置。 交換排序反序則 交換rirj起泡排序基本思想：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。 rj rj+1 ri+1 rn-1 rn 無序區(qū) 有序區(qū) 1ji-1 已經(jīng)位于最終位置反序則交換交換排序05981269385381起泡排序過程示例 交換排序059812693853810598126938538105981269385381交換排序Flag=1;for(i=1;in&flag;i+) flag=0; for(j=1;jrj+

16、1)flag=1;ri-rj+1因?yàn)榕判虻倪^程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進(jìn)行過交換，就說明序列有序，因此要在排序過程中設(shè)置一個(gè)標(biāo)志flag判斷元素是否進(jìn)行過交換。從而減少不必要的比較。起泡排序的時(shí)間性能分析最好情況（正序）：交換排序比較次數(shù)：n-1移動(dòng)次數(shù)：0 12345時(shí)間復(fù)雜度為O(n)。12345最壞情況（反序）：起泡排序的時(shí)間性能分析最好情況（正序）：交換排序比較次數(shù)：n-1移動(dòng)次數(shù)：0 54321時(shí)間復(fù)雜度為O(n)；時(shí)間復(fù)雜度為O(n2)。43215321452134512345比較次數(shù)：移動(dòng)次數(shù)：2)1(1-=nn(n-i)n-1i2)1(1-=n3n3(

17、n-i)n-1i平均情況：時(shí)間復(fù)雜度為O(n2)?？焖倥判虻幕舅枷胧紫冗x一個(gè)軸值（即比較的基準(zhǔn)），通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，前一部分記錄的關(guān)鍵碼均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等于軸值，然后分別對這兩部分重復(fù)上述方法，直到整個(gè)序列有序。交換排序如何選擇軸值？如何實(shí)現(xiàn)分割（稱一次劃分）？如何處理分割得到的兩個(gè)待排序子序列？如何判別快速排序的結(jié)束？需解決的關(guān)鍵問題?選擇軸值的方法：1.使用第一個(gè)記錄的關(guān)鍵碼；2.選取序列中間記錄的關(guān)鍵碼；3.比較序列中第一個(gè)記錄、最后一個(gè)記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個(gè)記錄的位置；4.隨機(jī)選取軸值。交換

18、排序關(guān)鍵問題：如何選擇軸值？選取不同軸值的后果：決定兩個(gè)子序列的長度，子序列的長度最好相等。13652750384955ji1338652750495513652750493855交換排序關(guān)鍵問題：如何實(shí)現(xiàn)一次劃分？jjiiijijjj解決方法：設(shè)待劃分的序列是rs rt，設(shè)參數(shù)i，j分別指向子序列左、右兩端的下標(biāo)s和t，令rs為軸值，（1）j從后向前掃描，直到rjri，將rj移動(dòng)到ri的位置，使關(guān)鍵碼?。ㄍS值相比）的記錄移動(dòng)到前面去；（2）i從前向后掃描，直到rirj，將ri移動(dòng)到rj的位置，使關(guān)鍵碼大（同軸值比較）的記錄移動(dòng)到后面去；（3）重復(fù)上述過程，直到i=j。交換排序關(guān)鍵問題：如何

19、實(shí)現(xiàn)一次劃分？交換排序關(guān)鍵問題：如何實(shí)現(xiàn)一次劃分？算法描述：int Partition(int r , int first, int end) i=first; j=end; /初始化 while (ij) while (ij & ri= rj) j-； /右側(cè)掃描 if (ij) rirj; i+; /將較小記錄交換到前面 while (ij & ri= rj) i+； /左側(cè)掃描 if (ij) rjri; j-; /將較大記錄交換到后面 retutn i; /i為軸值記錄的最終位置解決方法：對分割得到的兩個(gè)子序列遞歸地執(zhí)行快速排序。交換排序關(guān)鍵問題：如何處理分割得到的兩個(gè)待排序子序列？

20、1327386550495513275038495565ijij算法描述：交換排序關(guān)鍵問題：如何處理分割得到的兩個(gè)待排序子序列？ void QuickSort (int r , int first, int end ) pivotpos = Partition (r, first, end ); /一次劃分 QuickSort (r, first, pivotpos-1); /對前一個(gè)子序列進(jìn)行快速排序 QuickSort (r, pivotpos+1, end ); /對后一個(gè)子序列進(jìn)行快速排序解決方法：若待排序列中只有一個(gè)記錄，顯然已有序，否則進(jìn)行一次劃分后，再分別對分割所得的兩個(gè)子序列進(jìn)

21、行快速排序（即遞歸處理）。 交換排序關(guān)鍵問題：如何判別快速排序的結(jié)束？ void QuickSort (int r , int first, int end )/在序列 firstend中遞歸地進(jìn)行快速排序 if (first end) pivotpos = Partition (r, first, end ); QuickSort (r, first, pivotpos-1); QuickSort (r, pivotpos+1, end ); 算法描述：交換排序關(guān)鍵問題：如何判別快速排序的結(jié)束？ 交換排序例：38, 27, 55, 50, 13, 49, 65的快速排序遞歸樹如下：38135

22、055496527快速排序的遞歸執(zhí)行過程可以用遞歸樹描述?？焖倥判虻臅r(shí)間性能分析快速排序的時(shí)間性能分析交換排序快速排序的時(shí)間性能快速排序遞歸的深度每次劃分軸值的選取最好情況：每一次劃分對一個(gè)記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)?？焖倥判虻臅r(shí)間性能分析交換排序T(n)2T(n/2)n 2(2T(n/4)n/2)n4T(n/4)2n 4(2T(n/8)n/4)2n8T(n/8)3n nT(1)nlog2nO(nlog2n)最壞情況：每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列（另一個(gè)子序列為空），為 O(n2)。最好情況：每一次劃分對一個(gè)記錄定位后，該記錄的左

23、側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)?？焖倥判虻臅r(shí)間性能分析交換排序平均情況：為O(nlog2n)。)()1(21211nOnninni=-=-=）（選擇排序的主要操作是選擇，其主要思想是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，添加到有序序列中。 選擇排序有序序列r1r2ri-1rirnrk無序序列rnri+1r1r2ri-1riri交換最小記錄簡單選擇排序基本思想：第i 趟在n-i+1（i=1,2,n-1）個(gè)記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第i個(gè)記錄。 選擇排序需解決的關(guān)鍵問題?如何在待排序序列中選出關(guān)鍵碼最小的記錄？如何確定待排序序列中關(guān)鍵碼最小的記錄在有序

24、序列中的位置？ 簡單選擇排序示例0821i = 2最小者 08交換21,08最小者 16交換25,16最小者 21交換49,212128i = 12516490808i = 32108284921選擇排序28491625161625i = 4最小者 25交換25,28i = 5最小者 28不交換選擇排序簡單選擇排序示例492108281625254921081628252849210816282528無序區(qū)只有一個(gè)記錄解決方法：設(shè)置一個(gè)整型變量index，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。 選擇排序關(guān)鍵問題：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？212825164908indexi

25、ndexindex08算法描述：index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j;解決方法：設(shè)置一個(gè)整型變量index，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。 關(guān)鍵問題：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？解決方法：第i趟簡單選擇排序的待排序區(qū)間是ri rn，則ri是無序區(qū)第一個(gè)記錄，所以，將index所記載的關(guān)鍵碼最小的記錄與ri交換。選擇排序關(guān)鍵問題：如何確定最小記錄的最終位置？算法描述： if (index!=i) ririndex; void selectSort ( int r , int n) for ( i=1; i

26、n; i+) index=i; for (j=i+1; j=n; j+) if (rjrindex) index=j; if (index!=i) ririndex; 簡單選擇排序算法選擇排序簡單選擇排序算法的性能分析移動(dòng)次數(shù)：最好情況（正序）：0次選擇排序12345123451234512345123451234最壞情況：3(n-1)次簡單選擇排序算法的性能分析移動(dòng)次數(shù)：最好情況（正序）：0次選擇排序空間性能：需一個(gè)輔助空間。穩(wěn)定性：是一種穩(wěn)定的排序算法。45231152341253412354123451234比較次數(shù)：)()1(21211nOnninni=-=-=）（簡單選擇排序的時(shí)間復(fù)

27、雜度為O(n2)。堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。選擇排序182032364525385040281. 小根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最小者。2. 較小結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。選擇排序503845402836322018281. 大根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最大者。2. 較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。堆和序列的關(guān)系選擇排序

28、將堆用順序存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)，則堆對應(yīng)一組序列。5038454028363220182850 38 45 32 36 40 28 20 18 281 2 3 4 5 6 7 8 9 10采用順序存儲(chǔ)基本思想：首先將待排序的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個(gè)記錄。 選擇排序堆排序需解決的關(guān)鍵問題?如何由一個(gè)無序序列建成一個(gè)堆（即初始建堆）？如何處理堆頂記錄？如何調(diào)整剩余記錄，成為一個(gè)新堆（即重建堆）？ 堆調(diào)整堆調(diào)整：在一棵完全二叉樹中，根結(jié)點(diǎn)的左右子樹均是堆，如何調(diào)整根結(jié)點(diǎn)，使整個(gè)完

29、全二叉樹成為一個(gè)堆？選擇排序283632161825321618253628void sift ( int r , int k, int m )/要篩選結(jié)點(diǎn)的編號(hào)為k，堆中最后一個(gè)結(jié)點(diǎn)的編號(hào)為m i=k; j=2*i; while (j=m ) /篩選還沒有進(jìn)行到葉子 if (jm & rjrj) break; else ri rj; i=j; j=2*i; 選擇排序堆調(diào)整算法描述：選擇排序關(guān)鍵問題：如何由一個(gè)無序序列建成一個(gè)堆？282516321836163216282518362532162818362528323628161825算法描述：for (i=n/2; i=1; i-) sif

30、t(r, i, n) ; 選擇排序關(guān)鍵問題：如何由一個(gè)無序序列建成一個(gè)堆？最后一個(gè)結(jié)點(diǎn)（葉子）的序號(hào)是n，則最后一個(gè)分支結(jié)點(diǎn)即為結(jié)點(diǎn)n的雙親，其序號(hào)是n/2。選擇排序關(guān)鍵問題：如何處理堆頂記錄？32362816182536 28 32 25 18 161 2 3 4 5 6對應(yīng)交換16 28 32 25 18 361 2 3 4 5 6對應(yīng)321628361825算法描述：r1rn-i+1; 選擇排序關(guān)鍵問題：如何處理堆頂記錄？解決方法：第 i 次處理堆頂是將堆頂記錄r1與序列中第n-i+1個(gè)記錄rn-i+1交換。321628361825選擇排序關(guān)鍵問題：如何調(diào)整剩余記錄，成為一個(gè)新堆？162

31、81632361825283236181625解決方法：第 i 次調(diào)整剩余記錄，此時(shí)，剩余記錄有n-i個(gè)，調(diào)整根結(jié)點(diǎn)至第n-i個(gè)記錄。選擇排序關(guān)鍵問題：如何調(diào)整剩余記錄，成為一個(gè)新堆？算法描述：sift(r, 1, n-i);堆排序算法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); /重建堆 選擇排序堆排序算法的性能分析第1個(gè)for循環(huán)是初始建堆，需要O(n)時(shí)間；第2個(gè)for循環(huán)是輸出堆頂重建堆

32、，共需要取n-1次堆頂記錄，第 i 次取堆頂記錄重建堆需要O(log2i)時(shí)間，需要O(nlog2n)時(shí)間；因此整個(gè)時(shí)間復(fù)雜度為O(nlog2n)，這是堆排序的最好、最壞和平均的時(shí)間代價(jià)。選擇排序歸并排序歸并排序的主要操作是歸并，其主要思想是：將若干有序序列逐步歸并，最終得到一個(gè)有序序列。 歸并排序歸并：將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列的過程。 基本思想：將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長度為1的有序序列，然后進(jìn)行兩兩歸并，得到n/2個(gè)長度為2的有序序列，再進(jìn)行兩兩歸并，得到n/4個(gè)長度為4的有序序列，直至得到一個(gè)長度為n的有序序列為止。二路歸并排序歸并排序需解決的關(guān)鍵問題

33、?如何將兩個(gè)有序序列合成一個(gè)有序序列？怎樣完成一趟歸并？如何控制二路歸并的結(jié)束？60 20 31 5 44 55 65void Merge (int r , int r1 , int s, int m, int t ) i=s; j=m+1; k=s; while (i=m & j=t) if (ri=rj) r1k+=ri+; else r1k+=rj+; if (i=m) while (i=m) /收尾處理 r1k+=ri+; /前一個(gè)子序列 else while (j=t) r1k+=rj+; /后一個(gè)子序列 歸并排序關(guān)鍵問題：如何將兩個(gè)有序序列合成一個(gè)有序序列？算法描述：void Me

34、rgePass (int r , int r1 , int n, int h) i=1; while (in-2h+1) /情況1 Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; if (in-h+1) Merge (r, r1, i, i+h-1, n); /情況2 else for (k=i; k=n; k+) /情況3 r1k=rk;一趟歸并排序算法歸并排序算法描述：void MergeSort (int r , int r1 , int n ) h=1; while (hn) MergePass (r, r1, n, h); h=2*h; MergePass (r1, r, n, h); h=2*h; 歸并排序關(guān)鍵問題：如何控制二路