


版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、學(xué)號(hào)2014-2015學(xué)年第2學(xué)期高級(jí)語言程序設(shè)計(jì)課程設(shè)計(jì)報(bào)告題目:排序算法指導(dǎo)教師:計(jì)算機(jī)與信息工程系2015年3月26日引言 1需求分析 1第一章程序內(nèi)容及要求 11.1 冒泡排序 11.2 選擇排序 21.3 插入排序 3第二章概要設(shè)計(jì) 42.1冒泡排序 42.2選擇排序 52.3插入排序 6第三章程序的比較及其應(yīng)用 73.1時(shí)間復(fù)雜度 73.2空間復(fù)雜度 73.3穩(wěn)定程度 73.4應(yīng)用及其改進(jìn) 8第四章程序設(shè)計(jì)結(jié)果 9附錄 9參考文獻(xiàn) 13引言伴隨著社會(huì)的發(fā)展,數(shù)據(jù)也變得越來越龐大。如何將龐大的數(shù)據(jù)進(jìn)行很好 的排序,使用戶更加方便的查找資料,成了一件越來越重要的問題。對(duì)于程序員 來說,
2、這將是一個(gè)挑戰(zhàn)。經(jīng)常查找資料的朋友都會(huì)知道,面對(duì)海量的資料,如果其查找資料沒有進(jìn) 行排序,那么其查找資料將會(huì)是一家非常痛苦的事情。 針對(duì)這一問題,我們自此 通過一個(gè)課程設(shè)計(jì)來解決它。理論上排序算法有很多種,不過本課程設(shè)計(jì)只涉及到三種算法。這三種算 法包括:冒泡排序,選擇排序,直接插入排序。本課程設(shè)計(jì)通過對(duì)這三種算法的運(yùn)行情況進(jìn)行對(duì)比,選擇最優(yōu)秀的算法出來。希望通過我的努力能解決一些問題,帶來一些方便。需求分析本課程題目是排序算法的實(shí)現(xiàn),由于各方面的原因,本科程設(shè)計(jì)一共需要 設(shè)計(jì)三種排序算法。這三種算法包括:冒泡排序,選擇排序,直接插入排序。三 種排序算法各有獨(dú)到之處,因此我們要通過各種調(diào)試分析
3、來比較其優(yōu)劣長(zhǎng)短。由于使用的調(diào)試軟件及操作系統(tǒng)不一樣。因此個(gè)別程序在不同的軟件上可 能會(huì)報(bào)錯(cuò)。本課程軟件運(yùn)行的的操作系統(tǒng)為 Windows764位操作系統(tǒng)。所使用的軟件 為 Microsoft Visual C+6.0 以及 Turbo C2.0第一章 程序內(nèi)容及要求1.1冒泡排序冒泡排序(Bubble Sort,臺(tái)灣譯為:泡沫排序或氣泡排序)是一種簡(jiǎn)單 的排序算法。它重復(fù)地走訪過要排序的數(shù)列,一次比較兩個(gè)元素,如果他們的順 序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換, 也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交 換慢慢“浮”到數(shù)列的頂端,
4、故名。冒泡排序(BubbleSort )的基本概念是:依次比較相鄰的兩個(gè)數(shù),將小數(shù) 放在前面,大數(shù)放在后面。即在第一趟:首先比較第1個(gè)和第2個(gè)數(shù),將小數(shù)放前,大數(shù)放后。然后比較第2個(gè)數(shù)和第3個(gè)數(shù),將小數(shù)放前,大數(shù)放后,如此繼 續(xù),直至比較最后兩個(gè)數(shù),將小數(shù)放前,大數(shù)放后。至此第一趟結(jié)束,將最大的 數(shù)放到了最后。在第二趟:仍從第一對(duì)數(shù)開始比較(因?yàn)榭赡苡捎诘?個(gè)數(shù)和第 3個(gè)數(shù)的交換,使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)),將小數(shù)放前,大數(shù)放后,一 直比較到倒數(shù)第二個(gè)數(shù)(倒數(shù)第一的位置上已經(jīng)是最大的),第二趟結(jié)束,在倒 數(shù)第二的位置上得到一個(gè)新的最大數(shù)(其實(shí)在整個(gè)數(shù)列中是第二大的數(shù))。如此 下去,重復(fù)以上
5、過程,直至最終完成排序。用二重循環(huán)實(shí)現(xiàn),外循環(huán)變量設(shè)為i, 內(nèi)循環(huán)變量設(shè)為j。假如有10個(gè)數(shù)需要進(jìn)行排序,則外循環(huán)重復(fù) 9次,內(nèi)循環(huán) 依次重復(fù)9,8,. ,1次。每次進(jìn)行比較的兩個(gè)元素都是與內(nèi)循環(huán)j有關(guān)的,它們可以分別用aj和aj+1標(biāo)識(shí),i的值依次為1,2,.,9,對(duì)于每一個(gè)i,j的值依次為1,2,.10-i。冒泡排序算法的性能1.2選擇排序每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素,順序放 在已排好序的數(shù)列的最后,直到全部待排序的數(shù)據(jù)元素排完。選擇排序是不穩(wěn)定的排序方法?;舅枷耄簄個(gè)記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果: 初始狀態(tài):無序區(qū)為R仁n,有
6、序區(qū)為空。 第1趟排序 在無序區(qū)R仁n中選出關(guān)鍵字最小的記錄 Rk,將它與無序區(qū) 的第1個(gè)記錄R1交換,使R1.1和R2.n分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1 個(gè)的新無序區(qū)。第i趟排序 第i趟排序開始時(shí),當(dāng)前有序區(qū)和無序區(qū)分別為R1.i-1和R(1< i < n-1)。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄Rk,將它與無序區(qū)的第1個(gè)記錄R交換,使R1.i和R分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新 無序區(qū)。這樣,n個(gè)記錄的文件的直接選擇排序可經(jīng)過 n-1趟直接選擇排序得到有序結(jié)果。選擇排序法的第一層循環(huán)從起始元素開始選到倒數(shù)第二個(gè)元素,主要是在每
7、次進(jìn) 入的第二層循環(huán)之前,將外層循環(huán)的下標(biāo)賦值給臨時(shí)變量,接下來的第二層循環(huán)中,如果發(fā)現(xiàn)有比這個(gè) 最小位置處的元素更小的元素,則將那個(gè)更小的元素的下標(biāo)賦給臨時(shí)變量,最后,在二層循環(huán)退出后,如果 臨時(shí)變量改變,則說明,有比當(dāng)前外層循環(huán)位置更小的元素,需要將這兩個(gè)元素交換1.3 插入排序有一個(gè)已經(jīng)有序的數(shù)據(jù)序列,要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一 個(gè)數(shù),但要求插入后此數(shù)據(jù)序列仍然有序,這個(gè)時(shí)候就要用到一種新的排序方法-插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù) 據(jù)中,從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù),算法適用于少量數(shù)據(jù)的排序, 時(shí)間復(fù)雜度為0(nA2)。是穩(wěn)定的排序
8、方法。插入算法把要排序的 數(shù)組分成兩部 分:第一部分包含了這個(gè)數(shù)組的所有元素,但將最后一個(gè)元素除外(讓數(shù)組多一個(gè) 空間才有插入的位置),而第二部分就只包含這一個(gè)元素(即待插入元素)。在第 一部分排序完成后,再將這個(gè)最后元素插入到已排好序的第一部分中。插入排序的基本思想是:每步將一個(gè)待排序的紀(jì)錄,按其關(guān)鍵碼值的大小插入前面已經(jīng)排 序的文件中適當(dāng)位置上,直到全部插入完為止。1從有序數(shù)列和無序數(shù)列a2,a3,an開始進(jìn)行排序;2.處理第i個(gè)元素時(shí)(i=2,3,n),數(shù)列a1,a2,ai-1是已有序 的,而數(shù)列ai,ai+1 ,an是無序的。用ai與ai-1 ,a i-2,al進(jìn)行比 較,找出合適的位
9、置將ai插入;3重復(fù)第二步,共進(jìn)行n-i次插入處理,數(shù)列全部有序。第二章概要設(shè)計(jì)2.1冒泡排序在要排序的一組數(shù)中,對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù),自上而下對(duì) 相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整,讓較大的數(shù)往下沉,較小的往上冒。即:每 當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí),就將它們互換。for(i=0;i<10;i+)第一輪循環(huán),輸入十個(gè)數(shù)據(jù)。scanf( “%d,&ai);printf( “n ” );for(j=0;j<9;j+)挨個(gè)判斷輸入的書的大小,第二輪循環(huán)for(i=0;i<9-j;i+)if(ai>ai+1t=ai;進(jìn)行數(shù)的調(diào)換,把大的數(shù)據(jù)
10、調(diào)到后面。ai=ai+1;ai+1=t;2.2選擇排序簡(jiǎn)單選擇排序,每趟循環(huán)只能確定一個(gè)元素排序后的定位。我們可以考慮改進(jìn)為每趟循環(huán)確定兩個(gè)元素(當(dāng)前趟最大和最小記錄)的位置,從而減少排序所需的循環(huán)次數(shù)。改進(jìn)后對(duì) n個(gè)數(shù)據(jù)進(jìn)行排序,最多只需進(jìn)行n/2趟循環(huán)即i=lpn=lO;t e m戸=列j) alj)-a(i) aflj-tamp min >0ji+-為數(shù)組a的元素個(gè)數(shù)void select_sort(i nt a,i nt n)/n/進(jìn)行N-1輪選擇for(i nt i=0; i<n-1; i+) int min_in dex = i;/ 找出第i小的數(shù)所在的位置for(i
11、nt j=i+1; j< n; j+)if(aj < amin_in dex)min_i ndex = j;/ 將第i小的數(shù),放在第i個(gè)位置;如果剛好,就不用交換if( i != min_i ndex)int temp = ai;ai = amin_in dex;amin_i ndex = temp;2.3插入排序?qū)⒁粋€(gè)記錄插入到已排序好的有序表中,從而得到一個(gè)新,記錄數(shù)增1的有序表。即:先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列,然后從第 2個(gè)記錄逐個(gè)進(jìn)行插入,直至整個(gè)序列有序?yàn)橹?A-r34>3AJ5從數(shù)組中的第二個(gè)元素開始int temp;for (i nt i = 1
12、; i < len gth; +i) /temp = arri; /記錄當(dāng)前的元素int j = i - 1;while (j >= 0 && temp < arrj) /將當(dāng)前元素與之前的已經(jīng)排序好的序列元素進(jìn)行挨個(gè)比較arrj + 1 = arrj; /已經(jīng)排序好的序列整體向后移動(dòng)T;arrj + 1 = temp; /插入當(dāng)前的元素第三章程序的比較及其應(yīng)用3.1時(shí)間復(fù)雜度冒泡排序算法的最差時(shí)間復(fù)雜度為 0(n2),平均時(shí)間復(fù)雜度為0(n2)。選 擇排序算法的最差時(shí)間復(fù)雜度為 0(n2),平均時(shí)間復(fù)雜度為0(n2)。插入排序算法 的最差時(shí)間復(fù)雜度為0(n2
13、),平均時(shí)間復(fù)雜度為0(n2)。冒泡排序和插入排序時(shí)間 復(fù)雜度最好的情況下是 0(n),而選擇排序時(shí)間復(fù)雜度最好的情況下是0(n2)。從時(shí)間復(fù)雜度比較來看。選擇排序的時(shí)間復(fù)雜度在以下情況下是沒有冒泡排序和插 入排序的好。3.2空間復(fù)雜度冒泡排序,選擇排序,以及插入排序是空間復(fù)雜度都是0(1)。從空間復(fù)雜度來看,三者也沒有什么可以區(qū)分開來的。并不能直觀的看出優(yōu)劣。3.3穩(wěn)定程度冒泡排序和插入排序的穩(wěn)定程度都是比較穩(wěn)定的,只有選擇排序是不穩(wěn) 定的。那么綜合上面的比較來看,選擇排序是最不好的,而冒泡排序以及插入排 序是比較好的。冒泡排序是最慢的,但是也是最容易懂得。插入排序是比較快的, 但是對(duì)于自身
14、的能力有一定的要求。當(dāng)然,這只是相對(duì)而言3.4應(yīng)用及其改進(jìn)三種排序算法都可以應(yīng)用于一些簡(jiǎn)單排列數(shù)據(jù)的程序。也可以作為C語言初學(xué)者的練手的課題。對(duì)于我們學(xué)習(xí)C語言也是一個(gè)不小的幫助。同時(shí)可以 加深我們對(duì)于循環(huán)和數(shù)組的理解及其應(yīng)用。 同時(shí)我們可以對(duì)冒泡排序進(jìn)行一點(diǎn)點(diǎn) 的改進(jìn),使其更加的完善。冒泡算法的改進(jìn),當(dāng)排序的數(shù)據(jù)比較多時(shí)排序的時(shí)間會(huì)明顯延長(zhǎng)。改進(jìn) 方法:快速排序:具體做法:任意選取某一記錄(通常取第一個(gè)記錄),比較其 關(guān)鍵字與所有記錄的關(guān)鍵字,并將關(guān)鍵字比它小的記錄全部放在它的前面,將比它大的記錄均存放在它的后面,這樣,經(jīng)過一次排序之后,可將所有記錄以該記 錄所在的分界點(diǎn)分為兩部分,然后分別
15、對(duì)這兩部分進(jìn)行快速排序,直至排序完。 在冒泡排序中,一趟掃描有可能無數(shù)據(jù)交換,也有可能有一次或多次數(shù)據(jù)交換, 在傳統(tǒng)的冒泡排序算法及近年來的一些改進(jìn)的算法中,只記錄一趟掃描有無數(shù)據(jù) 交換的信息,對(duì)數(shù)據(jù)交換發(fā)生的位置信息則不予處理。為了充分利用這一信息, 可以在一趟全局掃描中,對(duì)每一反序數(shù)據(jù)對(duì)進(jìn)行局部冒泡排序處理, 稱之為局部 冒泡排序。局部冒泡排序與冒泡排序算法具有相同的時(shí)間復(fù)雜度,并且在正序和逆序的情況下,所需的關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)完全相同。由于局部冒泡排序和冒泡排序的數(shù)據(jù)移動(dòng)次數(shù)總是相同的, 而局部冒泡排序所需關(guān)鍵字的比較次 數(shù)常少于冒泡排序,這意味著局部冒泡排序很可能在平均比較次數(shù)
16、上對(duì)冒泡排序 有所改進(jìn),當(dāng)比較次數(shù)較少的優(yōu)點(diǎn)不足以抵消其程序復(fù)雜度所帶來的額外開銷, 而當(dāng)數(shù)據(jù)量較大時(shí),局部冒泡排序的時(shí)間性能則明顯優(yōu)于冒泡排序。第四章 程序設(shè)計(jì)結(jié)果插入排序算法的結(jié)果選擇排序算法的結(jié)果冒泡排序算法的結(jié)果附錄冒泡排序:#i nclude<stdio.h>void mai n()int a10;Int i,j,t;printf( “ in put 10 nu mbers :n”);for(i=0;i<10;i+) scanf( “%d,&ai);printf(“n ”);for(j=0;j<9;j+)for(i=0;i<9-j;i+)if(a
17、i>ai+1t=ai;ai=ai+1;ai+1=t;printf(“ the sorted nu mbers :n”printf(“%d ,ai);printf(“n ”);選擇排序:#i nclude<stdio.h>#i nclude<stdlib.h>#defi ne N 8void select_sort(i nt a,i nt n);/選擇排序?qū)崿F(xiàn)為數(shù)組a的元素個(gè)數(shù)void select_sort(i nt a,i nt n)/n/ 進(jìn)行N-1輪選擇for(i nt i=0; i<n-1; i+)int min_in dex = i;/ 找出第i小
18、的數(shù)所在的位置for(i nt j=i+1; j< n; j+)if(aj < amin_in dex)min_i ndex = j;/ 將第i小的數(shù),放在第i個(gè)位置;如果剛好,就不用交換if( i != min_i ndex)int temp = ai;ai = amin_in dex;amin_i ndex = temp;int mai n()int numN = 89, 38, 11, 78, 96, 44, 19, 25;select_sort (num, N);for(i nt i=0; i<N; i+)prin tf("%d ", nu mi);prin tf("n&qu
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)字化轉(zhuǎn)型對(duì)文化創(chuàng)意產(chǎn)業(yè)的推動(dòng)作用
- 油菜高產(chǎn)種植技術(shù)的創(chuàng)新與應(yīng)用
- 2025年托福口語綜合任務(wù)5-6專項(xiàng)突破:歷年真題詳解與技巧提煉
- 牦牛養(yǎng)殖與可持續(xù)發(fā)展的協(xié)同路徑
- 人工智能推動(dòng)遠(yuǎn)程醫(yī)療服務(wù)的創(chuàng)新發(fā)展
- 民俗文化的跨文化傳播與體驗(yàn)設(shè)計(jì)
- 哲學(xué)的生活智慧
- 春季新品盛宴
- 2025合同范本 物料與采購(gòu)管理系統(tǒng)協(xié)議
- 2025辦公用品購(gòu)銷合同
- 《中式美食鑒賞》課件
- 民航旅客運(yùn)輸試題及答案
- 安全用電宣傳課件初中
- 國(guó)開電大軟件工程形考作業(yè)3參考答案 (一)
- 針對(duì)不同人群的中醫(yī)健康管理方案研究
- 2025年-天津市安全員-B證考試題庫(kù)附答案
- 2025年鐵路列車員(中級(jí))職業(yè)技能鑒定參考試題庫(kù)-上(單選題)
- 游泳館安全知識(shí)培訓(xùn)課件
- 2025年遼寧省撫順市順城區(qū)中考一模歷史試題(原卷版+解析版)
- 自動(dòng)扶梯吊裝方案
- 第5課 弘揚(yáng)勞動(dòng)精神、勞模精神、工匠精神(教學(xué)設(shè)計(jì)) -【中職專用】中職思想政治《職業(yè)道德與法治》同步教學(xué)教學(xué)設(shè)計(jì)(高教版2023·基礎(chǔ)模塊)
評(píng)論
0/150
提交評(píng)論