1、1 10.4.2 堆排序（Floyd &Williams） 直接選擇的比較次數(shù)多是因?yàn)楹笠惶宋蠢们耙惶说谋容^結(jié)構(gòu)，樹形選擇可克服此缺點(diǎn)，但它耗費(fèi)的空間大，故實(shí)用的樹形選擇是堆排序。思想 將R1.n看作是1棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹的雙親和孩子之關(guān)系，在當(dāng)前無序區(qū)里選擇最?。ù螅┰獢U(kuò)充至有序區(qū)。二叉堆（快速選擇最大/小元） n個(gè)keys序列K1, K2, ，Kn稱為堆，當(dāng)且僅當(dāng)滿足如下性質(zhì)（堆性質(zhì)，堆序）： （1） 或 （2） 這里， 。即i結(jié)點(diǎn)不是葉子2 10.4.2 堆排序堆性質(zhì) 將R1.n看作是完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)時(shí)，堆性質(zhì)實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹： 樹中任一

2、非葉結(jié)點(diǎn)的key均不大/小于其左右孩子（若存在）結(jié)點(diǎn)的key。即：從根到任一葉子的路徑上的結(jié)點(diǎn)序列是一個(gè)有序序列，堆中任一子樹仍是堆。它適合查找嗎？ 101525305670701056253015堆頂703025561510107015255630堆頂小根堆大根堆3 10.4.2 堆排序算法思想 1、初始化 將R1.n建成大根堆，即初始無序區(qū)。 2、排序交換：設(shè)當(dāng)前無序區(qū)是大根堆R1.i，交換其中的首尾記錄，即最大元R1（堆頂）交換到無序區(qū)尾部（有序區(qū)頭部），使有序區(qū)在R的尾部逐漸擴(kuò)大： 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 堆排序算法實(shí)現(xiàn)void HeapSort( SeqList R ) int i; BuildHeap( R ); /將R1.n建成初始堆 for ( i=n; i1; i- ) /進(jìn)行n-1趟堆排序，當(dāng)前無序區(qū)為R1.i R1 Ri; /無序區(qū)首尾記錄交換，R0做暫存單元 Heapify( R,1,i-1 ); /將R1.i-1重新調(diào)整為堆 如何調(diào)整堆和構(gòu)造初始堆？5 10.4.2 堆排序調(diào)整（重建）堆 設(shè)調(diào)整區(qū)間為Rlow.high，因?yàn)橹挥懈鵕low違反堆序，它的兩子樹（若存在，則根為R2l

4、ow，R2low+1）均是堆。無須調(diào)整 若Rlow.key不小于兩孩子的Keys，則Rlow不違反堆序必須調(diào)整 將Rlow和它的兩孩子中較大者交換： 設(shè)Rlarge.key=max R2low.key, R2low+1.key 令Rlow Rlarge 交換后Rlarge可能違反堆序，重復(fù)上述過程，直至被調(diào)整的結(jié)點(diǎn)已滿足堆序，或該結(jié)點(diǎn)已是葉子。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是葉子，結(jié)束； /否則，先令large指向Rlow的左孩子 if (largehigh & Rlarge.key=Rlarge.key ) break; /滿足堆序 Rlow=Rlarge; /交換，小的篩下 low=large; /令low指向新的調(diào)整結(jié)點(diǎn) Rlow=temp; /將被調(diào)整結(jié)點(diǎn)放到最終的位置7 10.4.2 堆排序構(gòu)造初始堆算法 將R1.n建成堆，須將其每個(gè)結(jié)點(diǎn)為根的子樹均調(diào)整為堆。對(duì)葉子（i ）無須調(diào)整，只要依次將以序號(hào)為 , , ,2,1的結(jié)點(diǎn)為根的子樹均調(diào)整為堆即可。按此次

6、序調(diào)整每個(gè)結(jié)點(diǎn)時(shí)，其左右子樹均已是堆 void BuildHeap( SeqList R ) int i; for ( i=n/2; i0; i- ) Heapify( R, i, n); /將Ri.n 調(diào)整為堆 時(shí)間：最壞及平均皆為O(nlgn) (2nlgn+O(n)特點(diǎn)：就地，不穩(wěn)定8 10.5 歸并排序歸并的基本思想：將K（K2）個(gè)有序表合并成一個(gè)新的有序表。二路歸并：K2，類似于理牌void Merge( SeqList R, int low, int m, int high ) /將2個(gè)有序表Rlow.m和Rm+1.high歸并為1個(gè)有序表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( “存儲(chǔ)分配失敗” ) while( i=m & j=high ) /2子表非空時(shí)，取其頭上較小者輸出到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自上而下：分治法設(shè)計(jì) (1)分解：將當(dāng)前區(qū)間一分為二，分裂點(diǎn)mid (2)求解：遞歸地對(duì)2個(gè)子表Rlow.mid和Rmid+1.high進(jìn)行歸并排序，出口是當(dāng)前區(qū)間長(zhǎng)度為1。 (3)組合：將上述兩有序的子表歸并成1個(gè)有序表Rlow.highvoid MergeSort( SeqList R, int low, int high ) int mid; if ( low1 mid=( low+high )/2; /分解 MergeSort( R, low,

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

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

11、,48） 將2位整數(shù)看作2個(gè)keys，先對(duì)個(gè)位，后對(duì)十位做箱排序。因此，無須100個(gè)箱子，只要10個(gè)箱子。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進(jìn)行，箱子用鏈隊(duì)列表示。除第1

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

13、/基rd為10 typedef RecType DataType; /各箱子用鏈隊(duì)列表示，其中的結(jié)點(diǎn)數(shù)據(jù)類型改為與本章的記錄類型一致1510.6.2 基數(shù)排序void RadixSort( SeqList R ) /對(duì)R0.n-1做基數(shù)排序，設(shè)keys為非負(fù)整數(shù)， /且位數(shù)不超過KeySize LinkQueue BRadix; /10個(gè)箱子 int i； for ( i=0; i=0; i- ) /對(duì)位i箱排序，從低位到高位進(jìn)行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； /按關(guān)鍵字jth分量分配，進(jìn)入此過程時(shí)各箱子為空 j=KeySize - j; /將 j 換算為從個(gè)位起算，個(gè)位是第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ù)排序的時(shí)間是O(nlgn)。但是可將其改為n進(jìn)制表示： rdn， dlognnkk，T(n)O( k(n+n) )=O(n)輔助空間：O(n+rd)對(duì)key的要求：穩(wěn)定排序：要求第1趟穩(wěn)定，其余各趟必須穩(wěn)定。1810.7 各種排序方法的比較和選擇選擇因素：實(shí)例規(guī)模，記錄大小，key的結(jié)構(gòu)及初始狀態(tài)，對(duì)穩(wěn)定性的要求，存儲(chǔ)結(jié)構(gòu)，時(shí)間和輔助空間的要求，語言工具（指針）。比較n直接插入直接選擇冒泡排序堆排序快速排序隨 4000 8000 10000 15000機(jī) 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 各種排序方法的比較和