




下載本文檔
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、大連理工大學(xué)實(shí)驗(yàn)預(yù)習(xí)報(bào)告學(xué)院(系): 電信 專業(yè): 班級(jí): 姓 名: 學(xué)號(hào): 組: _ 實(shí)驗(yàn)時(shí)間: 實(shí)驗(yàn)室: 實(shí)驗(yàn)臺(tái): 指導(dǎo)教師簽字: 成績(jī): 實(shí)驗(yàn)名稱Merge sort一、 實(shí)驗(yàn)?zāi)康暮鸵?一)、實(shí)驗(yàn)?zāi)康腄esign the merge sort algorithm and implement it in C language設(shè)計(jì)歸并排序算法并于C語(yǔ)言實(shí)現(xiàn)。(二)、實(shí)驗(yàn)要求Requirements:1) Analyze the time complexity of your algorithm2) Submit the document explaining your algorithm
2、as well as the source code. 要求:1) 分析算法的時(shí)間復(fù)雜度。2) 提交的文檔中說(shuō)明你的算法和源代碼。二、實(shí)驗(yàn)原理歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。首先考慮下如何將將二個(gè)有序數(shù)列合并。這個(gè)非常簡(jiǎn)單,只要從比較二個(gè)數(shù)列的第一個(gè)數(shù),誰(shuí)小就先取誰(shuí),取了后就在對(duì)應(yīng)數(shù)列中刪除這個(gè)數(shù)。然后再進(jìn)行比較,如果有數(shù)列為空,那直接將另一個(gè)數(shù)列的數(shù)據(jù)依次取出即可解決了上面的合并有序數(shù)列問(wèn)題,再來(lái)看歸并排序,其的基本思路就是將數(shù)組分成二組A,B,如果這二組組內(nèi)的數(shù)據(jù)都是有序的,那么就可以很方便的將
3、這二組數(shù)據(jù)進(jìn)行排序。如何讓這二組組內(nèi)數(shù)據(jù)有序了?可以將A,B組各自再分成二組。依次類推,當(dāng)分出來(lái)的小組只有一個(gè)數(shù)據(jù)時(shí),可以認(rèn)為這個(gè)小組組內(nèi)已經(jīng)達(dá)到了有序,然后再合并相鄰的二個(gè)小組就可以了。這樣通過(guò)先遞歸的分解數(shù)列,再合并數(shù)列就完成了歸并排序。大連理工大學(xué)實(shí)驗(yàn)報(bào)告學(xué)院(系): 電信 專業(yè): 電創(chuàng) 班級(jí): 1501 姓 名: 陳曉牛津 學(xué)號(hào): 組: _ 實(shí)驗(yàn)時(shí)間: 2017/4/18 實(shí)驗(yàn)室: 實(shí)驗(yàn)臺(tái): 指導(dǎo)教師簽字: 成績(jī): 實(shí)驗(yàn)名稱Merge sort一、 算法分析歸并組合功能:用二分檢索查找的方法采用從低部分,高部分進(jìn)行查找建立一個(gè)新的數(shù)組,將小的數(shù)放入新的數(shù)組中。 歸并排序功能;利用遞歸進(jìn)
4、行排序,先查找中點(diǎn)位置,再對(duì)前部分查找,然后后部分,將小的數(shù)據(jù)放入新的數(shù)組二、 關(guān)鍵代碼及注釋void mergesort(int *a,int left,int right)int mid; if(left right) /* 分組條件 */ mid = (left + right)/2; /* 取中點(diǎn) */ mergesort(a,left,mid); /* 左邊分組 */ mergesort(a,mid+1,right); /* 右邊分組 */ partition(left,mid,right); /* 歸并函數(shù)*/三、 運(yùn)行結(jié)果四、 代碼#includeint a=70,66,88,7
5、0,45,90,33,66,70,22,11,90,11,90,11,90,k = 0;int i;void mergesort(int *a, int left, int right);void partition(int left, int mid, int right);int main()printf(要排序的數(shù)組為:n); /* 輸出要排序的數(shù) */ for(i = 0; ai != NULL; i+) printf(%4d,ai);printf(n); mergesort(a,0,15); /* 歸并排序 */ printf(則結(jié)果為:n); for(i = 0; ai != NU
6、LL; i+) /* 經(jīng)過(guò)排序之后輸出數(shù)組a */ printf(%4d,ai);printf(n);void mergesort(int *a,int left,int right)int mid; if(left = m & l mid+1) /* 終止條件為數(shù)組元素用盡 */ if(al am) /* 如果左邊的小,則將左邊的元素賦值給b */ bh+ = al+; else /* 否則將右邊元素賦值給b */ bh+ = am+; if(right m) /* 如果右邊的元素用完,則將左邊的元素全部賦值給數(shù)組b,完成一趟排序 */ for(; l mid) /* 如果是左邊的用完,則同理將右邊的全部賦值給數(shù)組b */ for(; m = right; m+) bh+ = am; for(; left = right; left+) /* 完成歸并,將數(shù)組b復(fù)制給數(shù)組a, 控制變量尤為重要 */ aleft = bj+;printf
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 項(xiàng)目共建合同協(xié)議
- 嚴(yán)琦的離婚賠償合同
- 智能辦公設(shè)備采購(gòu)合同書(shū)
- 建筑設(shè)計(jì)委托合同范本
- 建筑設(shè)計(jì)服務(wù)合同條款
- 【安永】2025靈活應(yīng)對(duì)變局重新平衡風(fēng)險(xiǎn)管理優(yōu)先事項(xiàng)研究報(bào)告
- Brand KPIs for pet supply online shop Time for Paws in the United Kingdom-外文版培訓(xùn)課件(2025.2)
- 幼兒表演性舞蹈《邊走邊唱》
- 人教版數(shù)學(xué)一年級(jí)下冊(cè)-05認(rèn)識(shí)人民幣-01簡(jiǎn)單的計(jì)算-教學(xué)反思03(4篇)教案
- 2025年深圳地鐵某區(qū)間土建工程勞務(wù)分包總價(jià)承包合同
- 無(wú)機(jī)保溫砂漿外墻外保溫系統(tǒng)施工工藝課件
- 產(chǎn)品追溯記錄表
- 高三二輪復(fù)習(xí):產(chǎn)業(yè)轉(zhuǎn)移以富士康的企業(yè)轉(zhuǎn)移為例課件
- 政府信息資源管理
- 中小微企業(yè)劃型證明
- 西南交大區(qū)段站工作組織課程設(shè)計(jì)2018
- 《監(jiān)察機(jī)關(guān)監(jiān)督執(zhí)法工作規(guī)定》測(cè)試題試題含答案
- Q∕GDW 12154-2021 電力安全工器具試驗(yàn)檢測(cè)中心建設(shè)規(guī)范
- 初中文言文專項(xiàng)訓(xùn)練十篇(含答案)
- 煤礦頂板事故防治(1)
- 漏電保護(hù)器試跳記錄表
評(píng)論
0/150
提交評(píng)論