c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)_第08講排序(已修改)
2024-10-29 03:54 本頁(yè)面
【正文】 實(shí)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 第 9章 排序 第 9章 排 序 ?知 識(shí) 點(diǎn) 排序的基本概念 插入排序方法：直接選擇排序、二分插入排序 快速排序、選擇排序、歸并排序 各種排序方法性能比較 ?難 點(diǎn) 堆排序 快速排序 歸并排序 ?要 求 熟練掌握以下內(nèi)容： 熟悉各種內(nèi)部排序方法的基本思想和特點(diǎn) 各種排序方法的優(yōu)缺點(diǎn)及性能比較 熟悉并掌握一些基本的排序算法 了解以下內(nèi)容： 二路歸并排序算法 堆排序算法 第 9章 目錄 ? 91 概述 ? 92 插入排序 ? 93 快速排序 ? 94 選擇排序 ? 95 歸并排序 ? 96 各種排序方法比較 ? 小 結(jié) ? 實(shí)驗(yàn) 9 排序子系統(tǒng) ? 習(xí)題 9 91 概 述 1． 排序 （ Sorting） 將數(shù)據(jù)元素 （ 或記錄 ） 的任意序列 ， 重新排列成一個(gè)按關(guān)鍵字有序 （ 遞增或遞減 ） 的序列的過(guò)程稱為排序 。 2． 排序過(guò)程中的兩種基本操作 （ 1） 比較兩個(gè)關(guān)鍵字值的大小 。 （ 2） 根據(jù)比較結(jié)果 ， 移動(dòng)記錄的位置 。 3． 對(duì)關(guān)鍵字排序的三個(gè)原則 （ 1） 關(guān)鍵字值為數(shù)值型的 ， 則按鍵值大小為依據(jù) 。 （ 2） 關(guān)鍵字值為 ASCII碼 ， 則按鍵值的內(nèi)碼編排順序?yàn)橐罁?jù) 。 （ 3） 關(guān)鍵字值為漢字字符串類型 ， 則大多以漢字拼音的字典次序?yàn)橐罁?jù) 。 4． 排序方法的穩(wěn)定和不穩(wěn)定 若對(duì)任意的數(shù)據(jù)元素序列 ， 使用某個(gè)排序方法 ， 對(duì)它按關(guān)鍵字進(jìn)行排序 ， 若對(duì)原先具有相同鍵值元素間的位置關(guān)系 ， 排序前與排序后保持一致 ， 稱此排序方法是穩(wěn)定的；反之 ， 則稱為不穩(wěn)定的 。 例如： 對(duì)數(shù)據(jù)鍵值為： 5， 3， 8， 3， 6， 6， 排序 。 若排序后的序列為： 3， 3， 5， 6， 6， 8， 其相同鍵值的元素位置依舊是 3在 3前 ， 6在 6前 ， 與排序前保持一致 ，則表示這種排序法是穩(wěn)定的； 若排序后的序列為： 3， 3， 5， 6， 6， 8， 則表示這種排序法是不穩(wěn)定的 。 5． 待排序記錄的三種存儲(chǔ)方式 （ 1） 待排序記錄存放在地址連續(xù)的一組存儲(chǔ)單元上 。 類似于線性表的順序存儲(chǔ)結(jié)構(gòu) 。 （ 2） 待排序記錄存放在靜態(tài)鏈表中 。 記錄之間的次序關(guān)系由指針指示 ， 排序不需要移動(dòng)記錄 。 （ 3） 待排序記錄存放在一組地址連續(xù)的存儲(chǔ)單元 ， 同時(shí)另設(shè)一個(gè)指示各個(gè)記錄存儲(chǔ)位置的地址向量 ， 在排序過(guò)程中不移動(dòng)記錄本身 ， 而移動(dòng)地址向量中這些記錄的 “ 地址 ” ， 在排序結(jié)束后 ， 再按照地址向量中的值調(diào)整記錄的存儲(chǔ)位置 。 6． 內(nèi)排序 整個(gè)排序過(guò)程都在內(nèi)存進(jìn)行的排序稱為內(nèi)排序 。 7． 外排序 待排序的數(shù)據(jù)元素量大 ， 以致內(nèi)存一次不能容納全部記錄 ， 在排序過(guò)程中需要對(duì)外存進(jìn)行訪問(wèn)的排序稱為外排序 。 92 插入排序 921 直接插入排序 1． 基本思想 直接插入排序 （ Straight Insertion Sort） 是一種最簡(jiǎn)單的排序方法 ， 它的基本操作是將一個(gè)記錄插到已排序好的有序表中 ， 從而得到一個(gè)新的 ， 記錄數(shù)增 1的有序表 。 插入前： （ 1 3 5 8） [ 2 7 4 9 6] 有序 無(wú)序 插入后： （ 1 2 3 5 8） [7 4 9 6] 有序 無(wú)序 2. 【 例 91】 輸入元素序列為： 39， 28， 55， 80， 75， 6，17， 45， 28按從小到大的序列排序 。 第一個(gè)取 39， 作第一個(gè)假設(shè)有序的記錄 ， 第二個(gè)取 28， 2839， 則交換 。 此后 ， 每取來(lái)一個(gè)記錄就與有序表最后一個(gè)關(guān)鍵字比較 ， 若大于或等于最后一個(gè)關(guān)鍵字 ， 則插入在其后；若小于最后一個(gè)關(guān)鍵字 ， 則把取來(lái)的記錄再與前一個(gè)關(guān)鍵字比較 …… ， 其過(guò)程如圖 91： 排序以后 ， 相同關(guān)鍵字元素的 28和 28與排序前的位置保持一致 ， 即 28仍然在 28之前 ， 所以直接插入排序方法是穩(wěn)定的 。 監(jiān)視哨 （ 哨兵 ） 的作用： （ 1） 在進(jìn)入確定插入位置的循環(huán)之前 ， 保存了插入值 r[i]的副本 ， 避免因記錄的移動(dòng)而丟失 r[i]中的內(nèi)容 。 （ 2） 使內(nèi)循環(huán)總能夠結(jié)束 ， 以免循環(huán)過(guò)程中數(shù)組下標(biāo)越界 。 3． 算法 void Insertsort() { for(i=2。i=L。i++) // 依次插入 r[2],r[3],…… r[n] {if (R[i].keyR[i1].key) { R[0]=R[i]。 // 置監(jiān)視哨 j=i1。 while(R[0].keyR[j].key) // 查找 r[i]的位置 { R[j+1]=R[j]。 // 向后移動(dòng)記錄 j 。 } R[j+1]=R[0]。 // 插入 r[i] } } } 4． 效率分析 空間效率：僅用了一個(gè)輔助單元 ， 輔助空間為 O（ 1） 。 時(shí)間效率：向有序表中逐個(gè)插入記錄的操作 ， 進(jìn)行了 n1趟 ， 每趟操作分為比較關(guān)鍵碼和移動(dòng)記錄 ， 而比較的次數(shù)和移動(dòng)記錄的次數(shù)取決于待排序列按關(guān)鍵碼的初始排列 。 最好情況下：即待排序列已按關(guān)鍵字有序 ， 每趟操作只需 1次比較 2次移動(dòng) 。 總比較次數(shù) =n1次 總移動(dòng)次數(shù) =2(n1)次 最壞情況下：即第 j趟操作 ， 插入記錄需要同前面的 j個(gè)記錄進(jìn)行 j次關(guān)鍵碼比較 ， 移動(dòng)記錄的次數(shù)為 j+2次 。 平均情況下：即第 j趟操作 ， 插入記錄大約同前面的 j/2個(gè)記錄進(jìn)行關(guān)鍵碼比較 ， 移動(dòng)記錄的次數(shù)為 j/2+2次 。 直接插入排序的時(shí)間復(fù)雜度為 O(n2)， 輔助空間為 O（ 1） 。 直接插入排序是穩(wěn)定的排序方法 。 直接插入排序最適合待排序關(guān)鍵字基本有序的序列 。 返 回 922 二分插入排序 (Binary Insertong Sort) 1． 基本思想 直接插入算法雖然簡(jiǎn)單 ， 但當(dāng)記錄數(shù)量 n很大時(shí) ， 則比較次數(shù)將大大增加 ， 對(duì)于有序表 （ 限于順序存儲(chǔ)結(jié)構(gòu) ） ， 為了減少關(guān)鍵字的比較次數(shù) ， 可采用二分插入排序 。 二分插入排序的基本思想是：用二分查找法在
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1