内容发布更新时间 : 2024/11/13 7:49:09星期一 下面是文章的全部内容请认真阅读。

天津职业技术师范大学

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;jarr[j+1]) {

}

} }

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; } } }