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

2、card at the proper position */ /* end for-P-loop */ ,最壞情形:,輸入的 A 是反序的。 T( N ) = O( N2 ),最好情形:,輸入的 A 是已預(yù)先排序的。 T( N ) = O( N ),3 一些簡單排序算法的下界,【定義】成員存數(shù)的數(shù)組的一個逆序是指數(shù)組中具有性質(zhì) i Aj 的序偶（ Ai， Aj）。,例1 輸入數(shù)據(jù) 34, 8, 64, 51, 32, 21 有 個逆序。,9,(34, 8) (34, 32) (34, 21) (64, 51) (64, 32) (64, 21) (51, 32) (51, 21) (32, 2

3、1),在插入排序中恰好需要執(zhí)行 次交換。,9,交換兩個不按原序排列的相鄰元素 恰好消除一個逆序。,T ( N, I ) = O( ) ， I 是初始數(shù)組中的逆序數(shù)。,I + N,如果數(shù)組幾乎有序， 這個時間是很快的。,這就是全部結(jié)論? 那么怎么加速排序?,嘿! 我們討論的是基于比較的排序， 你必須進(jìn)行比較，然后呢？,這個定理告訴我們什么?,聰明! 為了使算法運(yùn)行更快， 我們必須在一次交換中 不止消除一個逆序。, 交換距離較遠(yuǎn)的元素？,呃 散列?,對一整類只交換相鄰元素的算法來說， 都需要花費(fèi) O( N2 ) 的時間來排序。,3一些簡單排序算法的下界,【定理】N 個互異數(shù)的數(shù)組的平均逆序數(shù)是 N

4、 ( N 1 ) / 4.,【定理】通過交換相鄰元素進(jìn)行排序的任何算法平均需要 ( N2 ) 時間。,4 希爾排序 - by Donald Shell,5-sort,3-sort,1-sort, 定義一個增量序列 h1 h2 0; Increment /= 2 ) /*h sequence */ for ( i = Increment; i = Increment; j - = Increment ) if( Tmp A j - Increment ) A j = A j - Increment ; else break; A j = Tmp; /* end for-I and for-Inc

5、rement loops */ ,4 希爾排序, 最壞情形分析:,【定理】使用希爾增量的希爾排序的最壞運(yùn)行時間是 ( N2 )。,8-sort,4-sort,2-sort,1-sort,4 希爾排序, Hibbard增量序列:,hk = 2k 1 - 相鄰增量沒有公因子。,【定理】使用Hibbard增量的希爾排序的最壞情形運(yùn)行時間為 ( N3/2 ).,猜測：, Tavg Hibbard ( N ) = O ( N5/4 ), Sedgewick的最好增量序列是 1, 5, 19, 41, 109, ，該序列中的項(xiàng)要么是 94i 92i + 1，或者是 4i 32i + 1。 猜測其平均運(yùn)行時

6、間Tavg ( N ) = O ( N7/6 ) ， 最壞情形運(yùn)行時間Tworst ( N ) = O ( N4/3 ).,希爾排序算法的整體時間復(fù)雜度和增量序列的選取有關(guān)，目前并沒有統(tǒng)一的最優(yōu)增量序列。 希爾排序是算法非常簡單但又具有極其復(fù)雜的分析的一種排序算法。它對適度的大量輸入數(shù)據(jù)（萬數(shù)量級）是經(jīng)常選用的算法。,5 堆排序,Algorithm 1: BuildHeap( H ); for ( i=0; i 0; i - - ) Swap( ,堆排序的數(shù)據(jù)從位置 0 開始。,【定理】對 N 個互異項(xiàng)的隨機(jī)排列進(jìn)行堆排序，所用的比較平均次數(shù)為 2N log N O( N log log N

7、) .,Note: 雖然堆排序有最好的平均情形時間，但實(shí)踐中它比某個版本的使用 Sedgewick 增量序列的希爾排序要慢。,6 歸并排序,1. 合并兩個已排序數(shù)組,1,2,Lpos,Rpos,Tpos,T ( N ) = O ( ) ， N 是總的元素個數(shù)。,N,Lpos,Rpos,Tpos,Tpos,二路歸并。 也可以使用多路歸并。,6 歸并排序,2. Mergesort,void MSort( ElementType A , ElementType TmpArray , int Left, int Right ) int Center; if ( Left Right ) /* if t

8、here are elements to be sorted */ Center = ( Left + Right ) / 2; MSort( A, TmpArray, Left, Center ); /* T( N / 2 ) */ MSort( A, TmpArray, Center + 1, Right ); /* T( N / 2 ) */ Merge( A, TmpArray, Left, Center + 1, Right ); /* O( N ) */ void Mergesort( ElementType A , int N ) ElementType *TmpArray; /

9、* need O(N) extra space */ TmpArray = malloc( N * sizeof( ElementType ) ); if ( TmpArray != NULL ) MSort( A, TmpArray, 0, N - 1 ); free( TmpArray ); else FatalError( No space for tmp array! ); ,如果 TmpA 定義成Merge的局部變量，則每次調(diào)用Merge都需要開辟不同的空間, 那么 S(N) = O( ),N log N,6 歸并排序,/* Lpos = start of left half, Rp

10、os = start of right half */ void Merge( ElementType A , ElementType TmpArray , int Lpos, int Rpos, int RightEnd ) int i, LeftEnd, NumElements, TmpPos; LeftEnd = Rpos - 1; TmpPos = Lpos; NumElements = RightEnd - Lpos + 1; while( Lpos = LeftEnd ,6 歸并排序,3. 分析,T ( 1 ) = 1,T ( N ) = 2T ( N / 2 ) + O( N )

11、,= 2k T ( N / 2k ) + k * O( N ),= N * T ( 1 ) + log N * O( N ),= O( N + N log N ),非遞歸實(shí)現(xiàn):,Note:歸并排序需要線性的額外存儲, 并且經(jīng)常復(fù)制臨時數(shù)組導(dǎo)致效率降低。 它很少用于內(nèi)部排序，然而在外部排序中非常常用。,7 快速排序,- 實(shí)踐中已知的最快排序算法,1. 算法,void Quicksort ( ElementType A , int N ) if ( N ,j,i,i,j,i,i,j,i, A Center ) Swap( /* Return pivot */ ,7 快速排序,void Qsort(

12、 ElementType A , int Left, int Right ) int i, j; ElementType Pivot; if ( Left + Cutoff Pivot ) /* scan from right */ if ( i N 將會怎樣 ?, “基數(shù)排序 ( Radix Sort )” 是“桶排序 ( Bucket Sort )”的推廣。,10 基數(shù)排序, 基數(shù)排序：一般用于多關(guān)鍵字的排序,10 基數(shù)排序,例 一疊牌的排序要基于兩個關(guān)鍵字。, 基數(shù)排序的方法一般采用“主位優(yōu)先法” ( Most Significant Digit First, MSD) 或者“次位優(yōu)先法

13、” ( Least Significant Digit First, LSD),相當(dāng)于“分治法”,“分配-收集”法,主位優(yōu)先法(MSD ) 排序, 先排花色: 比如, 建立4個花色的“桶”, 再排面值: 每個桶分別獨(dú)立排序(可以采用以前介紹的任何排序方法),10 基數(shù)排序,先排面值: 建立13個面值的“桶”，把牌放入相應(yīng)的桶中（這叫“分配”）；, 依次“收集”它們成為一疊牌；,再排花色: 建立4個桶進(jìn)行再“分配”；,次位優(yōu)先法(LSD ) 排序, 再次“收集”它們成為一疊牌即告完成。,10 基數(shù)排序,還不趕緊拿一副牌出來試試？,例 給定 N = 10 個整數(shù)，范圍介于 0 到 999 ( M

14、= 1000 ) 之間。是否可以在線性的時間內(nèi)把它們排序 ?, 單關(guān)鍵字的基數(shù)排序,輸入: 64, 8, 216, 512, 27, 729, 0, 1, 343, 125,（3位數(shù)可以看成個3關(guān)鍵字，再按“次位優(yōu)先法”排序）,0,1,512,343,64,125,216,27,8,729,0,1,8,512,216,125,27,729,343,64,輸出: 0, 1, 8, 27, 64, 125, 216, 343, 512, 729,時間復(fù)雜性：T=O(D(N+R) 其中D是輪次, N 是元素個數(shù), R 是桶的數(shù)量.,按“主位優(yōu)先法”排序?qū)鯓?,10 基數(shù)排序,空間復(fù)雜性：S=O(

15、N+R) , N 是元素個數(shù), R 是桶的數(shù)量.,用鏈?zhǔn)絻Υ娓阌诜峙渑c收集？,11 外部排序*,11 外部排序*( External Sorting ), 內(nèi)部排序和外部排序, 分兩個步實(shí)施：(a) 分段內(nèi)排序 (b) 歸并（二路或多路）,要提高外排的效率，關(guān)鍵要解決以下4個問題： 如何減少歸并輪數(shù)； 如何有效安排內(nèi)存中的輸入、輸出塊，使得機(jī)器的并行處理能力被最大限度地利用； 如何有效生成歸并段； 如何將歸并段進(jìn)行有效歸并。, 外部排序模型,模型假設(shè)至少 3 個磁帶驅(qū)動器進(jìn)行排序工作。其中 2 個執(zhí)行有效的排序，而第 3 個驅(qū)動器進(jìn)行簡化工作。, 簡單算法,使用歸并排序的合并算法 趟，外加一趟構(gòu)造