排序算法的比較

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)排序算法的比較1課程設(shè)計(jì)名稱 排序算法的比較 概述排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作。它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。內(nèi)部排序算法主要分為5 大類，有十二個(gè)算法。插入排序類、交換排序類、選擇排序類、歸并排序類和基數(shù)排序類。算法主要包括：插入排序、折半插入排序、選擇排序、冒泡排序、希爾排序、快速排序、堆排序、歸并排序、基數(shù)排序等。2使用工具軟件 Microsoft Visual C+ 6.03 課程設(shè)計(jì)內(nèi)容簡介3.1課程設(shè)

2、計(jì)內(nèi)容掌握各種排序算法（直接插入排序、冒泡排序、快速排序、簡單選擇排序）的思路核比較他們之間的優(yōu)劣。3.2 基本要求1.任意性：系統(tǒng)首先生成1000個(gè)隨機(jī)整數(shù)，然后分別用不同的排序方法對其進(jìn)行升序排序，給出每種方法的比較次數(shù)或所用時(shí)間2.友好性：界面要友好，輸入有提示，盡量展示人性化3.可讀性：源程序代碼清晰、有層次 4.健壯性：用戶輸入非法數(shù)據(jù)時(shí)，系統(tǒng)要及時(shí)給出警告信息3.3 課程設(shè)計(jì)思想 程序設(shè)計(jì)的總體思路：首先構(gòu)建main()函數(shù)，根據(jù)題目的要求，再分別構(gòu)建四個(gè)排序函數(shù)：冒泡排序函數(shù)（long Bubblesort(long R, long n)）、選擇排序函數(shù)（long selects

3、ort(long R,long n)）、直接插入排序函數(shù)（long insertsort(long R, long n)）和快速排序函數(shù)（void QuickSort(long R,long n)）。為了使程序具有可讀性和層次感，建立一個(gè)導(dǎo)航函數(shù)（void DaoHang()）和操作函數(shù)（void operate(long a, long n)），其中，void DaoHang()用來告知用戶程序的操作流程，void operate(long a, long n)用來接收用戶不同的選擇，從而調(diào)用其它函數(shù)。3.4 程序分析3.4.1 存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)（如圖1）示意圖a0a1a2a3a4圖1

4、3.4.2 關(guān)鍵算法分析關(guān)鍵算法1實(shí)現(xiàn)四種算法的基本排序功能1冒泡排序：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序記錄為止。實(shí)現(xiàn)過程（如圖2）。對于數(shù)組（21 25 49 16 08）。初態(tài)：2125491608第一趟：2125160849第二趟：2116082549第三趟：1608212549第四趟：0816212549圖22選擇排序：從待排序的記錄序列中選擇關(guān)鍵碼最?。ɑ蜃畲螅┑挠涗洸⑺c序列中的第一個(gè)記錄交換位置；然后從不包括第一個(gè)位置上的記錄序列中選擇關(guān)鍵碼最?。ɑ蜃畲螅┑挠涗洸⑺c序列中的第二個(gè)記錄交換位置；如此重復(fù)，直到序列中只剩下一個(gè)記錄為止。實(shí)現(xiàn)過程（如圖3）。

5、對于數(shù)組（21 25 49 16 08）。初態(tài)：2125491608第一趟：0825491621第二趟：0816492521第三趟：0816212549圖33直接插入排序：依次將待排序的序列中的每一個(gè)記錄插入到先前排序好的序列中，直到全部記錄排序完畢。實(shí)現(xiàn)過程（如圖4）。對于數(shù)組（21 25 49 16 08）。初態(tài)：2125491608第一趟：2125491608第二趟：2125491608第三趟：2125491608第四趟：1621254908第五趟：0816212549圖44快速排序：首先選擇一個(gè)基準(zhǔn)，將記錄分割為兩部分，左支小于或等于基準(zhǔn)，右支則大于基準(zhǔn)，然后對兩部分重復(fù)上述過程，直至

6、整個(gè)序列排序完成。實(shí)現(xiàn)過程（如圖5）對于數(shù)組（21 25 49 16 08）。初態(tài)：R0=212125491608highlow第一趟：R0=210825491608highlowR0=210825491625highlowR0=210816491625highlowR0=210816491625lowhigh R0=210816494925highlowR0=21low=high0816214925圖5關(guān)鍵算法二獲取當(dāng)前系統(tǒng)時(shí)間，精確到毫秒，分別在代碼運(yùn)行前后調(diào)用記錄前后時(shí)間，再相減即可得到代碼運(yùn)行時(shí)間。/以冒泡排序?yàn)槔齭tart=(double)clock();/開始 Bubblesort

7、(R, n);end=(double)clock();/結(jié)束Time = (double)(end-start)/CLK_TCK;/相減，精確到毫秒關(guān)鍵算法三：實(shí)現(xiàn)手動(dòng)與計(jì)算機(jī)隨機(jī)雙重輸入。手動(dòng)輸入檢查程序的正確性，計(jì)算機(jī)隨即輸入，可以比較各排序算法的性能。void Rand()/隨機(jī)數(shù)函數(shù)void HandInput()/手動(dòng)輸入函數(shù)關(guān)鍵算法四 糾錯(cuò)功能。在用戶輸入非法數(shù)據(jù)時(shí)，給予警告，并要求用戶重新輸入，不必重啟程序。3.4.3時(shí)間復(fù)雜度與空間復(fù)雜度：理論分析可以得出各種排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度，如下表所示（圖6）：排序方法平均情況最好情況最壞情況輔助空間直接插入排序O(n2)O(

8、n)O(n2)O(1)起泡排序O(n2)O (n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n) O(n)簡單選擇排序O(n2)O(n2)O(n2)O(1)圖63.4.4 選擇排序算法的依據(jù)影響排序的因素有很多，平均時(shí)間復(fù)雜度低的算法并不一定就是最優(yōu)的。相反，有時(shí)平均時(shí)間復(fù)雜度高的算法可能更適合某些特殊情況。同時(shí)，選擇算法還得考慮它的可讀性，以利于軟件的維護(hù)。一般而言，需要考慮的因素有以下4 點(diǎn)：待排序的記錄數(shù)目n 的大小。記錄本身數(shù)據(jù)量的大小，也就是記錄中除關(guān)鍵字外的其他信息量的大小。關(guān)鍵字的結(jié)構(gòu)及其分布情況。對排序穩(wěn)定性的要求。3.5 程序流程圖m

9、ain()輸入0輸入a輸入排序方法輸入錯(cuò)誤輸入錯(cuò)誤判斷手動(dòng)還是隨機(jī)輸入(1,2)?HandInput()(手動(dòng)輸入)1Rand();(隨機(jī)輸入)2void DaoHang()void operate()cinai ;/數(shù)據(jù)存儲(chǔ)選擇排序方法Void print()結(jié)束圖73.6 運(yùn)行環(huán)境Microsoft Visual C+ 6.0/WIN32 Console Application3.7運(yùn)行結(jié)果3.7.1當(dāng)手動(dòng)輸入五個(gè)數(shù)據(jù)時(shí)，運(yùn)行結(jié)果（如圖8）圖83.7.2當(dāng)選擇隨機(jī)數(shù)時(shí)，運(yùn)行結(jié)果(如圖9)圖93.8 得意之處得意之處1將時(shí)間精確到毫秒，使得實(shí)驗(yàn)結(jié)果更容易觀察比較。代碼如下（冒泡排序?yàn)槔簊

10、tart=(double)clock();degree = Bubblesort(R, n);end=(double)clock();Time = (double)(end-start)/;其中CLK_TCK值為1000，即將時(shí)間精確到毫秒（圖10）。圖10得意之處2將排序過程的每一趟輸出，并且將已排好序的用中括號括起來，這樣以來，可以直接看出排序過程是否正確以及深入了解排序過程的每一步。如：對于冒泡排序（圖11）圖11得意之處3冒泡排序算法中，運(yùn)用做標(biāo)記的方法，使得排序得到正確結(jié)果后，便停止做不必要的循環(huán)。代碼如下while(i1)long lastExchangeIndex=1;/表示已經(jīng)

11、有序for(long j=1;ji;j+)if(Rj+1Rj)long t=Rj;Rj=Rj+1;Rj+1=t; BT+;lastExchangeIndex=j;/記下進(jìn)行的位置i=lastExchangeIndex;/本趟進(jìn)行過交換的最后一個(gè)記錄的位置4 課程設(shè)計(jì)中目前存在問題1交換次數(shù)統(tǒng)計(jì)不夠精確。2無論時(shí)間還是移動(dòng)次數(shù)，應(yīng)該有一個(gè)對比結(jié)果，不能只是羅列出來。3對于快速排序，存在兩個(gè)問題。其一，不能兩邊同時(shí)進(jìn)行排序，使得排序趟數(shù)增加；其二，沒能格式化輸出，使得輸出不清晰，不美觀。5 自我感受1在初期構(gòu)思代碼的時(shí)候，首先構(gòu)造了各種算法的基本實(shí)現(xiàn)代碼，已經(jīng)能夠?qū)崿F(xiàn)四種排序的基本功能，并且測試無

12、誤。后來考慮能否優(yōu)化本程序，首先考慮到測試算法的需求，需要大量隨機(jī)數(shù)，因?yàn)樵鎏砹穗S機(jī)函數(shù)發(fā)生函數(shù)，滿足各種測試條件的需求。之后考慮如何能簡化代碼以實(shí)現(xiàn)多達(dá)四種排序算法的簡單調(diào)用和性能指標(biāo)統(tǒng)計(jì)、算法時(shí)間的精確而簡易的統(tǒng)計(jì)、算法移動(dòng)次數(shù)和比較次數(shù)的精確統(tǒng)計(jì)。調(diào)用精確的系統(tǒng)函數(shù)實(shí)現(xiàn)時(shí)間的統(tǒng)計(jì)。此外還添加了一系列優(yōu)化，使得程序的結(jié)構(gòu)變得更加合理，版面風(fēng)格也變得好看，可讀性增強(qiáng)。2程序的優(yōu)化是一個(gè)艱辛的過程，如果只是實(shí)現(xiàn)一般的功能，將變得容易很多，當(dāng)加上優(yōu)化，不論是效率還是結(jié)構(gòu)優(yōu)化，都需要精心設(shè)計(jì)。這次做優(yōu)化的過程中，遇到不少阻力。因而以后要多花力氣學(xué)習(xí)C+編程語言，必須要加強(qiáng)這方面的訓(xùn)練，這樣才能在將

13、編程思想和數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為代碼的時(shí)候能得心應(yīng)手。3這次課設(shè)通過在網(wǎng)上查閱大量資料、程序以及一些學(xué)術(shù)論文，很好的對內(nèi)排序算法進(jìn)行了研究，特別對數(shù)據(jù)結(jié)構(gòu)這門課所學(xué)到的內(nèi)容付諸于實(shí)踐，加深了理解。另外，還學(xué)到了一寫別的方面的知識(shí)。這次課設(shè)做還有許多沒有考慮周到的地方，希望老師指出。6參考文獻(xiàn)1 嚴(yán)蔚敏 吳偉民，數(shù)據(jù)結(jié)構(gòu)（C語言版），北京:清華大學(xué)出版社,2007。2 汪祖柱 沈曉潞，基于C語言實(shí)現(xiàn)的若干排序算法和分析，安徽電氣工程職業(yè)學(xué)院學(xué)報(bào)，第九卷第一期。3 王莉，常用內(nèi)部排序算法的比較與選擇，軟件導(dǎo)刊，2006年1月號。4 趙延惠，排序方法及效率淺析，思茅師范高等?？茖W(xué)校學(xué)報(bào)，第18卷附錄：程序#

14、include #include#include #include #include #define MAX using namespace std;void print(long R,long n)for(int i=1;i=n;i+)coutsetw(4)1)long lastExchangeIndex=1;/表示已經(jīng)有序for(long j=1;ji;j+)if(Rj+1Rj)long t=Rj;Rj=Rj+1;Rj+1=t; BT+;lastExchangeIndex=j;/記下進(jìn)行的位置i=lastExchangeIndex;/本趟進(jìn)行過交換的最后一個(gè)記錄的位置cout第y趟:;y+

15、;for(long x=1;x=i;x+)coutsetw(4)Rx;coutsetw(3)Ri+1;for(x=i+2;x=n;x+)coutsetw(4)Rx;cout;coutendl;return BT;/-/選擇排序/-/static long ST=0;long SelectMinKey(long R,long i,long n)/在 Ri.R.length 中選擇關(guān)鍵字最小的記錄long temp=i;/記錄最小的元素值的位置for(int j=i;jRj)temp=j;/ST+;return temp;long selectsort(long R,long n)long j,i

16、,t;long y=1;int ST=0;for( i=1;in;i+)j = SelectMinKey(R,i,n);/ 在 L.ri.L.length 中選擇關(guān)鍵字最小的記錄if (i!=j) / 與第 i 個(gè)記錄交換t=Ri;Ri=Rj;Rj=t;ST+; cout第y趟: ;y+;for(long x=1;x=i;x+)coutsetw(4)Rx;coutsetw(3)Ri+1;for(x=i+2;x=n;x+)coutsetw(4)Rx;cout;/print(R,n);coutendl;return ST;/-/直接插入排序/-long insertsort(long R, lon

17、g n)long y=1;long IT=0,j;for(long i=2;i=n;+i)if(RiRi-1)R0=Ri;/復(fù)制為哨兵IT=IT+1;for( j=i-1;R0Rj;-j)Rj+1=Rj;/記錄后移IT=IT+1;Rj+1=R0;/插入到正確位置IT=IT+1;cout第y趟: ;y+;coutsetw(4)R1;for(long x=2;x=i;x+)coutsetw(4)Rx;cout;for(x=i+1;x=n;x+)coutsetw(4)Rx;coutendl;return IT;/-/快速排序/-static long QT=0;int Partition (long

18、 R, long low, long high,long n)R0 =Rlow; long pivotkey = Rlow; / 樞軸 QT=QT+2;while (lowhigh) while(low=pivotkey)/ 從右向左搜索- high; Rlow = Rhigh;QT=QT+1;while (lowhigh & Rlow=pivotkey)/ 從左向右搜索+ low; Rhigh = Rlow;QT=QT+1;Rlow =R0; QT=QT+1;return low;/ Partitionvoid quicksort (long R, int low, int high,lon

19、g n,long y)/ 對記錄序列L.rlow.high進(jìn)行快速排序if (low high) / 長度大于1 long pivotloc = Partition(R,low,high,n);/ 對 L.rlow.high 進(jìn)行一次劃分QT=QT+1;cout第y趟:;y+;print(R,pivotloc-1);coutsetw(2)Rpivotloc;cout;for(long x=pivotloc+1;x=n;x+)coutsetw(5)Rx;coutendl;quicksort(R, low, pivotloc-1,n,y); / 對低子序列遞歸排序quicksort(R, pivo

20、tloc+1, high,n,y); / 對高子序列遞歸排序 / QSortvoid QuickSort(long R,long n) long y=1;quicksort(R,1,n,n,y);/-/操作選擇函數(shù)/-void operate(long a, long n)void main();long * R = new long n;time_t start, end;/定義兩個(gè)變量double Time;/排序時(shí)間long degree;/排序次數(shù)char ch;cout ch;switch(ch)case 1:coutn;coutt=您選擇的是冒泡排序=n;for(int i = 1

21、; i =n; i +)/將隨機(jī)數(shù)付給RiRi = ai;start=(double)clock();degree = Bubblesort(R, n);end=(double)clock();Time = (double)(end-start)/CLK_TCK;/print(R,n);cout n;cout 冒泡排序所用時(shí)間：t Time n;cout 冒泡排序交換次數(shù)：t degree n;coutn;operate(a, n);break;case 2:coutn;coutt=您選擇的是選擇排序=n;for(int i = 1; i = n; i +)Ri = ai;start=(dou

22、ble)clock();degree = selectsort(R, n);end=(double)clock();Time = (double)(end-start)/CLK_TCK;/print(R,n);coutn;cout 選擇排序所用時(shí)間：t Time n;cout 選擇排序交換次數(shù)：t degree n;cout n;operate(a, n);break;case 3:coutn;coutt=您選擇的是直接插入排序=n;for(int i=1; i=n; i +)Ri = ai;start=(double)clock();degree = insertsort(R, n);end

23、=(double)clock();Time = (double)(end-start)/CLK_TCK;/print(R,n);coutn;cout 直接插入排序所用時(shí)間： Time n;cout 直接插入排序交換次數(shù)： degree n;cout n;operate(a, n);break;case 4:coutn;coutt=您選擇的是快速排序=n;for(int i=1; i=n; i +)Ri = ai;start=(double)clock();QuickSort(R, n);end=(double)clock();Time = (double)(end-start)/CLK_TCK;coutn;cout 快速排序所用時(shí)間：t Time n;cout 快速排序交換次數(shù)：t QT n;cout n;operate(a, n);break;case a:main();break;de