排序算法的比較

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

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

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

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

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

7、(R, n);end=(double)clock();/結束Time = (double)(end-start)/CLK_TCK;/相減，精確到毫秒關鍵算法三：實現(xiàn)手動與計算機隨機雙重輸入。手動輸入檢查程序的正確性，計算機隨即輸入，可以比較各排序算法的性能。void Rand()/隨機數(shù)函數(shù)void HandInput()/手動輸入函數(shù)關鍵算法四 糾錯功能。在用戶輸入非法數(shù)據(jù)時，給予警告，并要求用戶重新輸入，不必重啟程序。3.4.3時間復雜度與空間復雜度：理論分析可以得出各種排序算法的時間復雜度和空間復雜度，如下表所示（圖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ù)影響排序的因素有很多，平均時間復雜度低的算法并不一定就是最優(yōu)的。相反，有時平均時間復雜度高的算法可能更適合某些特殊情況。同時，選擇算法還得考慮它的可讀性，以利于軟件的維護。一般而言，需要考慮的因素有以下4 點：待排序的記錄數(shù)目n 的大小。記錄本身數(shù)據(jù)量的大小，也就是記錄中除關鍵字外的其他信息量的大小。關鍵字的結構及其分布情況。對排序穩(wěn)定性的要求。3.5 程序流程圖m

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

10、tart=(double)clock();degree = Bubblesort(R, n);end=(double)clock();Time = (double)(end-start)/;其中CLK_TCK值為1000，即將時間精確到毫秒（圖10）。圖10得意之處2將排序過程的每一趟輸出，并且將已排好序的用中括號括起來，這樣以來，可以直接看出排序過程是否正確以及深入了解排序過程的每一步。如：對于冒泡排序（圖11）圖11得意之處3冒泡排序算法中，運用做標記的方法，使得排序得到正確結果后，便停止做不必要的循環(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;/記下進行的位置i=lastExchangeIndex;/本趟進行過交換的最后一個記錄的位置4 課程設計中目前存在問題1交換次數(shù)統(tǒng)計不夠精確。2無論時間還是移動次數(shù)，應該有一個對比結果，不能只是羅列出來。3對于快速排序，存在兩個問題。其一，不能兩邊同時進行排序，使得排序趟數(shù)增加；其二，沒能格式化輸出，使得輸出不清晰，不美觀。5 自我感受1在初期構思代碼的時候，首先構造了各種算法的基本實現(xiàn)代碼，已經(jīng)能夠?qū)崿F(xiàn)四種排序的基本功能，并且測試無

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

13、編程思想和數(shù)據(jù)結構轉(zhuǎn)換為代碼的時候能得心應手。3這次課設通過在網(wǎng)上查閱大量資料、程序以及一些學術論文，很好的對內(nèi)排序算法進行了研究，特別對數(shù)據(jù)結構這門課所學到的內(nèi)容付諸于實踐，加深了理解。另外，還學到了一寫別的方面的知識。這次課設做還有許多沒有考慮周到的地方，希望老師指出。6參考文獻1 嚴蔚敏 吳偉民，數(shù)據(jù)結構（C語言版），北京:清華大學出版社,2007。2 汪祖柱 沈曉潞，基于C語言實現(xiàn)的若干排序算法和分析，安徽電氣工程職業(yè)學院學報，第九卷第一期。3 王莉，常用內(nèi)部排序算法的比較與選擇，軟件導刊，2006年1月號。4 趙延惠，排序方法及效率淺析，思茅師范高等專科學校學報，第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;/記下進行的位置i=lastExchangeIndex;/本趟進行過交換的最后一個記錄的位置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 中選擇關鍵字最小的記錄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 中選擇關鍵字最小的記錄if (i!=j) / 與第 i 個記錄交換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;/復制為哨兵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進行快速排序if (low high) / 長度大于1 long pivotloc = Partition(R,low,high,n);/ 對 L.rlow.high 進行一次劃分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;/定義兩個變量double Time;/排序時間long degree;/排序次數(shù)char ch;cout ch;switch(ch)case 1:coutn;coutt=您選擇的是冒泡排序=n;for(int i = 1

21、; i =n; i +)/將隨機數(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 冒泡排序所用時間：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 選擇排序所用時間：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 直接插入排序所用時間： 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 快速排序所用時間：t Time n;cout 快速排序交換次數(shù)：t QT n;cout n;operate(a, n);break;case a:main();break;de