第9章內(nèi)部排序

1、按排序的規(guī)則不同，可分為按排序的規(guī)則不同，可分為5類：類：插入排序插入排序交換排序（重點是快速排序）交換排序（重點是快速排序）選擇排序選擇排序歸并排序歸并排序基數(shù)排序基數(shù)排序d關(guān)鍵字的位數(shù)關(guān)鍵字的位數(shù)(長度長度)按排序算法的時間復(fù)雜度不同，可分為按排序算法的時間復(fù)雜度不同，可分為3類：類：簡單的排序算法：時間效率低，簡單的排序算法：時間效率低，O(n2)先進(jìn)的排序算法先進(jìn)的排序算法: 時間效率高，時間效率高，O( nlog2n )基數(shù)排序算算法：時間效率高，基數(shù)排序算算法：時間效率高，O( dn)* *表示后一個表示后一個25250 1 2 3 4 5 6252525494949252525*

2、 * *161616080808解：解：假設(shè)該序列已存入一維數(shù)組假設(shè)該序列已存入一維數(shù)組V7V7中，將中，將V0V0作為緩沖或作為緩沖或暫存單元（暫存單元（TempTemp）。則程序執(zhí)行過程為：）。則程序執(zhí)行過程為：初態(tài)：初態(tài)：111122142221nininnniRMNnnniKCN/)()( ,/)(22參見教材參見教材P272P272經(jīng)驗公式經(jīng)驗公式dkdk值依次裝在值依次裝在dltadltat t 中中11111233121nininninRMNnninKCN)()()()(見教材見教材P276/長度長度1/對順序表對順序表L中的子序列中的子序列r lowhigh 作快速排序作快速排

3、序/一趟快排，將一趟快排，將r 一分為二一分為二/在左子區(qū)間進(jìn)行遞歸快排，直到長度為在左子區(qū)間進(jìn)行遞歸快排，直到長度為1/在右子區(qū)間進(jìn)行遞歸快排，直到長度為在右子區(qū)間進(jìn)行遞歸快排，直到長度為1/QSort新的新的low 1, L.length Void SelectSort(SqList &L ) for (i=1; i0; - - i ) HeapAdjust(r, i, length ); 這是針對結(jié)點這是針對結(jié)點 i 的堆調(diào)整函數(shù)，其含義是：的堆調(diào)整函數(shù)，其含義是：從結(jié)點從結(jié)點i i開開始到始到堆尾堆尾為止，自上向下比較，如果子女的值大于雙為止，自上向下比較，如果子女的值大于雙親結(jié)點的值

4、，則互相交換，即把局部調(diào)整為大根堆。親結(jié)點的值，則互相交換，即把局部調(diào)整為大根堆。 /temp是根，是根，child是其左孩子是其左孩子 /檢查是否到達(dá)當(dāng)前堆尾檢查是否到達(dá)當(dāng)前堆尾 /讓讓child指向兩子女中的大者指向兩子女中的大者 /根大則不必調(diào)整，結(jié)束整個函數(shù)根大則不必調(diào)整，結(jié)束整個函數(shù) /否則子女中的大者上移否則子女中的大者上移/ /直到自下而上都滿足堆定義，再安置直到自下而上都滿足堆定義，再安置老老根根/將根下降到子女位置將根下降到子女位置123456136542123456136542123456136542123456136542123456136542這是針對結(jié)點這是針對結(jié)點i

5、 i 的堆調(diào)整函數(shù)的堆調(diào)整函數(shù)（也是建堆函（也是建堆函數(shù)）數(shù)），每次調(diào)用耗時，每次調(diào)用耗時O(logO(log2 2n)n)比較左右孩比較左右孩子大小，子大小，j指指向大者向大者比較大孩子比較大孩子與與rc的大小的大小若大向上浮若大向上浮rc = H.rs; j = 2s; jm &H.rj.keyH.rj+1.key+ j; / 指向右兄弟指向右兄弟j H.rj.keyH.rs=H.rj; s=j;j=2*j; /指向左孩子指向左孩子NNNYYYH.rsm中除中除rs外，其他具有堆特征外，其他具有堆特征現(xiàn)調(diào)整現(xiàn)調(diào)整rs的值的值 ，使，使H.rsm為堆為堆HeapAdjust( )關(guān)鍵字序列關(guān)

6、鍵字序列T= （21，25，49，25*，93，62，72，08，37，16，54），請給出歸并排序的具體實），請給出歸并排序的具體實現(xiàn)過程?，F(xiàn)過程。void (SR，&TR，i, m, n) / 將將有序的有序的SRim和和SRm+1n歸并為歸并為有序的有序的TRin for(k=i , j=m+1; i=m & j=n; +k ) if ( SRi= SRj )TRk=SRi+; else TRk=SRj+; / 將將SR中記錄由小到大地并入中記錄由小到大地并入TR if (i=m) TRkn=SRim; / 將剩余的將剩余的SRim復(fù)制到復(fù)制到TR if (j=n) TRkn=SRjn;

7、 / 將剩余的將剩余的SRjn復(fù)制到復(fù)制到TR / Merge void MSort (SR，&TR1，s, t) / 將將無序的無序的SRst歸并排序為歸并排序為TR1st if ( s=t )TR1s=SRs; / 當(dāng)當(dāng)len=1時返回時返回 else m=(s+t)/2; / 將將SR st平分為平分為SR sm和和SR m+1t MSort (SR，&TR2，s, m); / 將將SR 一分為二一分為二, 2分為分為4 / 遞歸地將遞歸地將SR sm歸并為有序的歸并為有序的TR2sm MSort (SR，&TR2，m+1, t ); / 遞歸地將遞歸地將SR m+1t歸并為有序的歸并為

8、有序的TR2m+1t (TR2， TR1， s, m, t ); / 將將TR2 sm和和TR2 m+1t歸并歸并到到TR1 st / MSort簡言之，先由簡言之，先由“長長”無序變成無序變成“短短”有序，再從有序，再從“短短”有序歸并為有序歸并為“長長”有序。有序。初次調(diào)用時為（初次調(diào)用時為（L, L, 1, length）因為在遞歸的歸并排序算法中，函數(shù)因為在遞歸的歸并排序算法中，函數(shù)Merge( )做一趟兩路歸并做一趟兩路歸并排序，需要調(diào)用排序，需要調(diào)用merge ( )函數(shù)函數(shù) n/(2*len) O(n/len) 次，函數(shù)次，函數(shù)Merge( )調(diào)用調(diào)用Merge( )正好正好 l

9、og2n 次，而每次次，而每次merge( )要執(zhí)行比要執(zhí)行比較較O(len)次，所以算法總的時間復(fù)雜度為次，所以算法總的時間復(fù)雜度為O(nlog2n)。因為需要一個與原始序列同樣大小的輔助序列（因為需要一個與原始序列同樣大小的輔助序列（TR）。這正）。這正是此算法的缺點。是此算法的缺點。以上兩例都是典型的多關(guān)鍵字排序！因為有分組，故此算法需遞歸實現(xiàn)。例：例：初始關(guān)鍵字序列初始關(guān)鍵字序列T=（32, 13, 27, 32*, 19，33），請分別），請分別用用MSD和和LSD進(jìn)行排序，并討論其優(yōu)缺點。進(jìn)行排序，并討論其優(yōu)缺點。法法1（MSD）：）：原始序列：原始序列：32, 13, 27, 3

10、2*, 19， 33 先按高位先按高位 排序：排序：（13, 19）, 27, （32, 32*，33） 再按低位再按低位排序排序 ： 13, 19 ， 27, 32, 32*, 33法法2（LSD）：）： 原始序列：原始序列： 32, 13, 27, 32*, 19 ，33 先按低位先按低位排序：排序： 32, 32*, 13, 33, 27, 19 再按高位再按高位排序：排序： 13, 19 , 27, 32, 32*, 33無需分組，易編程實現(xiàn)！又稱散列過程！又稱散列過程！排序時經(jīng)過了反復(fù)的排序時經(jīng)過了反復(fù)的“分配分配”和和“收集收集”過程。當(dāng)對關(guān)過程。當(dāng)對關(guān)鍵字所有的位進(jìn)行掃描排序后，

11、整個序列便從無序變?yōu)橛行蜴I字所有的位進(jìn)行掃描排序后，整個序列便從無序變?yōu)橛行蛄?。了。能！能！e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9r0f e eifi+1 530790921101614485215306637738r0e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9530790921101614485215306637738eifi+1 530790921101614485215306637738r0r0530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9eifi+1 530790921101614485215306637738r0r0ej隊不空，則新元素隊不空，則新元素應(yīng)鏈到原隊尾元素應(yīng)鏈到原隊尾元素之后之后P P是關(guān)鍵字序列是關(guān)鍵字序列r r 的指針分量的指針分量隊首為空