數(shù)據(jù)結(jié)構(gòu)用c語言描述第八章j-資料下載頁
2025-05-13 00:10本頁面
【正文】 if ( R[i] = R[j] ) { R1 [k] = R[i]。 i++。 k++。 } else { R1 [k] = R[j]。 j++。 k++。 } while ( i = mid ) { R1[k] = R[i]。 i++。 k++。 }//將 mid前剩余的并入 while ( j = high ) { R1[k] = R[j]。 j++。 k++。 } //將 mid后剩余的并入 } 兩路歸并算法 一趟歸并排序的情形 ? 設(shè) R[0]到 R[n1]中 n 個對象已經(jīng)分為一些長度為 len 的歸并項(xiàng) , 將這些歸并項(xiàng)兩兩歸并 , 歸并成長度為 2len 的歸并項(xiàng) , 結(jié)果放到 R1[ ]中。 ? 如果 n不是 2len的整數(shù)倍 , 則一趟歸并到最后 ,可能遇到兩種情形： ? 剩下一個長度為 len的歸并項(xiàng)和另一個長度不足 len的歸并項(xiàng) , 可用 merge算法將它們歸并成一個長度小于 2len 的歸并項(xiàng)。 ? 只剩下一個歸并項(xiàng)，其長度小于或等于 len, 將它直接抄到 R1[ ]中。 迭代的歸并排序算法 ? 迭代的歸并排序算法就是利用兩路歸并過程進(jìn)行排序的。其基本思想是： ? 假設(shè)初始對象序列有 n 個對象，首先把它看成是 n 個長度為 1 的有序子序列 (歸并項(xiàng) )，先做兩兩歸并，得到 ?n / 2? 個長度為 2 的歸并項(xiàng) (如果 n 為奇數(shù)，則最后一個有序子序列的長度為 1)；再做兩兩歸并， … ，如此重復(fù)，最后得到一個長度為 n 的有序序列。 迭代的歸并排序算法 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 MergePass ( rectype R[ ], rectype R1[ ], int len ) { int i = 0。 while (i+2*len1 = n1) { merge( R, R1, i, i+len1, i+2*len1)。 i += 2 * len。 //循環(huán)兩兩歸并 } if ( i+len = n1 ) merge( R, R1, i, i+len1, n1)。 else for ( int j = i。 j = n1。 j++) R1 [j] = R[j]。 } ?歸并排序的主算法 MergeSort ( rectype R[ ], int n ) { //按對象關(guān)鍵字非遞減的順序?qū)Ρ碇袑ο笈判? rectype R1[n]。 int len = 1。 while ( len n ) { MergePass ( R, R1, len )。 len *= 2。 MergePass ( R1, R, len )。 len *= 2。 } } ? 在迭代的歸并排序算法中 , 函數(shù) MergePass( ) 做一趟兩路歸并排序 , 要調(diào)用 merge ( )函數(shù) ?n/(2*len)? ? O(n/len) 次 , 函數(shù) MergeSort( )調(diào)用 MergePass( )正好 ?log2n? 次 ,而每次 merge( )要執(zhí)行比較 O(len)次 , 所以算法總的時間復(fù)雜度為 O(nlog2n)。 ? 歸并排序占用附加存儲較多 , 需要另外一個與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組 。 這是這個算法的缺點(diǎn) 。 ? 歸并排序是一個穩(wěn)定的排序方法 。 基數(shù)排序 ?多關(guān)鍵字排序 例 對 52張撲克牌按以下次序排序： ?2?3…… ?A?2?3…… ?A ?2?3…… ?A?2?3…… ?A 兩個關(guān)鍵字：花色 （ ???? ） 面值 （ 23……A ） 并且“花色”地位高于“面值” ?多關(guān)鍵字排序方法 最高位優(yōu)先法（ MSD)： 先對最高位關(guān)鍵字 k1（ 如花色）排序，將序列分成若干子序列，每個子序列有相同的 k1值；然后讓每個子序列對次關(guān)鍵字 k2（ 如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個子序列對最低位關(guān)鍵字 kd排序；最后將所有子序列依次連接在一起成為一個有序序列 最低位優(yōu)先法 (LSD)：從最低位關(guān)鍵字 kd起進(jìn)行排序，然后再對高一位的關(guān)鍵字排序， …… 依次重復(fù)，直至對最高位關(guān)鍵字 k1排序后，便成為一個有序序列 ? 鏈?zhǔn)交鶖?shù)排序 ? 基數(shù)排序：借助“分配”和“收集”對單邏輯關(guān)鍵字進(jìn)行排序的一種方法 ? 鏈?zhǔn)交鶖?shù)排序 方法 ：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序 ? 設(shè)置 10個隊(duì)列， f[i]和 e[i]分別為第 i個隊(duì)列的頭指針和尾指針 ? 第一趟分配對最低位關(guān)鍵字（個位）進(jìn)行，改變記錄的指針值，將鏈表中記錄分配至 10個鏈隊(duì)列中，每個隊(duì)列記錄的關(guān)鍵字的個位相同 ? 第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個非空隊(duì)列的隊(duì)頭記錄，重新將 10個隊(duì)列鏈成一個鏈表 ? 重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別對十位、百位進(jìn)行，最后得到一個有序序列 例： 初始狀態(tài)： 278 109 063 930 589 184 505 269 008 083 109 589 269 278 063 930 083 184 505 008 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] 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 一趟收集： 505 008 109 930 063 269 278 083 184 589 二趟收集： 083 184 589 063 505 269 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 二趟分配 008 109 278 930 063 083 184 505 278 008 109 589 269 一趟收集： 008 063 083 109 184 269 278 505 589 930 三趟收集： 109 008 184 930 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 三趟分配 063 083 269 278 505 589 505 008 109 930 063 269 278 083 184 589 二趟收集： 各種排序方法的比較 比較次數(shù) 移動次數(shù) 附加存儲排 序 方 法最好 最差最好 最差穩(wěn)定 性最好 最差直接插入排序 n n2 0 n2 ? 1折半插入排序 n l og2n 0 n2 ? 1起泡排序n n2 0 n2 ? 1快速排序 n l og2n n2n l og2n n2 ? l og2n n2簡單選擇排序 n2 0 n ? 1錦標(biāo)賽排序 n l og2n n l og2n ? n堆排序 n l og2n n l og2n ? 1歸并排序n l og2n n l og2n ? n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1