湘潭大學(xué) 數(shù)據(jù)結(jié)構(gòu) Ch07 Sorting 排序算法

1、編輯ppt1第7章 排序很常見的一類問(wèn)題（很常見的一類問(wèn)題（并不局限于排序本身）并不局限于排序本身）編輯ppt21 預(yù)備知識(shí)預(yù)備知識(shí)void X_Sort ( ElementType A , int N )/* N 是排序元素個(gè)數(shù)，是合法的整數(shù)是排序元素個(gè)數(shù)，是合法的整數(shù)*/* 為簡(jiǎn)單起見，假設(shè)數(shù)組只包含整數(shù)為簡(jiǎn)單起見，假設(shè)數(shù)組只包含整數(shù) */* 和和 運(yùn)算符存在，而且是僅有的允許對(duì)輸入數(shù)據(jù)進(jìn)行的操運(yùn)算符存在，而且是僅有的允許對(duì)輸入數(shù)據(jù)進(jìn)行的操作作 */基于比較基于比較的排序的排序/* 僅考慮內(nèi)部排序僅考慮內(nèi)部排序 */整個(gè)排序工作能夠在主存中完成整個(gè)排序工作能夠在主存中完成編輯ppt32 插

2、入排序插入排序void InsertionSort ( ElementType A , int N ) int j, P; ElementType Tmp; for ( P = 1; P 0 & A j - 1 Tmp; j- ) A j = A j - 1 ; /* shift sorted cards to provide a position for the new coming card */A j = Tmp; /* place the new card at the proper position */ /* end for-P-loop */最壞情形最壞情形:輸入的輸入的

3、 A 是反序的。是反序的。 T( N ) = O( N2 )最好情形最好情形:輸入的輸入的 A 是已預(yù)先排序的。是已預(yù)先排序的。 T( N ) = O( N )編輯ppt43 一些簡(jiǎn)單排序算法的下界一些簡(jiǎn)單排序算法的下界【定義定義】成員存數(shù)的數(shù)組的一個(gè)成員存數(shù)的數(shù)組的一個(gè)逆序逆序是指數(shù)組中具有性質(zhì)是指數(shù)組中具有性質(zhì) i Aj 的序偶（的序偶（ Ai， Aj）。）。例例1 輸入數(shù)據(jù)輸入數(shù)據(jù) 34, 8, 64, 51, 32, 21 有有 個(gè)逆序。個(gè)逆序。9 (34, 8) (34, 32) (34, 21) (64, 51) (64, 32) (64, 21) (51, 32) (51, 21

4、) (32, 21)在插入排序中恰好需要執(zhí)行在插入排序中恰好需要執(zhí)行 次交換。次交換。9交換兩個(gè)不按原序排列的相鄰元素交換兩個(gè)不按原序排列的相鄰元素恰好消除恰好消除一個(gè)逆序。一個(gè)逆序。T ( N, I ) = O( ) ， I 是初始數(shù)組中的逆序數(shù)。是初始數(shù)組中的逆序數(shù)。I + N如果數(shù)組如果數(shù)組幾乎有序幾乎有序，這個(gè)時(shí)間是很快的。這個(gè)時(shí)間是很快的。編輯ppt5這就是全部結(jié)論這就是全部結(jié)論?那么怎么加速排序那么怎么加速排序?嘿嘿! 我們討論的是我們討論的是基于比較的基于比較的排序，排序，你必須進(jìn)行比較，然后呢？你必須進(jìn)行比較，然后呢？這個(gè)定理告訴我們什么這個(gè)定理告訴我們什么? 聰明聰明! 為了

5、使算法運(yùn)行更快，為了使算法運(yùn)行更快，我們必須在一次交換中我們必須在一次交換中不止消除一個(gè)逆序不止消除一個(gè)逆序。 交換距離較遠(yuǎn)的元素？交換距離較遠(yuǎn)的元素？呃呃 散列散列?對(duì)一整類只交換相鄰元素的算法來(lái)說(shuō)，對(duì)一整類只交換相鄰元素的算法來(lái)說(shuō)，都需要花費(fèi)都需要花費(fèi) O( N2 ) 的時(shí)間來(lái)排序。的時(shí)間來(lái)排序。3一些簡(jiǎn)單排序算法的下界一些簡(jiǎn)單排序算法的下界【定理定理】N 個(gè)互異數(shù)的數(shù)組的平均逆序數(shù)是個(gè)互異數(shù)的數(shù)組的平均逆序數(shù)是 N ( N 1 ) / 4.【定理定理】通過(guò)交換相鄰元素進(jìn)行排序的任何算法平均需要通過(guò)交換相鄰元素進(jìn)行排序的任何算法平均需要 ( N2 ) 時(shí)間。時(shí)間。編輯ppt64 希爾排序希

6、爾排序 - by Donald Shell例例2Sort: 81941196123517952858417515962812588135419417751195155-sort964194112858357595128117153-sort1-sort96419411285835759512811715 定義一個(gè)定義一個(gè)增量序列增量序列 h1 h2 0; Increment /= 2 ) /*h sequence */for ( i = Increment; i = Increment; j - = Increment ) if( Tmp A j - Increment ) A j = A j

7、 - Increment ; else break; A j = Tmp; /* end for-I and for-Increment loops */編輯ppt84 希爾排序希爾排序 最壞情形分析最壞情形分析:【定理定理】使用希爾增量的希爾排序的最壞運(yùn)行時(shí)間是使用希爾增量的希爾排序的最壞運(yùn)行時(shí)間是 ( N2 )。例例3一個(gè)壞例子一個(gè)壞例子:19210311412513614715816192103114125136147158168-sort192103114125136147158164-sort192103114125136147158162-sort123456789101112 1

8、3 14 15 161-sort增量對(duì)未必增量對(duì)未必互素互素，因此較小的增量可能影響很小。，因此較小的增量可能影響很小。編輯ppt94 希爾排序希爾排序 Hibbard增量序列增量序列:hk = 2k 1 - 相鄰增量沒(méi)有公因子。相鄰增量沒(méi)有公因子。【定理定理】使用使用Hibbard增量的希爾排序的最壞情形運(yùn)行時(shí)增量的希爾排序的最壞情形運(yùn)行時(shí)間為間為 ( N3/2 ).猜測(cè)：猜測(cè)： Tavg Hibbard ( N ) = O ( N5/4 ) Sedgewick的最好增量序列是的最好增量序列是 1, 5, 19, 41, 109, ，該，該序列中的項(xiàng)要么是序列中的項(xiàng)要么是 9 4i 9 2i

9、 + 1，或者是，或者是 4i 3 2i + 1。 猜測(cè)其平均運(yùn)行時(shí)間猜測(cè)其平均運(yùn)行時(shí)間Tavg ( N ) = O ( N7/6 ) ， 最壞情形運(yùn)行時(shí)間最壞情形運(yùn)行時(shí)間Tworst ( N ) = O ( N4/3 ).編輯ppt10希爾排序算法的整體時(shí)間復(fù)雜度希爾排序算法的整體時(shí)間復(fù)雜度和增量序列的選取有和增量序列的選取有關(guān)關(guān)，目前并沒(méi)有統(tǒng)一的最優(yōu)增量序列。，目前并沒(méi)有統(tǒng)一的最優(yōu)增量序列。 希爾排序是算法非常簡(jiǎn)單但又具有極其復(fù)雜的分析的希爾排序是算法非常簡(jiǎn)單但又具有極其復(fù)雜的分析的一種排序算法。它對(duì)適度的大量輸入數(shù)據(jù)（萬(wàn)數(shù)量級(jí)）一種排序算法。它對(duì)適度的大量輸入數(shù)據(jù)（萬(wàn)數(shù)量級(jí)）是經(jīng)常選用的

10、算法。是經(jīng)常選用的算法。編輯ppt115 堆排序堆排序Algorithm 1: BuildHeap( H ); for ( i=0; iN; i+ ) TmpH i = DeleteMin( H ); for ( i=0; i= 0; i - - ) /* BuildHeap */ PercDown( A, i, N ); for ( i = N - 1; i 0; i - - ) Swap( &A 0 , &A i ); /* DeleteMax */ PercDown( A, 0, i ); 堆排序的數(shù)據(jù)從位置堆排序的數(shù)據(jù)從位置 0 開始。開始。【定理定理】對(duì)對(duì) N 個(gè)互異

11、項(xiàng)的隨機(jī)排列進(jìn)行堆排序，所用的比較個(gè)互異項(xiàng)的隨機(jī)排列進(jìn)行堆排序，所用的比較平均次數(shù)為平均次數(shù)為 2N log N O( N log log N ) .Note: 雖然堆排序有雖然堆排序有最好的平均情形時(shí)間最好的平均情形時(shí)間，但實(shí)踐中它比某個(gè)版本，但實(shí)踐中它比某個(gè)版本的使用的使用 Sedgewick 增量序列的希爾排序要慢。增量序列的希爾排序要慢。編輯ppt136 歸并排序歸并排序1. 合并兩個(gè)已排序數(shù)組合并兩個(gè)已排序數(shù)組113 24 26215 27 3812LposRposTposT ( N ) = O ( ) ， N 是總的元素個(gè)數(shù)。是總的元素個(gè)數(shù)。NLposRposTpos Tpos二路

12、歸并二路歸并。也可以使用也可以使用多路多路歸并歸并。編輯ppt146 歸并排序歸并排序2. Mergesortvoid MSort( ElementType A , ElementType TmpArray , int Left, int Right ) int Center; if ( Left Right ) /* if there are elements to be sorted */Center = ( Left + Right ) / 2; MSort( A, TmpArray, Left, Center ); /* T( N / 2 ) */MSort( A, TmpArray,

13、 Center + 1, Right ); /* T( N / 2 ) */Merge( A, TmpArray, Left, Center + 1, Right ); /* O( N ) */ void Mergesort( ElementType A , int N ) ElementType *TmpArray; /* need O(N) extra space */ TmpArray = malloc( N * sizeof( ElementType ) ); if ( TmpArray != NULL ) MSort( A, TmpArray, 0, N - 1 ); free( T

14、mpArray ); else FatalError( No space for tmp array! ); 如果如果 TmpA 定義成定義成Merge的的局部變量局部變量，則每次調(diào)用，則每次調(diào)用Merge都需要開辟不同的空間都需要開辟不同的空間, 那么那么 S(N) = O( )N log N編輯ppt156 歸并排序歸并排序/* Lpos = start of left half, Rpos = start of right half */ void Merge( ElementType A , ElementType TmpArray , int Lpos, int Rpos, int

15、RightEnd ) int i, LeftEnd, NumElements, TmpPos; LeftEnd = Rpos - 1; TmpPos = Lpos; NumElements = RightEnd - Lpos + 1; while( Lpos = LeftEnd & Rpos = RightEnd ) /* main loop */ if ( A Lpos = A Rpos ) TmpArray TmpPos+ = A Lpos+ ; else TmpArray TmpPos+ = A Rpos+ ; while( Lpos = LeftEnd ) /* Copy re

16、st of first half */ TmpArray TmpPos+ = A Lpos+ ; while( Rpos = RightEnd ) /* Copy rest of second half */ TmpArray TmpPos+ = A Rpos+ ; for( i = 0; i NumElements; i+, RightEnd - - ) /* Copy TmpArray back */ A RightEnd = TmpArray RightEnd ; 編輯ppt166 歸并排序歸并排序3. 分析分析T ( 1 ) = 1T ( N ) = 2T ( N / 2 ) + O(

17、 N )= 2k T ( N / 2k ) + k * O( N )= N * T ( 1 ) + log N * O( N )= O( N + N log N )非遞歸實(shí)現(xiàn)非遞歸實(shí)現(xiàn):A0123 n 4 n 3 n 2 n 1 Note:歸并排序需要?dú)w并排序需要線性的額外線性的額外存儲(chǔ)存儲(chǔ), 并且經(jīng)常復(fù)制臨時(shí)并且經(jīng)常復(fù)制臨時(shí)數(shù)組導(dǎo)致效率降低。數(shù)組導(dǎo)致效率降低。 它它很很少用于內(nèi)部排序少用于內(nèi)部排序，然而在，然而在外部排序外部排序中非常常用。中非常常用。編輯ppt177 快速排序快速排序- 實(shí)踐中已知的實(shí)踐中已知的最快最快排序算法排序算法1. 算法算法void Quicksort ( Elem

18、entType A , int N ) if ( N = e元素元素 = e2元素元素 = e1元素元素 jiijiiji A Center ) Swap( &A Left , &A Center ); if ( A Left A Right ) Swap( &A Left , &A Right ); if ( A Center A Right ) Swap( &A Center , &A Right ); /* Invariant: A Left = A Center = A Right */ Swap( &A Center , &am

19、p;A Right - 1 ); /* Hide pivot */ /* only need to sort A Left + 1 A Right 2 */ return A Right - 1 ; /* Return pivot */ 編輯ppt237 快速排序快速排序void Qsort( ElementType A , int Left, int Right ) int i, j; ElementType Pivot; if ( Left + Cutoff = Right ) /* if the sequence is not too short */ Pivot = Median3(

20、A, Left, Right ); /* select pivot */ i = Left; j = Right 1; /* why not set Left+1 and Right-2? */ for( ; ; ) while ( A + +i Pivot ) /* scan from right */ if ( i j ) Swap( &A i , &A j ); /* adjust partition */ else break; /* partition done */ Swap( &A i , &A Right - 1 ); /* restore pi

21、vot */ Qsort( A, Left, i - 1 ); /* recursively sort left part */ Qsort( A, i + 1, Right ); /* recursively sort right part */ /* end if - the sequence is long */ else /* do an insertion sort on the short subarray */ InsertionSort( A + Left, Right - Left + 1 );編輯ppt247 快速排序快速排序6. 分析分析T( N ) = T( i ) +

22、 T( N i 1 ) + c N 最壞情形最壞情形:T( N ) = T( N 1 ) + c NT( N ) = O( N2 ) 最好情形最好情形: . . . . T( N ) = 2T( N / 2 ) + c NT( N ) = O( N log N ) 平均情形平均情形:假設(shè)對(duì)任意的假設(shè)對(duì)任意的i， T( i )的平均值是的平均值是 10)(1NjjTNcNjTNNTNj 10)(2)(T( N ) = O( N log N )void Qselect( ElementType A , int k, int Left, int Right ) int i, j; ElementTy

23、pe Pivot;/* 1*/ if( Left + Cutoff = Right ) /* 2*/ Pivot = Median3( A, Left, Right );/* 3*/ i = Left; j = Right - 1;/* 4*/ for( ; ; ) /* 5*/ while( A +i Pivot ) /* 7*/ if( i j )/* 8*/ Swap( &A i , &A j ); else/* 9*/ break; /*10*/ Swap( &A i , &A Right - 1 ); /* Restore pivot */*11*/

24、if( k i + 1 )/*14*/ Qselect( A, k, i + 1, Right ); else /* Do an insertion sort on the subarray */*15*/ InsertionSort( A + Left, Right - Left + 1 ); /* END */例例選擇問(wèn)題。選擇問(wèn)題。 快速選擇快速選擇關(guān)于此問(wèn)題的關(guān)于此問(wèn)題的第第5種種算法。算法。編輯ppt268 大型結(jié)構(gòu)的排序大型結(jié)構(gòu)的排序問(wèn)題問(wèn)題: 交換大型結(jié)構(gòu)可能是非常昂貴的操作。交換大型結(jié)構(gòu)可能是非常昂貴的操作。解決方法解決方法: 在數(shù)組中包含指向結(jié)構(gòu)的指針，通過(guò)交換指針來(lái)排序在數(shù)

25、組中包含指向結(jié)構(gòu)的指針，通過(guò)交換指針來(lái)排序 間接間接排序。排序。 最后在必要時(shí)再實(shí)際地重新安排結(jié)構(gòu)。最后在必要時(shí)再實(shí)際地重新安排結(jié)構(gòu)。listkeytable0d01b12f23c34a45e5table 413052排序列表是排序列表是list table0 , list table1 , , list tablen 1 Note: 每一個(gè)序列都由不相交的環(huán)構(gòu)成。每一個(gè)序列都由不相交的環(huán)構(gòu)成。listkeytable0d41b12f33c04a55e2temp = dcurrent = 0next = 4a045e452f523c23d3最壞情形下有最壞情形下有 ? 個(gè)環(huán)，需要個(gè)環(huán)，需要 ?

26、 次記錄的移動(dòng)。次記錄的移動(dòng)。 N / 2 3N / 2 T = O( m N ) ， m 是每個(gè)結(jié)構(gòu)的大小。是每個(gè)結(jié)構(gòu)的大小。例例Table Sort編輯ppt279 排序的一般下界排序的一般下界【定理定理】只使用只使用元素間比較元素間比較的任何排序算法需要進(jìn)行的任何排序算法需要進(jìn)行 ( N log N )次比較。次比較。證明證明:K0 K1K1 K2K0 K2stop0,1,2stop0,2,1stop2,0,1TFTFK0 K2K1 K2stop1,0,2stop1,2,0stop2,1,0TFTFTF三元素排序的決策樹三元素排序的決策樹當(dāng)進(jìn)行當(dāng)進(jìn)行 N 個(gè)互異元素排序時(shí)，有個(gè)互異元素排

27、序時(shí)，有 N! 種可能的結(jié)果。種可能的結(jié)果。因此任意決策樹必定含有至少因此任意決策樹必定含有至少N! 片樹葉。片樹葉。如果樹高為如果樹高為 k, 那么那么 N! 2k 1 (一棵完全二叉樹中的葉子數(shù)量一棵完全二叉樹中的葉子數(shù)量) k log(N!) + 1由于由于 N! (N/2)N/2 及及 log2 N! (N/2)log2(N/2) = ( N log2 N )因此因此 T(N) = k c N log2 N .編輯ppt28 桶排序桶排序例例 假如有假如有N 個(gè)學(xué)生，每個(gè)人的成績(jī)分布在個(gè)學(xué)生，每個(gè)人的成績(jī)分布在 0 到到 100 (令令 M = 101 種可能的成績(jī)種可能的成績(jī)). 如

28、何在如何在線性的時(shí)間線性的時(shí)間內(nèi)按照成績(jī)給他們內(nèi)按照成績(jī)給他們排序排序 ?count0110088算法思想：算法思想： 初始化鏈表頭數(shù)組初始化鏈表頭數(shù)組 count ; while (讀一個(gè)學(xué)生的成績(jī)讀一個(gè)學(xué)生的成績(jī)) 把它插入鏈表把它插入鏈表 countstdnt.grade; for (i=0; i N 將會(huì)怎樣將會(huì)怎樣 ? “基數(shù)排序基數(shù)排序 ( Radix Sort )” 是是“桶排序桶排序 ( Bucket Sort )”的推廣的推廣。10 基數(shù)排序基數(shù)排序編輯ppt29 基數(shù)排序基數(shù)排序：一般用于多關(guān)鍵字的排序：一般用于多關(guān)鍵字的排序10 基數(shù)排序基數(shù)排序例例 一疊牌的排序要基于一

29、疊牌的排序要基于兩個(gè)關(guān)鍵字。兩個(gè)關(guān)鍵字。第一關(guān)鍵字第一關(guān)鍵字花色花色 第一關(guān)鍵字第一關(guān)鍵字面值面值2 3 4 5 6 7 8 9 10 J Q K A排序結(jié)果應(yīng)該是排序結(jié)果應(yīng)該是: 2 . A 2 . A 2 . A 2 . A 基數(shù)排序的方法一般采用基數(shù)排序的方法一般采用“主位優(yōu)先法主位優(yōu)先法” ( Most Significant Digit First, MSD) 或者或者“次位優(yōu)先法次位優(yōu)先法” ( Least Significant Digit First, LSD)相當(dāng)于相當(dāng)于“分治法分治法”“分配分配-收集收集”法法編輯ppt30主位優(yōu)先法主位優(yōu)先法(MSD ) 排序排序 先排花

30、色先排花色: 比如比如, 建立建立4個(gè)花色的個(gè)花色的“桶桶”3 3 5 5 A A 4 4 再排面值再排面值: 每個(gè)桶分別獨(dú)立排序每個(gè)桶分別獨(dú)立排序(可以采用以前介紹的任何排序方法可以采用以前介紹的任何排序方法) 10 基數(shù)排序基數(shù)排序編輯ppt31先排面值先排面值: 建立建立13個(gè)面值的個(gè)面值的“桶桶”，把牌放入相應(yīng)的桶中（這叫，把牌放入相應(yīng)的桶中（這叫“分配分配”）；）；2 2 3 3 4 4 5 5 A A . 依次依次“收集收集”它們成為一疊牌；它們成為一疊牌；A A 3 3 2 2 再排花色再排花色: 建立建立4個(gè)桶進(jìn)行再個(gè)桶進(jìn)行再“分配分配”；次次位優(yōu)先法位優(yōu)先法(LSD ) 排序

31、排序 再次再次“收集收集”它們成為一疊牌即告完成。它們成為一疊牌即告完成。10 基數(shù)排序基數(shù)排序還不趕緊拿一副牌出來(lái)試試？還不趕緊拿一副牌出來(lái)試試？編輯ppt32例例 給定給定 N = 10 個(gè)整數(shù)，范圍介于個(gè)整數(shù)，范圍介于 0 到到 999 ( M = 1000 ) 之間。是否之間。是否可以在可以在線性的時(shí)間線性的時(shí)間內(nèi)把它們排序內(nèi)把它們排序 ? 單關(guān)鍵字的單關(guān)鍵字的基數(shù)排序基數(shù)排序輸入輸入: 64, 8, 216, 512, 27, 729, 0, 1, 343, 1250桶：桶：123456789（3位數(shù)可以看成個(gè)位數(shù)可以看成個(gè)3關(guān)鍵關(guān)鍵字，再按字，再按“次位優(yōu)先法次位優(yōu)先法”排序）排序）0輪次輪次 11512 34364125 216278729輪次輪次 20151234364125216278729輪次輪次 30185122161252772934364輸出輸出: 0, 1, 8, 27, 64, 125, 216, 343, 512, 729時(shí)間復(fù)雜性：時(shí)間復(fù)雜性：T=O(D(N+R) 其中其中D是輪次是輪次, N 是元素個(gè)數(shù)是元素個(gè)數(shù), R 是桶的數(shù)是桶的數(shù)量量.按按“主位優(yōu)先法主位優(yōu)先法”排序?qū)?huì)怎樣排序?qū)?huì)