【正文】 最后得到一個(gè)長度為 n 的有序序列 。 82 兩路歸并算法 typedef int SortData。 void merge ( SortData InitList[ ], SortData mergedList[ ], int left, int mid, int right ) { int i = left, j = mid+1, k = left。 while ( i = mid amp。amp。 j = right ) //兩兩比較 if ( InitList[i] = InitList[j] ) { mergedList [k] = InitList[i]。 i++。 k++。 } else { mergedList [k] = InitList[j]。 j++。 k++。 } 83 while ( i = mid ) { mergedList[k] = InitList[i]。 i++。 k++。 } while ( j = right ) { mergedList[k] = InitList[j]。 j++。 k++。 } } 84 一趟歸并排序的情形 ? 設(shè) initList[0]到 initList[n1]中 n 個(gè)對象 已經(jīng)分為一些長度為 len 的歸并項(xiàng) , 將這些歸并項(xiàng)兩兩歸并 , 歸并成長度為 2len 的歸并項(xiàng) , 結(jié)果放到 mergedList[ ]中。 ? 如果 n不是 2len的整數(shù)倍 , 則一趟歸并到最后 ,可能遇到兩種情形： ? 剩下一個(gè)長度為 len的歸并項(xiàng)和另一個(gè)長度不足 len的歸并項(xiàng) , 可用 merge算法 將它們歸并成一個(gè)長度小于 2len 的歸并項(xiàng)。 ? 只剩下一個(gè)歸并項(xiàng)，其長度小于或等于 len, 將它直接抄到 MergedList[ ]中。 85 void MergePass ( SortData initList[ ], SortData mergedList[ ], int len ) { int i = 0。 while (i+2*len1 = n1) { merge( initList, mergedList, i, i+len1, i+2*len1)。 i += 2 * len。 //循環(huán)兩兩歸并 } if ( i+len = n1 ) merge( initList, mergedList, i, i+len1, n1)。 else for ( int j = i。 j = n1。 j++) mergedList [j] = initList[j]。 } 86 迭代的歸并排序算法 21 25 25* 25* 93 62 72 08 37 16 54 49 21 25 49 62 93 08 72 16 37 54 21 25 25* 49 08 62 72 93 16 37 54 08 08 21 16 25 21 25* 25 49 25* 62 37 72 49 93 54 16 37 54 62 72 93 len=1 len=2 len=4 len=8 len=16 87 (兩路 )歸并排序的主算法 void MergeSort ( SortData initList[ ], int n ) { //按對象排序碼非遞減的順序?qū)Ρ碇袑ο笈判? SortData tempList[n]。 int len = 1。 while ( len n ) { MergePass ( initList, tempList, len )。 len *= 2。 MergePass ( tempList, initList, len )。 len *= 2。 } } 88 ? 在迭代的歸并排序算法中 , 函數(shù) MergePass( ) 做一趟兩路歸并排序 , 要調(diào)用 merge ( )函數(shù) ?n/(2*len)? ? O(n/len) 次 , 函數(shù) MergeSort( )調(diào)用 MergePass( )正好?log2n? 次 ,而每次 merge( )要執(zhí)行比較 O(len)次 , 所以算法總的時(shí)間復(fù)雜度為 O(nlog2n)。 ? 歸并排序占用附加存儲(chǔ)較多 , 需要另外一個(gè)與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組 。 這是這個(gè)算法的缺點(diǎn) 。 ? 歸并排序是一個(gè) 穩(wěn)定 的排序方法 。 89 只需要一個(gè)附加存儲(chǔ)的兩路歸并算法 ? 設(shè)算法中參加歸并的兩個(gè)歸并段是 A[left] ?A[mid] 和 A[mid+1]?A[right]，歸并后結(jié)果歸并段放在原地。 08 21 25 49 62 72 16 37 54 left mid mid+1 right A 08 16 08 21 25 49 62 72 16 37 54 A 21 16 08 21 25 49 62 16 37 54 A temp = 72 90 left mid mid+1 right 08 16 21 25 49 62 16 37 54 A temp = 72 08 16 21 25 49 62 37 54 A temp = 72 08 16 21 25 49 62 37 54 72 A 08 16 21 25 49 62 37 54 72 A 21 37 08 16 21 25 49 62 37 54 72 A 25 37 08 16 21 25 49 62 37 54 72 A 49 37 91 left mid mid+1 right 08 16 21 25 49 37 54 72 A temp = 62 08 16 21 25 37 49 37 54 72 A temp = 62 08 16 21 25 37 49 54 62 72 A 08 16 21 25 37 49 54 62 72 A 49 54 08 16 21 25 37 49 54 62 72 A 結(jié)束 92 typedef int SortData。 void merge( SortData A[ ], int left, int mid, int right ) { int i, j。 SortData temp。 for ( i = left。 i = mid。 i++ ) { if ( A[i] A[mid+1] ) { temp = A[mid]。 for ( j = mid1。 j = i。 j ) A[j+1] = A[j]。 A[i] = A[mid+1]。 if ( temp = A[mid+2] ) A[mid+1] = temp。 93 else { for ( j = mid+2。 j = right。 j++ ) if ( temp A[j] ) A[j1] = A[j]。 else { A[j1] = temp。 break。 } } } } } 基數(shù)排序 (Radix Sorting) 前邊將過的各種排序方法主要是通過關(guān)鍵字的比較和記錄的移 動(dòng)完成的。而 基數(shù)排序，不需要進(jìn)行記錄關(guān)鍵字的比較。它是借助 多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)行排序的方法。 多關(guān)鍵字排序通常有兩種方法其一 稱為最高位優(yōu)先法 (Most Significant Digit first)簡稱 MSD；其二是從最地次位關(guān)鍵字起進(jìn)行排 序。然后再對高一位的關(guān)鍵字進(jìn)行排序，直到最高位，這種稱為最 低位優(yōu)先法 (Least Significant Digit first)簡稱 LSD。 基數(shù)排序是借助 “ 分配 ” 和 “ 收集 ” 兩種操作對單邏輯關(guān)鍵字進(jìn)行排 序的一種內(nèi)排序方法。根據(jù)在實(shí)際工程中使用的關(guān)鍵字大都是由數(shù) 字（或字母）組成的，現(xiàn)在，以數(shù)字為例來說明這種排序的過程。 我們知道數(shù)字關(guān)鍵字都是由 0到 9十個(gè)數(shù)字組成，那么，在內(nèi)存設(shè)立 編號為 0— 9的十個(gè)桶。對待排序的記錄從其關(guān)鍵字的最低為到最高 位作如下處理：把每個(gè)記錄存放（分配）到內(nèi)存中桶號與該記錄關(guān) 鍵字當(dāng)前數(shù)位上數(shù)字相同的桶中。經(jīng)過處理（收集）得到一次排序 結(jié)果。下面以順序存儲(chǔ)為例看一看實(shí)際過程。 初始狀態(tài) 278 109 063 930 589 184 505 269 008 183 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 269 083 008 589 930 063 184 505 278 109 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 930 063 083 184 505 278 008 109 589 269 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 109 589 008 269 184 505 930 063 278 083 f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 第二次 505 008 109 930 063 269 278 083 184 589 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 083 063 184 278 589 008 109 269 505 930 f[0]