各种排序算法性能比较E01114300

《各种排序算法性能比较E01114300》由会员分享，可在线阅读，更多相关《各种排序算法性能比较E01114300（23页珍藏版）》请在装配图网上搜索。

1、 . . . . 数据结构课程设计实验报告各种排序算法性能比拟 ：顾云康 学号：E1114300 指导教师：王爱平 日期：2013.10.8目 录1 课程设计的目的22 需求分析23 课程设计报告容23.1 概要设计23.2 详细设计23.3 调试分析64 总结75 程序清单86 参考文献87 程序运行结果8附录1023 / 231 课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等根本方法 和技能;(4) 提高综合运用所学的理论知识和方法独

2、立分析和解决问题的能力;2需求分析1使用数组来存放产生的40000个随机数2编写统计程序运行时间的函数3编写快速排序、冒泡排序、插入排序、梳排序四种排序算法的函数 (4 ) 编写主函数，控制程序运行3 课程设计报告容3.1 概要设计1使用四种排序算法：插入排序、冒泡排序、快速排序、梳排序2使用clock()函数来统计时间3.2 详细设计（1） 主函数：int main()int numberMAX = 0;int number1MAX = 0;int number2MAX = 0;int number3MAX = 0;int number4MAX = 0; int i; srand(unsig

3、ned) 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();quicksort(number1,

4、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;/插入排序并计算时间clock_t begin3, end3; double cost3; begin3 = clock();insertSort(number3,M

5、AX);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;jMAX;j+)printf(%d , number1j); printf(n); printf(排序完成!n); printf(快速排序耗时

6、:%lf secondsn, cost1); printf(冒泡排序耗时:%lf secondsn, cost2); printf(插入排序耗时:%lf secondsn, cost3); printf(梳 排 序耗时:%lf secondsn, cost4);return 0;（2） 插入排序函数：void insertSort(int a, int len)int i, j, temp;for(i = 1; i = 0; j -)if(aj temp)aj + 1 = aj;elsebreak;aj + 1 = temp;（3） 冒泡排序函数：void Bubble(int a,int l

7、en)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; while (lowhigh&llow=prvotkey) +low; lhigh=llow; llow=l0; return

8、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;3.3 调试分析1使用随机数产生函数，产生40000个随机数，再使用四种算法进展排序，并统计各种算法统计时间。（2） 运行截图如下：3由屡次试验结果可得，梳排序和快速排序的排序速度相对较

9、快。4 总结 通过这次课程设计我认识到了排序功能在解决实际问题中的作用，使我对数据结构的学习有了更进一步的理解。 在完本钱次课程设计中，我发现很多理论性知识在实际使用时与单纯的理论还是有所差异的，今后我会更加注重培养自己的实践动手能力。5 程序清单见附录6 参考文献1严蔚敏，吴伟民 编著. 数据结构(C 语言版)-: 清华大学，2007.2严蔚敏，吴伟民 米 宁 编著. 数据结构题集(C 语言版)-: 清华大学，2007.3 zh.wikipedia.org/wiki/%E6%A2%B3%E6%8E%92%E5%BA%8F7 程序运行结果附 录程序清单：#include stdafx.h#in

10、clude #include #include /*用到了time函数，所以要有这个头文件*/#define MAX 40000/插入排序void insertSort(int a, int 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=aj; aj=aj+1; aj+1=

11、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 = gap /

12、 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() %

13、 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();quicksort(number1,MAX);end1 = clock();cost1 = (double)(end1 - begin1) / CLOCKS_PER

14、_SEC; /冒泡排序并计算时间clock_t begin2, end2; double cost2; begin2 = clock();Bubble(number2,MAX);end2 = clock();cost2 = (double)(end2 - begin2) / CLOCKS_PER_SEC;/插入排序并计算时间clock_t begin3, end3; double cost3; begin3 = clock();insertSort(number3,MAX);end3 = clock();cost3 = (double)(end3 - begin3) / CLOCKS_PER_

15、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;jMAX;j+)printf(%d , number1j); printf(n); printf(排序完成!n); printf(快速排序耗时:%lf secondsn, cost1); printf(冒泡排序耗时:%lf secondsn, cost2); printf(插入排序耗时:%lf secondsn, cost3); printf(梳 排 序耗时:%lf secondsn, cost4);return 0;