各种排序算法性能比较-顾云康E01114300.doc

数据结构课程设计报告 数据结构课程设计实验数据结构课程设计实验 报告报告 各各种种排排序序算算法法性性能能比比较较 姓名：顾云康姓名：顾云康 学号：学号：E1114300 指导老师：王爱平指导老师：王爱平 日期：日期：2013.10.8 数据结构课程设计报告 I 目目 录录 1 课程设计的目的课程设计的目的.2 2 需求分析需求分析.2 3 课程设计报告内容课程设计报告内容.2 3.1 概要设计概要设计.2 3.2 详细设计详细设计.2 3.3 调试分析调试分析.6 4 总结总结.7 5 程序清单程序清单.8 6 参考文献参考文献.8 7 程序运行结果程序运行结果.8 附附 录录.10 数据结构课程设计报告 2 1 课程设计的目的 (1) 熟练使用熟练使用 C 语言编写程序，解决实际问题语言编写程序，解决实际问题; (2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分了解并掌握数据结构与算法的设计方法，具备初步的独立分 析和设计能力析和设计能力; (3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、初步掌握软件开发过程的问题分析、系统设计、程序编码、 测试等基本方法测试等基本方法 和技能和技能; (4) 提高综合运用所学的理论知识和方法独立分析和解决问题的提高综合运用所学的理论知识和方法独立分析和解决问题的 能力能力; 2 需求分析 （1）使用数组来存放产生的）使用数组来存放产生的 40000 个随机数个随机数 （2）编写统计程序运行时间的函数）编写统计程序运行时间的函数 （3）编写快速排序、冒泡排序、插入排序、梳排序四种排序算）编写快速排序、冒泡排序、插入排序、梳排序四种排序算 法的函数法的函数 (4 ) 编写主函数，控制程序运行编写主函数，控制程序运行 3 课程设计报告内容 3.1 概要设计概要设计 （1）使用四种排序算法：插入排序、冒泡排序、快速排序、梳）使用四种排序算法：插入排序、冒泡排序、快速排序、梳 数据结构课程设计报告 3 排序排序 （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(unsigned) time(NULL); /*播种子播种子*/ for(i = 0; i temp) aj + 1 = aj; else break; 数据结构课程设计报告 7 aj + 1 = temp; （3）冒泡排序函数：冒泡排序函数： void Bubble(int a,int len) int length=len; int i=0; int j=0; for(;i 1) gap = gap / shrink_factor; swapped = 0; i = 0; while (gap + i) 0) swap = ai; ai = ai + gap; ai + gap = swap; swapped = 1; +i; 数据结构课程设计报告 11 3.3 调试分析调试分析 （1）使用随机数产生函数，产生）使用随机数产生函数，产生 40000 个随机数，再使用四种个随机数，再使用四种 算法进行排序，并统计各种算法统计时间。算法进行排序，并统计各种算法统计时间。 （2）运行截图如下：运行截图如下： 数据结构课程设计报告 12 （3）由多次试验结果可得，梳排序和快速排序的排序速度相对）由多次试验结果可得，梳排序和快速排序的排序速度相对 较快。较快。 4 总结 通过这次课程设计我认识到了排序功能在解决实际问题中通过这次课程设计我认识到了排序功能在解决实际问题中 的作用，使我对数据结构的学习有了更进一步的理解。的作用，使我对数据结构的学习有了更进一步的理解。 在完成在完成 本次课程设计中，我发现很多理论性知识在实际使用时与单纯本次课程设计中，我发现很多理论性知识在实际使用时与单纯 的理论还是有所差别的，今后我会更加注重培养自己的实践动的理论还是有所差别的，今后我会更加注重培养自己的实践动 手能力。手能力。 数据结构课程设计报告 13 5 程序清单 见附录 6 参考文献 1严蔚敏，吴伟民严蔚敏，吴伟民 编著编著. 数据结构数据结构(C 语言版语言版)-北京北京: 清华大清华大 学出版社，学出版社，2007. 2严蔚敏，吴伟民严蔚敏，吴伟民 米米 宁宁 编著编著. 数据结构题集数据结构题集(C 语言版语言版)-北北 京京: 清华大学出版社，清华大学出版社，2007. 3 /wiki/%E6%A2%B3%E6%8E%92%E5%B A%8F 7 程序运行结果 数据结构课程设计报告 14 附 录 程序清单：程序清单： #include “stdafx.h“ #include #include #include /*用到了用到了 time 函数，所以要有这个头文件函数，所以要有这个头文件*/ #define MAX 40000 /插入排序插入排序 void insertSort(int a, int len) 数据结构课程设计报告 15 int i, j, temp; for(i = 1; i = 0; j -) if(aj temp) aj + 1 = aj; else break; aj + 1 = temp; /冒泡排序冒泡排序 void Bubble(int a,int len) 数据结构课程设计报告 16 int length=len; int i=0; int j=0; for(;i 1) gap = gap / shrink_factor; 数据结构课程设计报告 19 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; 数据结构课程设计报告 20 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(); quicksort(number1,MAX); end1 = clock(); 数据结构课程设计报告 21 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,MAX); end3 = clock(); cost3 = (double)(end3 - begin3) / CLOCKS_PER_SEC; /梳排序并计算时间梳排序并计算时间 clock_t begin4, end4; double cost4; begin4 = clock(); 数据结构课程设计报告 22 combsort(number4,MAX); end4 = clock(); cost4 = (double)(end4 - begin4) / CLOCKS_PER_SEC; for(int j=0;jMAX;j+) printf(“%d “, number1j); printf(“n“); printf(“排序完成排序