c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)_第08講排序-資料下載頁(yè)
2024-10-17 03:54本頁(yè)面
【正文】 歸并排序是將兩個(gè)或兩個(gè)以上的有序子表合并成一個(gè)新的有序表 。 1． 基本思想 （ 1） 將 n個(gè)記錄的待排序序列看成是有 n個(gè)長(zhǎng)度都為 1的有序子表組成 。 （ 2） 將兩兩相鄰的子表歸并為一個(gè)有序子表 。 （ 3） 重復(fù)上述步驟 ， 直至歸并為一個(gè)長(zhǎng)度為 n的有序表 。 2． 【 例 910】 設(shè)初始關(guān)鍵字序列為： 49 38 65 97 76 13 27 20 執(zhí)行歸并排序的過程如圖 910所在示 。 95 歸并排序 初始關(guān)鍵字： [49] [38] [65] [97] [76] [13] [27] [20] 一趟歸并之后： [38 49] [65 97] [13 76] [20 27] 二趟歸并之后： [38 49 65 97 ] [13 20 27 76 ] 三趟歸并之后： [13 20 27 38 49 65 76 97 ] 圖 911 歸并排序過程 3． 算法 void Merge (int low,int mm,int high) // 兩個(gè)相鄰有序段的合并 { RecType *R1。 while(i=mmamp。amp。j=high) R1[p++]=(R[i].key=R[j].key)?R[i++]:R[j++]。 while(i=mm) R1[p++]=R[i++]。 while(j=high) R1[p++]=R[j++]。 for(p=0,i=low。i=high。p++,i++) R[i]=R1[p]。 } void MergePass(int length) // 完成一趟完整的合并 { for (i=1。i+2*length1=L。i=i+2*length) Merge(i,i+length1,i+2*length1)。 if (i+length1L) Merge(i,i+length1,L)。 } void Mergesort() // 控制有序段的長(zhǎng)度 ， 每合并一趟 ， 有序段長(zhǎng)加倍 { for (length=1。lengthL。length*=2) { MergePass(length)。 m++。 } } 4． 效率分析 對(duì) n個(gè)元素的序列 ， 執(zhí)行二路歸并算法 ， 則必須做log2n趟歸并 ， 每一趟歸并的時(shí)間復(fù)雜度是 O（ n） ， 所以二路歸并的時(shí)間復(fù)雜度為 O(nlog2n)。 兩路歸并排序需要和待排序序列一樣多的輔助空間 。其空間復(fù)雜度為 O（ n） 。 兩路歸并排序也是一種穩(wěn)定性的排序 。 返 回 評(píng)估一個(gè)排序法的好壞，除了用排序的時(shí)間及空間外，尚需考慮穩(wěn)定度、最壞狀況和程序的編寫難易程度，例如冒泡排序法，雖然效率不高，但卻常常被使用，因?yàn)楹脤懸锥?。而歸并排序法需要大量的額外空間，快速排序法雖然很快，但在某些時(shí)候效率卻與插入排序法差不多。以下就常用的排序法按最壞情況下所需時(shí)間、平均所需時(shí)間、是否屬于穩(wěn)定排序、所需的額外空間等以表 93來表示。 96 各種排序方法的比較 返 回 （ 1） 排序是將數(shù)據(jù)的任意序列 ， 重新排列成一個(gè)按關(guān)鍵字有序的序列 。 （ 2） 整個(gè)排序過程全部在內(nèi)存進(jìn)行的排序稱為內(nèi)排序 ， 直接插入排序 、 希爾排序 、 冒泡排序 、 快速排序 、 簡(jiǎn)單選擇排序 、 堆排序一般適合內(nèi)排序 。 歸并排序既適合內(nèi)排序 ，也適合外排序 。 （ 3） 若對(duì)任意的數(shù)據(jù)元素序列 ， 使用某個(gè)排序方法 ， 對(duì)它按關(guān)鍵字進(jìn)行排序 ， 若相同關(guān)鍵字元素間的位置關(guān)系 ， 排序前與排序后保持一致 ， 稱此排序方法是穩(wěn)定的；反之 ，則稱為不穩(wěn)定的 。 （ 4） 直接插入排序 、 冒泡排序 、 歸并排序是穩(wěn)定的排序方法；而簡(jiǎn)單選擇排序 、 希爾排序 、 快速排序 、 堆排序是不穩(wěn)定的排序方法 。 小 結(jié) （ 5） 直接插入排序 、 冒泡排序 、 簡(jiǎn)單選擇排序是簡(jiǎn)單型的排序 ， 其時(shí)間復(fù)雜度都為 O（ n 2） ， 空間復(fù)雜度為 O（ 1） 。 （ 6） 堆排序 、 快速排序和歸并排序是改進(jìn)型的排序方法 ，其時(shí)間復(fù)雜度均為 O（ nlog2n） ， 空間復(fù)雜度分別為： O（ 1） 、 O（ log2n） 、 O（ n） 。 （ 7） 希爾排序又稱為縮小增量排序 ， 也是插入類排序的方法 ， 但在時(shí)間上有較大的改進(jìn) 。 其時(shí)間復(fù)雜度約為： O（ ） ， 空間復(fù)雜度為： O（ 1） 。 （ 8） 各種不同的排序方法應(yīng)根據(jù)不同的環(huán)境及條件分別選擇 。 一般而言 ， 對(duì)于排序元素少的 ， 可以選用時(shí)間復(fù)雜度為 O（ n2） 的算法； 對(duì)于元素多的 ， 可選用時(shí)間復(fù)雜度為 :O（ nlog2n） 的算法 。 返 回 實(shí)驗(yàn) 8 排序子系統(tǒng) 1． 實(shí)驗(yàn)?zāi)康? （ 1） 掌握常用排序方法的基本思想； （ 2） 通過實(shí)驗(yàn)加深理解各種排序算法； （ 3） 通過實(shí)驗(yàn)掌握各種排序方法的時(shí)間復(fù)雜度分析； （ 4） 了解各種排序方法的優(yōu)缺點(diǎn)及適用范圍 。 2． 實(shí)驗(yàn)內(nèi)容 （ 1） 編寫直接插入排序程序； （ 2） 編寫希爾排序程序； （ 3） 編寫冒泡排序程序； （ 4） 編寫快速排序程序； （ 5） 編寫選擇排序程序； （ 6） 編寫歸并排序程序； （ 7） 編寫堆排序程序； （ 8） 程序執(zhí)行時(shí) ， 要求能顯示每一趟的排序結(jié)果； （ 9） 設(shè)計(jì)一個(gè)選擇式菜單 ， 以菜單方式選擇上述排序程序 。 排 序 子 系 統(tǒng) *************************************************** * 1更新排序數(shù)據(jù) * * 2直接插入排序 * * 3希 爾 排 序 * * 4冒 泡 排 序 * * 5快 速 排 序 * * 6選 擇 排 序 * * 7歸 并 排 序 * * 8堆 排 序 * * 0返 回 * *************************************************** 請(qǐng)選擇菜單項(xiàng)： 返 回 習(xí)題 9 參見習(xí)題解答 返 回
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1