各種排序算法性能比較-顧云康E01114300

1、各種排序算法性能比較E01114300-顧云康數據結構課程設計報告數據結構課程設計實驗 報告 各種排序算法性能比較姓名：顧云康 學號： E1114300 指導老師：王愛平 日期： 2013.10.8數據結構課程設計報告目 錄1 課程設計的目的2.2 需求分析2.3課程設計報告內容 2.3.1概要設計2.3.2詳細設計3.3.3調試分析114總結125程序清單 136參考文獻137程序運行結果13附 錄14i數據結構課程設計報告1 課程設計的目的(1) 熟練使用 C 語言編寫程序，解決實際問題 ;(2) 了解并掌握數據結構與算法的設計方法，具備初步的獨立分 析和設計能力 ;(3) 初步掌握軟件開

2、發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、 測試等基本方法和技能 ;(4) 提高綜合運用所學的理論知識和方法獨立分析和解決問題 的能力 ;2 需求分析( 1)使用數組來存放產生的 40000 個隨機數 (2)編寫統(tǒng)計程序運行時間的函數( 3)編寫快速排序、冒泡排序、插入排序、梳排序四種排序算 法的函數(4 ) 編寫主函數，控制程序運行3 課程設計報告內容3.1 概要設計(1) 使用四種排序算法：插入排序、冒泡排序、快速排序、梳排序( 2)使用 clock() 函數來統(tǒng)計時間3.2 詳細設計(1)主函數：int main()int numberMAX = 0;int number1MAX = 0;i

3、nt number2MAX = 0;int number3MAX = 0;int number4MAX = 0;int i;srand(unsigned) time(NULL); /* 播種子 */for(i = 0; i MAX; i+)numberi = rand() % 20000; /* 產生 101 以內的隨機整數 */number1i=number2i=number3i=number4i=numberi;while(numberi=0)numberi = rand() % 20000;number1i=number2i=number3i=number4i=numberi; /快速排

4、序并計算時間clock_t begin1, end1;double cost1;begin1 = clock();quicksort(number1,MAX);end1 = clock();cost1 = (double)(end1 - begin1) / CLOCKS_PER_SEC;/冒泡排序并計算時間clock_t begin2, end2;double cost2;begin2 = clock();Bubble(number2,MAX);end2 = clock();cost2 = (double)(end2 - begin2) / CLOCKS_PER_SEC;/插入排序并計算時間c

5、lock_t begin3, end3;double cost3;begin3 = clock();insertSort(number3,MAX);end3 = clock();cost3 = (double)(end3 - begin3) / CLOCKS_PER_SEC;/梳排序并計算時間 clock_t begin4, end4;double cost4;begin4 = clock();combsort(number4,MAX);end4 = clock();cost4 = (double)(end4 - begin4) / CLOCKS_PER_SEC;for(int j=0;jMA

6、X;j+)printf(%d , number1j);printf(n);printf( 排序完成 !n);printf( 快速排序耗時 :%lf secondsn, cost1);, cost2);, cost3);, cost4);printf( 冒泡排序耗時 :%lf secondsn printf( 插入排序耗時 :%lf secondsn printf( 梳 排 序耗時 :%lf secondsn return 0;(2) 插入排序函數：void insertSort(int a, int len)int i, j, temp;for(i = 1; i = 0; j -)if(aj

7、temp)aj + 1 = aj;elsebreak;aj + 1 = temp;(3) 冒泡排序函數：void Bubble(int a,int len)int length=len;int i=0;int j=0;for(;ilen;i+)for(;jaj+1)int temp=aj;aj=aj+1;aj+1=temp;length-;j=0;(4) 快速排序函數：int partions(int l,int low,int high)int prvotkey=llow;l0=llow;while (lowhigh)while (low=prvotkey)-high;llow=lhigh;

8、while (lowhigh&llow=prvotkey) +low;lhigh=llow;llow=l0;return low;void qsort(int l,int low,int high)int prvotloc;if(low 1) | swapped)if (gap 1) gap = gap / shrink_factor; swapped = 0;i = 0;while (gap + i) 0)swap = ai; ai = ai + gap; ai + gap = swap; swapped = 1;+i;10數據結構課程設計報告3.3調試分析(1) 使用隨機數產生函數，產生4

9、0000個隨機數，再使用四種算法進行排序，并統(tǒng)計各種算法統(tǒng)計時間。(2) 運行截圖如下:ii數據結構課程設計報告.exe-E八 Vicrosoft /i?ual Stud oMyPrcjset弓詡:.字Det了擊E 弓 1?77 LS778 19780 丄9袖丄 19?B1 JJ783 197B4 19785 1?7#5 19785 1?78S 1*786 1787 19787 19788 19788 1979B 1929O 19790 19793 19793 19793 1?9J 1?7?4 1976 19?6 19 797 19799 1979(1 19798 19?99 19880 19

10、A81 1?01 19802 19893 的 19906 19807 19fiA p 1900 灼g陸 1910 19811 lySil19fil3 19812 19S1C 1991C 1?S1P 101B 19B19psi? 19B19 19S21 19822 1?824 丄汕加 19826 1?82? 19S29 1?B3B 19830 19631 19831 IS 1VB3L134 1983 lVBJb lV83b 1VU32 1VW4M 1VH4U 19842 1VH42 iy4b 1艸4* l?84t L仙站 19S51 19853 1953 19A5S 1965t 19SS6 19

11、S5? 198S7 lMbU 1859 l$85y pgtO 19SC0 19AG1 19SG2 19SC2 198&2 198G4 19S64 1弘“丄網航丄他強 1 彌“ 1989 19 SG9 1966? 19070 9871 17871 19B71 19S72 19674 19676 15677 19677 19977 12677 13077 1?S7B Ly7 19SK0 19881 1988Z 1J/HN4 1?WW4 lVUKb 1VB87 18 18S!? 1TS9 198VU L9S91 19391 19S92 19S93 19893 丄他掐 19fi?5 19895 198

12、951989? 1987 19898 19R9fl 194BR 199B1 1990 19903 199Q3 199的 1904 19904 199BA 1907 19987 199RR 199HV 19910 1910 19911 19911 19912 15913 19914 19926 19923 19924 1J924 ?925 9926 p?27Jl92? 1930 丄793丄 19332 19932 1934 19$34 1?938 1938 1S939 19941 1942 1942 19543 11944 19947 1994# 19448 19949 19953 1W53 1

13、99S3 19954 19954 1995 S 1*955 159S5 19957 19*57 19$5 194&S 199&8 1991 19912 19V62 W63 1964 1$%4 p9fcG 19?67 9967 194&S 19971 19971 19972 19973?974 1997E 1997C 1997G 19k 1978 19478 丄99? 1997? 19980 19?88 19584 1?88 1995 H9S9 1?50 l?i 1?9921二1廿二t甜 TJ nQ nn k 成序序序序細 F - J. - = s s箱屮乳nr舌克seconds seconds

14、 seconds secondsi to eontinae00110098.246&2*2710000.01390(9(3) 由多次試驗結果可得，梳排序和快速排序的排序速度相對 較快。4總結通過這次課程設計我認識到了排序功能在解決實際問題中 的作用，使我對數據結構的學習有了更進一步的理解。在完成本次課程設計中，我發(fā)現很多理論性知識在實際使用時與單純的 理論還是有所差別的，今后我會更加注重培養(yǎng)自己的實踐動手能 力。5 程序清單見附錄6 參考文獻1嚴蔚敏，吳偉民 編著. 數據結構 （C 語言版）-北京: 清華大學 出版社， 2007.2嚴蔚敏，吳偉民 米 寧 編著. 數據結構題集 （C 語言版 ）

15、-北京: 清華大學出版社， 2007.3 /wiki/%E6%A2%B3%E6%8E%92%E5 %BA%8F7 程序運行結果.013009tn contsecond-e sec-urnd-s seconds seconds i nue199V4 ivyyt iyiyyyv?77 丄?78 丄止寧m 157?丄丄V ?8O 丄7 7弱2 1?88 19989 19989 丄?17?19927 19?29 1972 19930 丄933丄 19932 19?32 19?34 19?34 1?938 1938 1S939 19941 1942 1942

16、19943 11944 19947 19948 19448 19949 1J953 IW53 19953 19J54 19954 199 S 1955 159S5 19957 19957 19$58 194&A 19968 1991 19912 192 19963 1*964 1$96419967 1L99&S 19971 19971 1992 1973 1974 1?974 19975 19975 1997C 19 1991BI 159ie19912 17*313 19?14 1992B 19923 19924 17924 19925 1992C7 1TH7B 1UW7 19VSU 1V8N

17、1 1VSN 1J/S84 lWW 1VNS6 1VB8 7 1 lKB? 1?B8?L9S91 19891 19S92 19A93 19893 19895 19A95 19895 19895189? 1987 19898 1R9S 199QR 19901 199fl3 199133199H31994 199BA 1907 199B7 199RR 195iSG7 1?8G7 l?870 丄!?87丄 17871 19B71 17872 17B74 1?76 1?877 17B77 17B7719919 19821 9822 19824 1S26 1?8Z 19829 1929 19830 18

18、30 丄如丄 1 ；31 1V83L 1VM3J 1834 1983 1V6 IVKJb 19W32 1VU4H 1VH4U 19842 1VH42 iy4b lU .l$84t LS4fi 19851 19853 1V853 19855 1965fc 19S56 19S5? 198S7 l6b9 1859 i$8591990 19AG1 19SG2 19SG2 198&3 1984 19SC4 199&C 198&6 19H9 1S l77fi 19778 丄9780 丄978丄丄9?81 19783 19784 19785 197#5 19785 1?786 1*786 丄?787 197

19、87 19788 19788 19790 1979B 19790 19793 19793 19793 1?9J 1?7?4 1976 19?6 1 797 19799 1979(1 19798 19799 19880 19801 190D1 19602 19893 的 1的朋 19807 19Hi 9 1996 1090 1910 19811 19S11 1913 19613 198L2 19S1E 1991G 1817 19019 19B19 Er/icrosoft Visual Stud o：MyProject譏徘序Qebug讀E序芒燼l019盤泡入曲1 霞附錄程序清單：#i nclude

20、 stdafx.h#in elude #in elude #include /*用到了 time函數，所以要有這個頭文件 */#defi ne MAX 40000/插入排序void in sertSort(i nt a, i nt len)int i, j, temp;for(i = 1; i = 0; j -)if(aj temp)aj + 1 = aj;elsebreak;aj + 1 = temp;/冒泡排序 void Bubble(int a,int len)int length=len;int i=0;int j=0;for(;ilen;i+)for(;jaj+1)int temp=

21、aj;aj=aj+1; aj+1=temp;length-;j=0;/快速排序 int partions(int l,int low,int high)int prvotkey=llow;l0=llow;while (lowhigh)while (low=prvotkey)-high;llow=lhigh;while (lowhigh&llow=prvotkey)+low;lhigh=llow;llow=l0;return low;void qsort(int l,int low,int high)int prvotloc;if(low 1) | swapped)if (gap 1) gap

22、= gap / shrink_factor;swapped = 0;i = 0;while (gap + i) 0)swap = ai;ai = ai + gap; ai + gap = swap; swapped = 1;+i;int main()int numberMAX = 0;int number1MAX = 0;int number2MAX = 0;int number3MAX = 0;int number4MAX = 0;int i;srand(unsigned) time(NULL); /* 播種子 */for(i = 0; i MAX; i+)numberi = rand() % 20000; /* 產生 101 以內的隨機整數 */number1i=number2i=number3i=number4i=numberi; while(numberi=0)numberi = rand() % 20000;number1i=number2i=number3i=number4i=numberi;/快速排序并計算時間clock_t begin1, end1;double cost1;begin1 = clock();qui