[計(jì)算機(jī)軟件及應(yīng)用]數(shù)據(jù)結(jié)構(gòu)-文庫(kù)吧
2025-09-20 04:11 本頁(yè)面
【正文】 if ( [0].key [m].key ) high = m1。 // 插入點(diǎn)在低半?yún)^(qū) else low = m+1。 // 插入點(diǎn)在高半?yún)^(qū) } for( j=i1。 j=high+1。 j ) [j+1]=[j]。 // 記錄后移 [high+1]=[0]。 // 插入 } } 算法分析： ? 折半插入排序所需要的關(guān)鍵字比較次數(shù)與待排序記錄序列的初始排列無關(guān)，僅依賴于記錄個(gè)數(shù)。在插入第 i 個(gè)記錄時(shí)，需要經(jīng)過 ?log2i? +1 次關(guān)鍵字比較，才能確定它應(yīng)插入的位置。 將 n 個(gè)記錄用折半插入排序所進(jìn)行的關(guān)鍵字比較次數(shù)為O(nlog2n) . ? 折半插入排序的時(shí)間復(fù)雜度仍為 O（ n2） ? 當(dāng) n 較大時(shí) ， 總的關(guān)鍵字比較次數(shù)比直接插入排序的最壞情況要好得多 ， 但比其最好情況要差 。 ? 在記錄的初始排列已經(jīng)按關(guān)鍵字排好序或接近有序時(shí) ， 直接插入排序比折半插入排序執(zhí)行的關(guān)鍵字比較次數(shù)要少 。 折半插入排序的記錄移動(dòng)次數(shù)與直接插入排序相同 ， 依賴于記錄的初始排列 。 ? 折半插入排序是一個(gè)穩(wěn)定的排序方法 。 希爾排序 (Shell Sort) ? 從對(duì)直接插入排序的分析可知 ， 其時(shí)間復(fù)雜度為O(n2), 但是當(dāng)待排序記錄處于 “ 基本有序 ” 狀態(tài)或 當(dāng) n值較小 時(shí) ， 直接插入排序的效率可大大提高 。Shell 排序方法正是基于這兩點(diǎn)考慮對(duì)直接插入排序加以改進(jìn)而提出的一種插入排序算法 。 ? Shell 排序方法是一種 “ 逐漸縮小插入間隔 ” 的插入排序方法 ， 在時(shí)間效率上較直接插入排序有較大的改進(jìn) 。 ? 先確定一個(gè)小于 n 的整數(shù) d1作為第一個(gè) 增量 ，把記錄序列分為 d1個(gè)組，所有距離為 d1倍數(shù)的記錄放在同一個(gè)組中，在各組內(nèi)進(jìn)行直接插入排序； ? 然后，取第二個(gè)增量 d2（ d2 d1 ） ,重復(fù)上述分組和排序，直至所取的增量 dt=1（ dtdt1… d 2 d1 ） , 即所有記錄處在同一組中進(jìn)行直接插入排序?yàn)橹埂? Shell 排序的基本做法： 21 25 49 25* 16 08 1 2 3 4 5 6 21 25* i = 1 d1 = 3 49 25 16 08 25 16 49 25* 08 21 08 49 25 21 25* 16 21 25 49 25* 16 08 1 2 3 4 5 6 21 i = 2 08 d2 = 2 25 49 16 25* 16 08 21 25 49 25* 49 08 16 21 25* 25 21 25 49 25* 16 08 0 1 2 3 4 5 21 i = 3 08 d3 = 1 25 16 49 25* ?開始時(shí) 增量 值較大，子序列中的 記錄較少 ，排序速度較快；隨著排序進(jìn)展，增量值逐漸變小，子序列中記錄個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)記錄已 基本有序 ，所以排序速度仍然很快。 void ShellInsert( SqList amp。L,int dk ){ for( i=dk+1。 i=。 i++ ) if([i].key [idk].key){ // 需將 [i]插入有序增量子表 [0] = [i]。 // 暫存在 [0],但不是哨兵 。 for(j=idk。 j0 amp。amp。 [0].key[j].key。 j=dk) [j+dk] = [j]。 // 記錄后移 ， 查找插入位置 [j+dk] = [0]。 } } void ShellSort(SqList amp。L, int dlta[], int t){ // 按增量序列 dlta[0..t1]對(duì)順序表 L作希爾排序 for(k=0。 kt。 t++){ ShellInsert( L, dlta[k] )。 // 一趟增量為 dlta[k]的插入排序 } 希爾排序的算法： ? 增量 的取法有多種。最初 shell 提出取 d1 = ?n/2?， d2 = ?d1/2?，直到 dt = 1。后來 knuth 提出取 di+1 = ?di/3? +1。還有人提出都取奇數(shù)為好，也有人提出各 增量 互質(zhì)為好。 算法分析： 對(duì)特定的待排序記錄序列 ， 可以準(zhǔn)確地估算關(guān)鍵字的比較次數(shù)和記錄移動(dòng)次數(shù) 。 但想要弄清關(guān)鍵字比較次數(shù)和記錄移動(dòng)次數(shù)與增量選擇之間的依賴關(guān)系 ， 并給出完整的數(shù)學(xué)分析 ， 還沒有人能夠做到 。 快速排序 ( Exchange Sort ) ? 基本方法 ： 比較相鄰兩個(gè)記錄的關(guān)鍵字，若R[i].keyR[i+1].key，則交換之，其中 i 從 0到 npass1（ pass的初值為 1）稱之為一趟起泡排序，其結(jié)果是使最大關(guān)鍵字的記錄被交換到 npass的位置上，如果某一趟起泡排序過程中沒有進(jìn)行一次記錄的交換，則排序過程結(jié)束。最壞情況下需 n1趟排序。 基本思想： 是兩兩比較待排序記錄的關(guān)鍵字，如果發(fā)生逆序 (即排列順序與排序后的次序正好相反 )，則交換之，直到所有記錄都排好序?yàn)橹埂? 起泡排序 (Bubble Sort) 21 25 49 25* 16 08 0 1 2 3 4 5 21 25* i = 1 49 25 16 25 16 08 49 noSwap=1 08 25* 49 21 noSwap =1 i = 2 i = 3 08 16 noSwap =1 25* 25 21 25* 0 1 2 3 4 5 i = 4 49 16 noSwap =0 08 25 21 void BubbleSort( SqList amp。L ){ // 從下往上掃描的起泡排序 for( i=0。 in2。i++ ){ // 做 n1趟排序 noSwap=TRUE。 // 置未交換標(biāo)志 for( j=n1。j=i。j ) // 從下往上掃描 if([j+1].key [j].key) { temp=[j+1]。 // 交換記錄 [j+1]=[j]。 [j]=temp。 noSwap=FALSE。 } if( noSwap ) break。 // 本趟掃描未發(fā)生交換 ， 則終止算法 } } 起泡排序的算法： 算法分析： 在記錄的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí)，此算法只執(zhí)行一趟起泡，做 n1 次關(guān)鍵字比較，不移動(dòng)記錄。這是最好的情形。 ? 最壞的情形是算法執(zhí)行了 n1趟起泡，第 i 趟 (1? i? n) 做了 n i 次關(guān)鍵字比較，執(zhí)行了 ni 次記錄交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù) KCN和記錄移動(dòng)次數(shù) RMN為： ? 起泡排序需要一個(gè)附加記錄以實(shí)現(xiàn)記錄值的對(duì)換。 ? 起泡排序是一個(gè)穩(wěn)定的排序方法。 ??????????????11111233121nininninR M NnninK C N)()()()(快速排序 (Quick Sort) ? 基本思想 ： – 是任取待排序記錄序列中的某個(gè)記錄 (例如取第一個(gè)記錄 ) 作為 基準(zhǔn) ，按照該記錄的關(guān)鍵字大小，將整個(gè)記錄序列劃分為左右兩個(gè)子序列： ? 左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于基準(zhǔn)記錄的關(guān)鍵字 ? 右側(cè)子序列中所有記錄的關(guān)鍵字都大于或等于基準(zhǔn)記錄的關(guān)鍵字 – 基準(zhǔn)記錄則排在這兩個(gè)子序列中間 (這也是該記錄最終應(yīng)安放的位置 )。 – 然后分
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1