基數(shù)排序的時間是Onlgn課件

1、1 10.4.2 堆排序（Floyd &Williams） 直接選擇的比較次數(shù)多是因為后一趟未利用前一趟的比較結構，樹形選擇可克服此缺點，但它耗費的空間大，故實用的樹形選擇是堆排序。思想 將R1.n看作是1棵完全二叉樹的順序存儲結構，利用完全二叉樹的雙親和孩子之關系，在當前無序區(qū)里選擇最?。ù螅┰獢U充至有序區(qū)。二叉堆（快速選擇最大/小元） n個keys序列K1, K2, ，Kn稱為堆，當且僅當滿足如下性質(zhì)（堆性質(zhì)，堆序）： （1） 或 （2） 這里， 。即i結點不是葉子2 10.4.2 堆排序堆性質(zhì) 將R1.n看作是完全二叉樹的順序存儲結構時，堆性質(zhì)實質(zhì)上是滿足如下性質(zhì)的完全二叉樹： 樹中任一

2、非葉結點的key均不大/小于其左右孩子（若存在）結點的key。即：從根到任一葉子的路徑上的結點序列是一個有序序列，堆中任一子樹仍是堆。它適合查找嗎？ 101525305670701056253015堆頂703025561510107015255630堆頂小根堆大根堆3 10.4.2 堆排序算法思想 1、初始化 將R1.n建成大根堆，即初始無序區(qū)。 2、排序交換：設當前無序區(qū)是大根堆R1.i，交換其中的首尾記錄，即最大元R1（堆頂）交換到無序區(qū)尾部（有序區(qū)頭部），使有序區(qū)在R的尾部逐漸擴大： R1.i-1.keysRi.n.keys /前者為無序區(qū)，后者為有序區(qū) 顯然，in,n-1,2，即n1趟

3、排序即可完成。調(diào)整：將新無序區(qū)R1.i-1調(diào)整為堆。注意：只有R1可能違反堆性質(zhì)。4 10.4.2 堆排序算法實現(xiàn)void HeapSort( SeqList R ) int i; BuildHeap( R ); /將R1.n建成初始堆 for ( i=n; i1; i- ) /進行n-1趟堆排序，當前無序區(qū)為R1.i R1 Ri; /無序區(qū)首尾記錄交換，R0做暫存單元 Heapify( R,1,i-1 ); /將R1.i-1重新調(diào)整為堆 如何調(diào)整堆和構造初始堆？5 10.4.2 堆排序調(diào)整（重建）堆 設調(diào)整區(qū)間為Rlow.high，因為只有根Rlow違反堆序，它的兩子樹（若存在，則根為R2l

4、ow，R2low+1）均是堆。無須調(diào)整 若Rlow.key不小于兩孩子的Keys，則Rlow不違反堆序必須調(diào)整 將Rlow和它的兩孩子中較大者交換： 設Rlarge.key=max R2low.key, R2low+1.key 令Rlow Rlarge 交換后Rlarge可能違反堆序，重復上述過程，直至被調(diào)整的結點已滿足堆序，或該結點已是葉子。2010562530155610252030155610202530156 10.4.2 堆排序調(diào)整堆算法void Heapify( SeqList R, int low, int high ) int large; /只有Rlow可能違反堆序 RecT

5、ype temp=Rlow; for ( large=2*low; largehigh，則Rlow是葉子，結束； /否則，先令large指向Rlow的左孩子 if (largehigh & Rlarge.key=Rlarge.key ) break; /滿足堆序 Rlow=Rlarge; /交換，小的篩下 low=large; /令low指向新的調(diào)整結點 Rlow=temp; /將被調(diào)整結點放到最終的位置7 10.4.2 堆排序構造初始堆算法 將R1.n建成堆，須將其每個結點為根的子樹均調(diào)整為堆。對葉子（i ）無須調(diào)整，只要依次將以序號為 , , ,2,1的結點為根的子樹均調(diào)整為堆即可。按此次

6、序調(diào)整每個結點時，其左右子樹均已是堆 void BuildHeap( SeqList R ) int i; for ( i=n/2; i0; i- ) Heapify( R, i, n); /將Ri.n 調(diào)整為堆 時間：最壞及平均皆為O(nlgn) (2nlgn+O(n)特點：就地，不穩(wěn)定8 10.5 歸并排序歸并的基本思想：將K（K2）個有序表合并成一個新的有序表。二路歸并：K2，類似于理牌void Merge( SeqList R, int low, int m, int high ) /將2個有序表Rlow.m和Rm+1.high歸并為1個有序表Rlow.high int i=low,

7、j=m+1, p=0; /i,j指向輸入子表頭，p指向輸出子表 RecType *R1=(RecType *)malloc(high-low+1)*sizeof(RecType);/輸出 if （ !R1 ）Error( “存儲分配失敗” ) while( i=m & j=high ) /2子表非空時，取其頭上較小者輸出到R1p上 R1p+=( Ri.key=Rj.key ) ? R i+: R j+ ; while ( i=m ) /第1子表非空，將剩余記錄copy到R1中 R1p+=R i+ ; while ( j=high ) /第2子表非空，將剩余記錄copy到R1中 R1p+=R j

8、+ ; R=R1; /將R1copy回R，Rlow.high R10.high-low9 10.5 歸并排序排序算法自底向上：見Fig10.13自上而下：分治法設計 (1)分解：將當前區(qū)間一分為二，分裂點mid (2)求解：遞歸地對2個子表Rlow.mid和Rmid+1.high進行歸并排序，出口是當前區(qū)間長度為1。 (3)組合：將上述兩有序的子表歸并成1個有序表Rlow.highvoid MergeSort( SeqList R, int low, int high ) int mid; if ( low1 mid=( low+high )/2; /分解 MergeSort( R, low,

9、 mid ); /解子問題1，結束時Rlow.mid有序 MergeSort( R, mid+1, high ); /解子問題2，結束時Rmid+1.high有序 Merge( R, low, mid, high ); /組合 /endif10 10.5 歸并排序性能分析時間：最好最壞均是O(nlgn)空間：輔助O(n)，非就地排序特點穩(wěn)定易于在鏈表上實現(xiàn)與快排相比：分解易、組合難11 10.6 分配排序基于比較的排序時間下界:由Stirling公式知：lgn!nlgn-1.44n+O(lgn)要突破此界，就不能通過keys的比較。分配排序正是如此，它通過“分配”和“收集”過程實現(xiàn)排序，時間為

10、O(n)。10.6.1 箱排序基本思想分配：掃描R0.n-1,將key等于k的記錄全裝入kth箱子里收集：按序號將各非空箱子首尾連接起來多趟：每個關鍵字1趟，例如:撲克牌時間：分配：O(n)；收集：設箱子數(shù)為m(與key相關)，時間為O(m)或O(m+n)總計：O(m+n)=O(n) if m=O(n)1210.6.2 基數(shù)排序基本思想箱排序只適用于keys取值范圍小的情況，否則浪費時間和空間。例如，若mO(n2), 則時間和空間均為O(n2)?；鶖?shù)排序是通過分析key的構成，用多趟箱排序?qū)崿F(xiàn)的。例子設n10，ki0.99, 1i 10輸入:（36,5,10,16,98,95,47,32,36

11、,48） 將2位整數(shù)看作2個keys，先對個位，后對十位做箱排序。因此，無須100個箱子，只要10個箱子。1310.6.2 基數(shù)排序第1趟箱排序分配：0 101 2 32345 5,956 36,16,367 478 98,489收集：10,32,5,95,36,16,36,47,98,48（36,5,10,16,98,95,47,32,36,48）第2趟箱排序分配：0 051 10,162 3 32,36,364 47,485 6 7 8 9 95,98收集：05,10,16,32,36,36,47,48,95,98各趟排序前要求清空箱子，分配和收集須按FIFO進行，箱子用鏈隊列表示。除第1

12、趟外，其余各趟一定要是穩(wěn)定的排序，否則結果可能有錯。m不再在數(shù)量級上大于O(n)，故上述排序時間是O(n)1410.6.2 基數(shù)排序一般情況設任一記錄Ri的key均由d個分量 構成多關鍵字文件：d個分量皆為獨立的key單關鍵字文件：每個分量是key中的1位，只討論這種情況。 設每位取值范圍相同： C0KjCrd-1 (0jd) 這里，rd稱為基數(shù)，d為key的位數(shù)。 若key為十進制整數(shù)，按位分解后rd10，C00，C99排序算法 從低位到高位依次對Kj（jd-1,d-2,0）進行d趟箱排序，所需的箱子數(shù)為基rd。 #defin KeySize 4 /設d4 #define Radix 10

13、/基rd為10 typedef RecType DataType; /各箱子用鏈隊列表示，其中的結點數(shù)據(jù)類型改為與本章的記錄類型一致1510.6.2 基數(shù)排序void RadixSort( SeqList R ) /對R0.n-1做基數(shù)排序，設keys為非負整數(shù)， /且位數(shù)不超過KeySize LinkQueue BRadix; /10個箱子 int i； for ( i=0; i=0; i- ) /對位i箱排序，從低位到高位進行d趟箱排序 Distribute( R,B,i ); /分配 Collect( R,B ); /收集 1610.6.2 基數(shù)排序void Distribute( Se

14、qList R, LinkQueue B , int j ) int i，k，t； /按關鍵字jth分量分配，進入此過程時各箱子為空 j=KeySize - j; /將 j 換算為從個位起算，個位是第1位 for ( i=0; in; i+ ) /掃描R，裝箱 k=Ri.key; for( t=1; tj; t- ) k=k/10; /去掉key的后j-1位 k=k%10; /取key的第j位數(shù)字k EnQueue( &Bk,Ri ); /將Ri裝入箱子Bk void Collect( SeqList R, LinkQueue B ) int i=0, j; /依次連接各非空箱子，完成后使各箱

15、子變空 for ( j=0; j1)，則key的位數(shù)是： dlog10nkklog10nO(klgn) 因此，基數(shù)排序的時間是O(nlgn)。但是可將其改為n進制表示： rdn， dlognnkk，T(n)O( k(n+n) )=O(n)輔助空間：O(n+rd)對key的要求：穩(wěn)定排序：要求第1趟穩(wěn)定，其余各趟必須穩(wěn)定。1810.7 各種排序方法的比較和選擇選擇因素：實例規(guī)模，記錄大小，key的結構及初始狀態(tài)，對穩(wěn)定性的要求，存儲結構，時間和輔助空間的要求，語言工具（指針）。比較n直接插入直接選擇冒泡排序堆排序快速排序隨 4000 8000 10000 15000機 20000增 20000減 200005.6723.1535.4380.23143.670.05286.9217.3029.4346.02103.00185.05185.78199.0015.7864.0399.10223.28399.470.03584.670.130.280.350.580.770.750.800.070.170.220.330.470.230.28說明 直接選擇無論k和i是否相等，均交換；快排用中間元做劃分元。1910.7 各種排序方法的比較和