哈工大數(shù)據(jù)結(jié)構(gòu)10

1、第第10章章 排序排序10.1 概述概述1.1.排序（排序（SortingSorting） 將數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵將數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序（遞增或遞減）的序列的過程稱為排序。字有序（遞增或遞減）的序列的過程稱為排序。2.2. 排序過程中的兩種基本操作排序過程中的兩種基本操作（1 1）比較兩個關(guān)鍵字值的大小。）比較兩個關(guān)鍵字值的大小。（2 2）根據(jù)比較結(jié)果，移動記錄的位置。）根據(jù)比較結(jié)果，移動記錄的位置。3.3.對關(guān)鍵字排序的三個原則對關(guān)鍵字排序的三個原則 （1 1）關(guān)鍵字值為數(shù)值型的，則按鍵值大小為依據(jù)。）關(guān)鍵字值為數(shù)值型的，則按

2、鍵值大小為依據(jù)。 （2 2）關(guān)鍵字值為）關(guān)鍵字值為ASCIIASCII碼，則按鍵值的內(nèi)碼編排順序?yàn)橐罁?jù)。碼，則按鍵值的內(nèi)碼編排順序?yàn)橐罁?jù)。 （3 3）關(guān)鍵字值為漢字字符串類型，則大多以漢字拼音的字典次）關(guān)鍵字值為漢字字符串類型，則大多以漢字拼音的字典次序?yàn)橐罁?jù)。序?yàn)橐罁?jù)。4.4.排序方法的穩(wěn)定和不穩(wěn)定排序方法的穩(wěn)定和不穩(wěn)定 若對任意的數(shù)據(jù)元素序列，使用某個排序方法按關(guān)鍵字進(jìn)若對任意的數(shù)據(jù)元素序列，使用某個排序方法按關(guān)鍵字進(jìn)行排序，對原先具有相同鍵值元素間的位置關(guān)系，若排序前與行排序，對原先具有相同鍵值元素間的位置關(guān)系，若排序前與排序后保持一致，稱此排序方法是穩(wěn)定的；反之，則稱為不穩(wěn)排序后保持一

3、致，稱此排序方法是穩(wěn)定的；反之，則稱為不穩(wěn)定的。定的。例：對數(shù)據(jù)鍵值為：例：對數(shù)據(jù)鍵值為：5 5，3 3，8 8，3 3，6 6，6 6，排序。，排序。 若排序后的序列為：若排序后的序列為：3 3，3 3，5 5，6 6，6 6，8 8 其相同鍵值的元素位置依舊是其相同鍵值的元素位置依舊是 3 3 在在 3 3 前，前，6 6 在在 6 6 前，前，與排序前保持一致，則這種排序法是穩(wěn)定的。與排序前保持一致，則這種排序法是穩(wěn)定的。 若排序后的序列為：若排序后的序列為：3 3，3 3，5 5，6 6，6 6，8 8則這種排序法是不穩(wěn)定的。則這種排序法是不穩(wěn)定的。5 5待排序記錄的三種存儲方式待排序

4、記錄的三種存儲方式 （1 1）待排序記錄存放在地址連續(xù)的一組存儲單元上。）待排序記錄存放在地址連續(xù)的一組存儲單元上。 （2 2）待排序記錄存放在靜態(tài)鏈表中。）待排序記錄存放在靜態(tài)鏈表中。 （3 3）待排序記錄存放在一組地址連續(xù)的存儲單元，同時另設(shè)）待排序記錄存放在一組地址連續(xù)的存儲單元，同時另設(shè)一個指示各個記錄存儲位置的地址向量，在排序過程中不移動一個指示各個記錄存儲位置的地址向量，在排序過程中不移動記錄本身，而移動地址向量中這些記錄的記錄本身，而移動地址向量中這些記錄的“地址地址”，在排序結(jié)，在排序結(jié)束后，再按照地址向量中的值調(diào)整記錄的存儲位置。束后，再按照地址向量中的值調(diào)整記錄的存儲位置。

5、 6 6內(nèi)排序內(nèi)排序 整個排序過程都在內(nèi)存進(jìn)行的排序稱為內(nèi)排序。整個排序過程都在內(nèi)存進(jìn)行的排序稱為內(nèi)排序。7 7外排序外排序 待排序的數(shù)據(jù)元素量大，以致內(nèi)存一次不能容納全部記錄，待排序的數(shù)據(jù)元素量大，以致內(nèi)存一次不能容納全部記錄，在排序過程中需要對外存進(jìn)行訪問的排序稱為外排序。在排序過程中需要對外存進(jìn)行訪問的排序稱為外排序。本章只討論內(nèi)排序。本章只討論內(nèi)排序。10.2 插入排序插入排序取要插入的元素，直接插在一個有序序列的合適位置。取要插入的元素，直接插在一個有序序列的合適位置。1.1.直接插入排序直接插入排序012362410612345基本思想：基本思想： 直接插入排序是一種最簡單的排序方

6、法，它的基本操直接插入排序是一種最簡單的排序方法，它的基本操作是將一個記錄插到已排序好的有序表中，從而得到一個作是將一個記錄插到已排序好的有序表中，從而得到一個新的，記錄數(shù)增新的，記錄數(shù)增 1 1 的有序表。的有序表。 整個排序過程為整個排序過程為 n-1 趟插入，即先將序列中第趟插入，即先將序列中第 1 個記個記錄看成是一個有序子序列，然后從第錄看成是一個有序子序列，然后從第 2 個記錄開始，逐個個記錄開始，逐個進(jìn)行插入，直至整個序列有序進(jìn)行插入，直至整個序列有序。排序過程：排序過程：將第一個元素將第一個元素 r1 作為已排序有序序列；作為已排序有序序列；其他元素其他元素r2,r3,r4,r

7、5,.rn作為未排序序列；作為未排序序列；循環(huán)：循環(huán)：從未排序序列中依次取一個元素；（循環(huán)從從未排序序列中依次取一個元素；（循環(huán)從i=2,3,4,5.）取一個元素后進(jìn)行判斷：取一個元素后進(jìn)行判斷：如果所取元素小于當(dāng)前有序序列的序尾，則：如果所取元素小于當(dāng)前有序序列的序尾，則：（1 1）將所取）將所取元素賦值給元素賦值給r0， r0 當(dāng)作哨兵。當(dāng)作哨兵。（2 2）循環(huán)：）循環(huán)： 在當(dāng)前有序序列中尋找自己的位置，進(jìn)行插入：在當(dāng)前有序序列中尋找自己的位置，進(jìn)行插入： 從當(dāng)前有序序列的序尾開始，倒著往前，將哨兵與相應(yīng)元素逐個比較：從當(dāng)前有序序列的序尾開始，倒著往前，將哨兵與相應(yīng)元素逐個比較： 哨兵比當(dāng)

8、前元素小，當(dāng)前元素就往后移一個位置；再往前比，若哨哨兵比當(dāng)前元素小，當(dāng)前元素就往后移一個位置；再往前比，若哨 兵比當(dāng)前元素還小，當(dāng)前元素再往后移一個位置兵比當(dāng)前元素還小，當(dāng)前元素再往后移一個位置 . .直到哨兵大于直到哨兵大于 等于當(dāng)前元素，循環(huán)結(jié)束，將哨兵插入到當(dāng)前元素的后面。等于當(dāng)前元素，循環(huán)結(jié)束，將哨兵插入到當(dāng)前元素的后面。如果如果所取元素大于等于有序序列的序尾，則保持原存儲位置不變。所取元素大于等于有序序列的序尾，則保持原存儲位置不變。e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排

9、序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序012362410612345362424ie.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453624ie.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之

10、中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453624i24e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453610i2410e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的

11、元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453610i24e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453610i24e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)

12、組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106123453610i2410e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序01236241061234536246i106e.g: 36、24、10、6、

13、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序01236241061234536246i10e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序01236241061234536246i10

14、e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序01236241061234536246i10e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624

15、1061234536246i106e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106345362412i1061212e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1

16、、直接插入排序、直接插入排序0123624106345362412i10612e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為 1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106345362412i10612e.g: 36、24、10、6、12存放在存放在 r 數(shù)組的下標(biāo)為數(shù)組的下標(biāo)為 1 至至 5 的元素之中，用直接插入法將的元素之中，用直接插入法將 其排序。結(jié)果仍保存在下標(biāo)為其排序。結(jié)果仍保存在下標(biāo)為

17、1 至至 5 的元素之中。的元素之中。1、直接插入排序、直接插入排序0123624106345362412i1061212算法：算法：void Insertsort() for( i=2;i=L;i+ ) / 依次插入依次插入r2,r3,rn if ( ri.keyri-1.key ) r0=ri; / 置監(jiān)視哨置監(jiān)視哨 j=i-1; while(r0.key275653275，在后半?yún)^(qū)繼續(xù)找；，在后半?yún)^(qū)繼續(xù)找； （2 2）再與后半?yún)^(qū)中間位置的關(guān)鍵字比較，）再與后半?yún)^(qū)中間位置的關(guān)鍵字比較，653512653512，再，再繼續(xù)在后半?yún)^(qū)找；繼續(xù)在后半?yún)^(qū)找； （3 3）再與后半?yún)^(qū)中間位置的關(guān)鍵字比較

18、，）再與后半?yún)^(qū)中間位置的關(guān)鍵字比較，653897653897，經(jīng)，經(jīng)三次比較找到插入位置，然后插入三次比較找到插入位置，然后插入653653。算法：算法：void BInsSort() for(i=2;i=n;i+) r0=ri; / 將將ri 暫存到暫存到r0 while(lowhigh時，循環(huán)結(jié)束，大致插入位置已確定。時，循環(huán)結(jié)束，大致插入位置已確定。 m=(low+high)/2; / 折半折半 if(r0.key=high+1;- -j) rj+1=rj; / 記錄后移，直到空出記錄后移，直到空出 rhigh+1為止為止 rhigh+1=r0; / 插入插入 二分插入排序輔助空間和直接

19、插入相同，為二分插入排序輔助空間和直接插入相同，為O (1 1) 。 從時間上比較，二分插入僅減少了比較次數(shù)，而記錄從時間上比較，二分插入僅減少了比較次數(shù)，而記錄的移動次數(shù)不變，時間復(fù)雜度仍為的移動次數(shù)不變，時間復(fù)雜度仍為O(n(n2 2) )。 二分插入排序是穩(wěn)定的排序方法。二分插入排序是穩(wěn)定的排序方法。3.3.希爾排序希爾排序(Shells Sort) 希爾排序又稱希爾排序又稱“縮小增量排序縮小增量排序”，它也是一種插入排序方法，它也是一種插入排序方法，但在時間上較前兩種排序方法有較大的改進(jìn)。但在時間上較前兩種排序方法有較大的改進(jìn)?；舅枷耄夯舅枷耄?先將先將整個待排序記錄序列整個待排序

20、記錄序列分割成若干分割成若干子序列子序列分別進(jìn)行分別進(jìn)行直接直接插入排序插入排序，待整個序列中的記錄，待整個序列中的記錄“基本有序時基本有序時”，再對全體記錄，再對全體記錄進(jìn)行一次直接插入排序。進(jìn)行一次直接插入排序。 特點(diǎn)：特點(diǎn)： 子序列不是簡單的逐段分割，而是將相隔某個子序列不是簡單的逐段分割，而是將相隔某個“增量增量”的記錄的記錄組成一個子序列，組成一個子序列， 所以關(guān)鍵字較小的記錄不是一步一步地前移，所以關(guān)鍵字較小的記錄不是一步一步地前移，而是跳躍式前移，從而使得在進(jìn)行最后一趟增量為而是跳躍式前移，從而使得在進(jìn)行最后一趟增量為 1 的插入排序的插入排序時，序列已基本有序，只要做少量比較和

21、移動即可完成排序，時時，序列已基本有序，只要做少量比較和移動即可完成排序，時間復(fù)雜度較低。間復(fù)雜度較低。排序過程：排序過程： 先取一個正整數(shù)先取一個正整數(shù) d1n d1n ，把所有相隔把所有相隔 d1 d1 的記錄放一組，的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后取組內(nèi)進(jìn)行直接插入排序；然后取 d2d1d20) for ( i=gap+1; i0) if ( rjrj+gap ) / 對子序列作直接插入排序?qū)ψ有蛄凶髦苯硬迦肱判?x=rj; rj=rj+gap; rj+gap=x; j=j-gap; else j=0; gap=gap/2; / 每次減半每次減半,直至步長為直至步長為 1 效率分

22、析：效率分析： 希爾排序可提高排序速度：希爾排序可提高排序速度： 分組后分組后 n n 值減小，值減小，nn更小。更小。在大量實(shí)驗(yàn)基礎(chǔ)上可推出：當(dāng)在大量實(shí)驗(yàn)基礎(chǔ)上可推出：當(dāng) n n 在某在某 個特定范圍內(nèi)希爾排序所需的比較和移動次數(shù)約為個特定范圍內(nèi)希爾排序所需的比較和移動次數(shù)約為 n n1.3 1.3 , , 所以其所以其平均時平均時 間復(fù)雜度約為間復(fù)雜度約為O( nO( n1.31.3) )。其其輔助空間為輔助空間為O(1)O(1)。 關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為 1 1 的插入排的插入排 序時，序列已基本有序。序時，序列已

23、基本有序。 希爾排序?yàn)椴环€(wěn)定排序。希爾排序?yàn)椴环€(wěn)定排序。 增量序列取法：增量序列取法： 沒有除沒有除1 1以外的公因子。以外的公因子。 最后一個增量值必須為最后一個增量值必須為1 1。10.3 快速排序法快速排序法1.1.冒泡排序冒泡排序基本思想：基本思想： 冒泡法也稱沉底法，每相鄰兩個記錄關(guān)鍵字比大小，大的冒泡法也稱沉底法，每相鄰兩個記錄關(guān)鍵字比大小，大的記錄往下沉（即較小的往上?。?。每一趟把最后一個下沉的位記錄往下沉（即較小的往上?。Ｃ恳惶税炎詈笠粋€下沉的位置記下，下一趟只需檢查比較到此為止；到所有記錄都不發(fā)生置記下，下一趟只需檢查比較到此為止；到所有記錄都不發(fā)生下沉?xí)r，整個過程結(jié)束。下

24、沉?xí)r，整個過程結(jié)束。排序過程：排序過程： 將第一個記錄的關(guān)鍵字與第二個記錄的關(guān)鍵字進(jìn)行比將第一個記錄的關(guān)鍵字與第二個記錄的關(guān)鍵字進(jìn)行比較，若為逆序較，若為逆序r1.keyr2.keyr1.keyr2.key，則交換；然后比較第二則交換；然后比較第二個記錄與第三個記錄；依次類推，直至個記錄與第三個記錄；依次類推，直至用用n-1n-1次比較完成次比較完成 n n個記錄個記錄的的第一趟冒泡排序第一趟冒泡排序，結(jié)果關(guān)鍵字，結(jié)果關(guān)鍵字最大最大的記錄被安置的記錄被安置在最后一個記錄上。在最后一個記錄上。 對前對前n-1n-1個記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字個記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次次大

25、大的記錄被安置在第的記錄被安置在第n-1n-1個記錄位置。個記錄位置。 重復(fù)上述過程，直到重復(fù)上述過程，直到“在一趟排序過程中沒有可進(jìn)行在一趟排序過程中沒有可進(jìn)行記錄交換的操作記錄交換的操作”為止。為止。例例49 38 65 97 76 13 27 30 初始關(guān)鍵字初始關(guān)鍵字38 49 65 76 13 27 30 97 第一趟第一趟38 49 65 13 27 30 76 第二趟第二趟38 49 13 27 30 65 第三趟第三趟38 13 27 30 49 第四趟第四趟13 27 30 38 第五趟第五趟384976971397279730971376767627301365276530

26、651313494930492738273830381 2 3 4 5 6 7 8算法：算法：void Bubblesort() for(i=1;iL;i+) for(j=1;jRj+1.key ) / / 大則交換大則交換 R0.key=Rj.key; Rj.key=Rj+1.key; Rj+1.key=R0.key; 效率分析：效率分析： 空間效率：僅用了一個輔助單元，空間效率：僅用了一個輔助單元，空間復(fù)雜度為空間復(fù)雜度為O O（1 1）。）。 時間效率：總共要進(jìn)行時間效率：總共要進(jìn)行n-1n-1趟冒泡，對趟冒泡，對j j個記錄的表進(jìn)行一趟冒個記錄的表進(jìn)行一趟冒泡需要泡需要j-1j-1次關(guān)

27、鍵字的比較。次關(guān)鍵字的比較。 移動次數(shù)：移動次數(shù)： 最好情況下：待排序列已有序，不需移動。最好情況下：待排序列已有序，不需移動。 最壞情況下：每次比較后均要進(jìn)行三次移動。最壞情況下：每次比較后均要進(jìn)行三次移動。 移動次數(shù)移動次數(shù)= = 時間復(fù)雜度為時間復(fù)雜度為: : O O（n n2 2） 冒泡排序是一種穩(wěn)定排序。冒泡排序是一種穩(wěn)定排序。) 1(21) 1(2nnjnj總比較次數(shù))1(23)1(32nnjnj 2. 2.快速排序快速排序基本思想：基本思想： 就排序時間而言，快速排序被認(rèn)為是一種最好的內(nèi)部排序方法。就排序時間而言，快速排序被認(rèn)為是一種最好的內(nèi)部排序方法。 通過一趟快速排序?qū)⒋判?/p>

28、的記錄分割成獨(dú)立的兩部分，其中前一部分通過一趟快速排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分，其中前一部分記錄的關(guān)鍵字均比樞軸記錄的關(guān)鍵字小；后一部分記錄的關(guān)鍵字均比樞軸記記錄的關(guān)鍵字均比樞軸記錄的關(guān)鍵字小；后一部分記錄的關(guān)鍵字均比樞軸記錄的關(guān)鍵字大，樞軸記錄得到了它在整個序列中的最終位置并被存放好，這錄的關(guān)鍵字大，樞軸記錄得到了它在整個序列中的最終位置并被存放好，這個過程稱為一趟快速排序。個過程稱為一趟快速排序。 第二趟再分別對分割成兩部分子序列，再進(jìn)行快速排序，這兩部分子序第二趟再分別對分割成兩部分子序列，再進(jìn)行快速排序，這兩部分子序列中的樞軸記錄也得到了最終在序列中的位置而被存放好，并且它們又

29、分別列中的樞軸記錄也得到了最終在序列中的位置而被存放好，并且它們又分別分割出獨(dú)立的兩個子序列分割出獨(dú)立的兩個子序列。顯然，這是一個遞歸的過程，不斷進(jìn)行下去，。顯然，這是一個遞歸的過程，不斷進(jìn)行下去，直到每個待排序的子序列中只有一個記錄時為止，整個排序過程結(jié)束。直到每個待排序的子序列中只有一個記錄時為止，整個排序過程結(jié)束。 快速排序是對冒泡排序的一種改進(jìn)?？焖倥判蚴菍γ芭菖判虻囊环N改進(jìn)。 如何把一個記錄組分成兩個部分？通常是以序列中第一個記錄的關(guān)鍵字如何把一個記錄組分成兩個部分？通常是以序列中第一個記錄的關(guān)鍵字值作為樞軸記錄。值作為樞軸記錄。排序過程：排序過程： 對對rstrst中記錄進(jìn)行一趟快

30、速排序，附設(shè)兩個指針中記錄進(jìn)行一趟快速排序，附設(shè)兩個指針i i和和j j，設(shè)樞軸記錄設(shè)樞軸記錄rp=rsrp=rs，x=rp.keyx=rp.key 初始時令初始時令i=s,j=ti=s,j=t 首先從首先從 j j 所指位置向前搜索第一個關(guān)鍵字所指位置向前搜索第一個關(guān)鍵字小于小于 x x 的記錄，的記錄，并和并和 rp rp 交換；交換； 再從再從 i i 所指位置起向后搜索，找到第一個關(guān)鍵字所指位置起向后搜索，找到第一個關(guān)鍵字大于大于 x x 的記錄，和的記錄，和 rp rp 交換；交換； 重復(fù)上述兩步，直至重復(fù)上述兩步，直至i=ji=j為止為止 再分別對兩個子序列進(jìn)行快速排序，直到每個子

31、序列再分別對兩個子序列進(jìn)行快速排序，直到每個子序列只含只含有一個記錄有一個記錄為止。為止。例例初始關(guān)鍵字：初始關(guān)鍵字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序：完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進(jìn)行快速排序：分別進(jìn)行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束：快速排序結(jié)束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij算法：算法：int Partition(int i,int j) int Partition(i

32、nt i,int j) /i/i、j j為形參，分別代表為形參，分別代表lowlow和和highhigh RecType pivot=Ri; while(ij) while(ij) / / 從表的兩端交替地向中間掃描從表的兩端交替地向中間掃描 while(i=pivot.key) while(i=pivot.key) j- -; j- -; if (ij) Ri+=Rj; if (ij) Ri+=Rj; while (ij&Ri.key=pivot.key) while (ij&Ri.key=pivot.key) i+ +; i+ +; if (ij) if (ij) Rj- -=Ri; Rj

33、- -=Ri; Ri=pivot; return i; Ri=pivot; return i; void QuickSort(int low,int high) void QuickSort(int low,int high) / / 遞歸形式的快排序遞歸形式的快排序 int pivotpos,k;int pivotpos,k; if (lowhigh) if (lowhigh) pivotpos=Partition(low,high); pivotpos=Partition(low,high); /調(diào)用調(diào)用Partition(low,high)Partition(low,high)函數(shù)函數(shù)

34、QuickSort(low,pivotpos-1); QuickSort(low,pivotpos-1); / / 對低子表遞歸排序?qū)Φ妥颖磉f歸排序 QuickSort(pivotpos+1,high); QuickSort(pivotpos+1,high); / / 對高子表遞歸排序?qū)Ω咦颖磉f歸排序 算法評價算法評價時間復(fù)雜度時間復(fù)雜度 最好情況最好情況（每次總是選到中間值作樞軸）（每次總是選到中間值作樞軸）T(n)=O(nlogT(n)=O(nlog2 2n)n)經(jīng)經(jīng)驗(yàn)證明快速排序?yàn)橥瑪?shù)量級下平均性能最好的。驗(yàn)證明快速排序?yàn)橥瑪?shù)量級下平均性能最好的。 最壞情況最壞情況（每次總是選到最小或最

35、大元素作樞軸）（每次總是選到最小或最大元素作樞軸）-退化為冒退化為冒泡排序泡排序T(n)=O(n)T(n)=O(n)?？臻g復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸最壞情況：最壞情況：S(n)=O(n)S(n)=O(n)一般情況：一般情況：S(n)=O(logS(n)=O(log2 2n)n)快速排序?yàn)椴环€(wěn)定排序?？焖倥判?yàn)椴环€(wěn)定排序。10.4 10.4 選擇排序選擇排序 1. 1.簡單選擇簡單選擇排序排序基本思想：基本思想： （1）初始狀態(tài)：整個數(shù)組）初始狀態(tài)：整個數(shù)組 r 劃分成兩個部分，即有序區(qū)劃分成兩個部分，即有序區(qū)（初始為空）和無序區(qū)。（初始為空）和無序區(qū)。 （2）基本

36、操作：從無序區(qū)中選擇關(guān)鍵字值最小的記錄，將）基本操作：從無序區(qū)中選擇關(guān)鍵字值最小的記錄，將其與無序區(qū)的第一個記錄交換（實(shí)質(zhì)是添加到有序區(qū)尾部）。其與無序區(qū)的第一個記錄交換（實(shí)質(zhì)是添加到有序區(qū)尾部）。 從初態(tài)（有序區(qū)為空）開始，重復(fù)步驟（從初態(tài)（有序區(qū)為空）開始，重復(fù)步驟（2 2），直到終態(tài)），直到終態(tài)（無序區(qū)為空）。（無序區(qū)為空）。 排序過程排序過程 首先通過首先通過 n-1 n-1 次關(guān)鍵字比較，從次關(guān)鍵字比較，從 n n 個記錄中找出關(guān)個記錄中找出關(guān)鍵字最小的記錄，鍵字最小的記錄，將它與第一個記錄交換將它與第一個記錄交換； 再通過再通過 n-2 n-2 次比較，從剩余的次比較，從剩余的 n

37、-1 n-1 個記錄中找出關(guān)個記錄中找出關(guān)鍵字次小的記錄，鍵字次小的記錄，將它與第二個記錄交換將它與第二個記錄交換； 重復(fù)上述操作，共進(jìn)行重復(fù)上述操作，共進(jìn)行 n-1n-1趟趟 排序后，排序結(jié)束。排序后，排序結(jié)束。例例初始：初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟：一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 27 38 49 65

38、 97 76 六趟：六趟： 13 27 38 49 65 76 97 排序結(jié)束：排序結(jié)束： 13 27 38 49 65 76 97算法：算法： void Selectsort() for (i=1;in;i+) k=i; for (j=i+1;j=n;j+) if (Rj.keyas； for (j=2*s；j=m；j=j*2) /沿關(guān)鍵碼較大的子女結(jié)點(diǎn)向下篩選沿關(guān)鍵碼較大的子女結(jié)點(diǎn)向下篩選 if (jaj.keyaj+1.key) j=j+1； / /為關(guān)鍵碼較大的元素下標(biāo)為關(guān)鍵碼較大的元素下標(biāo) if (ac.keyaj.key) baeak； / ac/ ac應(yīng)插入在位置應(yīng)插入在位置s

39、s上上 h-as=h-aj； s=j； / / 使使s s結(jié)點(diǎn)滿足堆定義結(jié)點(diǎn)滿足堆定義 h-as=ac； / / 插入插入 void HeapSoat (S_TBL *h) for (i=h-length/2；i0；i- -) / / 將將a1.lengtha1.length建成堆建成堆 HeapAdjust (h，i，h-length)； for (i=h-length；i1；i- -) h-a1h-ai； / / 堆頂與堆低元素交換堆頂與堆低元素交換 HeapAdjust (h，1，i-1)； / / 將將a1.i-1a1.i-1重新調(diào)整為堆重新調(diào)整為堆 算法評價：算法評價：時間復(fù)雜度：最好、壞情況下時間復(fù)雜度：最好、壞情況下T(n)=O(nlogn)-n較大時比較有效較大時比較有效空間復(fù)雜度：空間復(fù)雜度：S(n)=O(1)堆排序?yàn)椴环€(wěn)定排序。堆排序?yàn)椴环€(wěn)定排序。10.5 10.5 歸并排序歸并排序 歸并排序是將兩個或兩個以上的有序子表合并成一個新歸并排序是將兩個或兩個以上的有序子表合并成一個新的有序表。的有序表?；舅枷耄夯舅枷耄?（1）將）將n個記錄的待排序序列看成是有個記錄的待排序序列看成是有n個長度都為個長度都為1的有的有序子表組成。序子表組成。 （2）將兩兩相鄰的子表歸并為一個有序子表。）將兩兩相鄰的子