发布时间 : 星期一 文章数据结构 排序算法的比较更新完毕开始阅读
天津职业技术师范大学
TianjinUniversity of Technology and Education
《数据结构》课程设计
排序算法的比较
学 院：信息技术工程学院 专 业：计算机科学与技术 班级学号： 学生姓名：*** 指导教师：***
二〇一三年六月
一、 课程设计名称：排序算法的比较 二、 使用开发工具：Microsoft Visual C++ 6.0 三、 课程设计内容介绍：
1.1课程设计的基本结构流程：
（1）编写4个排序方法函数，快速排序、插入排序、选择排序，冒泡排序，使他们接收数组，进行数值交换。
（2）编写随机生成数组函数，使其随机产生1000个数据，存放到数组中，供排序方法使用。
（3）编写输出界面函数，程序的UI界面在此函数中，实现界面的友好性。
（4）主函数中调用上述几个已定义的几个函数，实现程序功能。 1.2程序界面及运行结果：
四、得意之处：
排序是在日产生活中，最常用，通过本次课程设计，熟练掌握了排序的几种方法，快速排序，插入排序，冒泡排序，选择排序，在几种排序中，快速排序是最快的，它是冒泡排序的优化算法。 下面是几种排序的比较： 排序方法 平均时间 最坏情况 辅助存储 简单排序 O(n2) O(n2) O(1) 快速排序 O(nlogn) O(n2) O(logn) 堆排序 O(nlogn) O(nlogn) O(1) 归并排序 O(nlogn) O(nlogn) O(n) 基数排序 O(d(n+d)) O(d(n+d)) O(rd) 五、课程设计中目前存在的问题：
程序现在能进行排序，结果和效率问题都已经考虑到了，但是在设计的时候，函数书写不太规范，在以后直接调用使用，不是太方便，日后，优化排序函数，使得在以后直接调用函数时，方便快捷。
六、课设计实践过程中的自我感受：
在程序实现过程中，关于排序的交换时，在什么时候交换不容易实现，循环次数不容易控制，但是在参考文献及老师的帮助下，我结果了在排序中的问题，排序过程中的巧妙，深深感受到了算法设计者的用心，也体会到了数据结构的严禁。
七、参考文献：
严蔚敏等，《数据结构》，清华大学出版社，北京．2000 谭浩强，《C语言程序设计》，清华大学出版社，北京．
附录
各排序核心代码： 1.快速排序：
voidqsort(int s[], int l, int r) {
int change=0; int compare=0; int i, j, x; if (l < r) {
i = l; j = r; x = s[i]; while (i < j) {
while(i < j && s[j] > x) j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) i++; if(i < j) s[j--] = s[i]; {
s[i] = x; change++; }
qsort(s, l, i-1); /* 递归调用 */ qsort(s, i+1, r); } }
2.插入排序
intinsert_sort(intarr[],int length) { for(int i=2;i for(int j=i-1;arr[0] arr[j+1]=arr[0]; } } } 3.冒泡排序 voidbubble_sort(intarr[],int length) { for(int i=1;i for(int j=1;j } } } intnum=arr[j]; arr[j] = arr[j+1]; arr[j+1] = num; } 4.选择排序 intselectMin(intarr[],inti,int length) { int j = i; for(i=i+1;i return j; } voidselect_sort(intarr[],int length) { int j; for(int i=1;i j=selectMin(arr,i,length); if(i!=j) { intnum = arr[i]; arr[i] = arr[j]; arr[j] = num; } } }