數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序

上傳人:da****ge 文檔編號:59536675 上傳時間:2022-03-03 格式:DOC 頁數(shù):10 大?。?16KB
收藏 版權(quán)申訴 舉報 下載
數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序_第1頁
第1頁 / 共10頁
數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序_第2頁
第2頁 / 共10頁
數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序_第3頁
第3頁 / 共10頁

下載文檔到電腦,查找使用更方便

16 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序》由會員分享,可在線閱讀,更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語言版) 第9章 排序(10頁珍藏版)》請在裝配圖網(wǎng)上搜索。

1、第9章 內(nèi)部排序排序:調(diào)整記錄表中記錄次序,使之按關(guān)鍵值有序(增序)。記錄表結(jié)構(gòu):SeqList類內(nèi)部排序記錄集全部在內(nèi)存中(戰(zhàn)術(shù)問題)外部排序記錄集部分在內(nèi)存中,排序過程中,需訪問外存(戰(zhàn)略問題) 穩(wěn)定性:關(guān)鍵值相同的記錄,排序前后的相對次序不變。排序前排序后5 1 4 3 41 3 4 4 5穩(wěn)定排序1 3 4 4 5不穩(wěn)定排序 1 插入排序 思路:起源于數(shù)據(jù)陸續(xù)達(dá)到的思路,摸牌的行為。1.1 直接插入1.1.1 算法思路與步驟設(shè)已存在一個有序子序列;每趟將一個記錄按關(guān)鍵值大小插入到有序子序列中。初始化時,有序子序列只有一個記錄;n-1趟后,有序子序列有n個記錄。初始21254925*81

2、6第1趟21254925*816第2趟21254925*816第3趟212525*49816第4趟8212525*4916第5趟816212525*491.1.2 算法實現(xiàn)/直接插入排序template void SeqList:InsertSort() int n=m_Data.size(); for(int i=1; i=0 & m_Datajtmp; j-) m_Dataj+1=m_Dataj; / 記錄移1位 m_Dataj+1=tmp; 1.1.3 性能分析 屬于穩(wěn)定排序。時間復(fù)雜度是O(n2)。 KCN:關(guān)鍵值比較次數(shù) RMN:記錄移動次數(shù)比較移動最好情況記錄集有序1次/趟=KCN

3、=n-12次/趟=RMN=2(n-1)最壞情況記錄集逆序i次/趟=KCN=n(n-1)/2i+2次/趟=RMN=(n+4)(n-1)/21.2 希爾排序發(fā)明人:D.L.Shell,發(fā)明于1959年。1.2.1 算法思路與步驟直接插入排序的缺點:每個記錄被一步一步地挪到目標(biāo)位置。將記錄較快地挪到目標(biāo)位置的方法:加大步長。僅僅加大步長的值,可行嗎?縮小增量法:最后一次的步長一定為1。 希爾排序:將記錄序列按某個步長分成若干子序列;分別對各子序列排序。步長的取值方法之一:n/2,n/4,8,4,2,1。初始561748329第1趟步長=4461258379第2趟步長=2123647589第3趟步長=

4、11234567891.2.2 算法實現(xiàn)template void SeqList:ShellSort() int n=m_Data.size(); for(int step=n/2; step0; step=step/2) for(int i=step; i=0 & m_Datajtmp; j=j-step) m_Dataj+step = m_Dataj; / 記錄移step位 m_Dataj+step=tmp; 1.2.3性能分析 屬于不穩(wěn)定排序。(各子序列彼此獨立的交換) 時間復(fù)雜度:O(n1.5)O(n1.3)。第9章 內(nèi)部排序3 選擇排序思路:“比較”比“賦值”速度快得多3.1 直接

5、選擇排序3.1.1 算法思路與步驟 每趟:在剩余序列中找到最小值,將之交換到目標(biāo)位置。 n-1趟選出n-1個極值,置于相應(yīng)目標(biāo)位置。初始561748329第1趟165748329第2趟1257483693.1.2 算法實現(xiàn)template void SeqList:SelectSort() int n=m_Data.size(); for(int i=0; in-1; i+) int min_i=i; for(int j=i+1; jn; j+) if(m_Datajm_Datamin_i) min_i=j; if(i!=min_i) T tmp=m_Datai; m_Datai=m_Data

6、min_i; m_Datamin_i=tmp; 3.1.3 性能分析 時間復(fù)雜度:O(n2) 空間復(fù)雜度:O(1) 穩(wěn)定性:不穩(wěn)定。示例:排序前3 4 5 3 1 一趟后1 4 5 3 33.1.4 擴(kuò)展思考 減少移動記錄的方法:采用靜態(tài)鏈表結(jié)構(gòu)。 示例:普通的直接選擇排序 初始56314第1趟16354 例:基于靜態(tài)鏈表的直接選擇排序 下標(biāo)012345初始5631412345-1第1趟5631445312-1第4趟5631442-15313.2 樹排序3.2.1 算法思路減少比較次數(shù)的方法:錦標(biāo)賽的賽制。選出冠軍的過程:(比較次數(shù)=n-1)選出亞軍的方法:將冠軍值改為。(比較次數(shù)=log2n

7、)3.2.2 性能分析時間復(fù)雜度: O(nlog2n)空間復(fù)雜度: O(n)3.3 堆排序3.3.1 堆的定義60年代Williams首先提出堆排序算法。 有n個記錄的序列,其關(guān)鍵值序列為(K0,K1,Kn-1) 若2i+1n,則有Ki=K2i+1 若2i+2n,則有Ki=K2i+2本質(zhì):將序列當(dāng)作完全二叉樹的順序存儲形式。 每個分支結(jié)點的關(guān)鍵值 = 其左右孩子結(jié)點的關(guān)鍵值稱為小根堆。3.3.2 建堆方法 建堆是一個依次調(diào)整結(jié)點的過程。 從簡單的事做起:從最后一個分支結(jié)點開始調(diào)整!初始情形調(diào)整結(jié)點(i=3)3,4,5,1,6,8,2,73,4,5,1,6,8,2,7調(diào)整結(jié)點(i=2)調(diào)整結(jié)點(

8、i=1)3,4,2,1,6,8,5,73,1,2,4,6,8,5,7調(diào)整結(jié)點(i=0)1,3,2,4,6,8,5,73.3.3 堆排序方法 堆排序是n-1次交換、調(diào)整結(jié)點的過程。 第1次交換第1次調(diào)整7,3,2,4,6,8,5,(1)2,3,5,4,6,8,7,(1)第2次交換第2次調(diào)整7,3,5,4,6,8,(2,1)3,4,5,7,6,8,(2,1)3.3.4 堆排序的實現(xiàn)template void SeqList:HeapSort() int n=m_Data.size(); for(int i=n/2-1; i=0; i-) HeapShift(i,n-1); for(i=n-1; i

9、0; i-) T tmp=m_Data0; m_Data0=m_Datai; m_Datai=tmp; HeapShift(0,i-1); / 調(diào)整范圍:m_Datarootm_Databottomtemplate void SeqList:HeapShift(int root,int bottom) T tmp=m_Dataroot; int ch_i=2*root+1; while(ch_i=bottom) if(ch_i+1m_Datach_i+1) ch_i+; / ch_i是左右孩子中較小者的下標(biāo) if(m_Datach_i = tmp) break; m_Dataroot = m_Datach_i; root=ch_i; ch_i=2*root+1; m_Dataroot=tmp;3.3.5 性能分析時間復(fù)雜度: O(nlog2n) 其中:建堆O(n),每次調(diào)整O(log2n)空間復(fù)雜度: O(1) 穩(wěn)定性:不穩(wěn)定排序。示例:2個3最初的位置,誰先誰后? 直觀的經(jīng)驗:比賽分組不同,結(jié)果有差異。 最糟情形:針對基本有序序列的排序。試題:一組記錄的關(guān)鍵值為(4,7,5,2,3,8),利用堆排序算法建立的初始堆為 C 。 A、2,4,5,7,3,8B、4,2,5,7,3,8 C、2,3,5,7,4,8D、8,3,5,7,4,2

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!