c语言课程设计---各种排序算法的设计和分析

《c语言课程设计---各种排序算法的设计和分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华中科技大学文华学院数据结构课程设计姓名：学号：学部：信息科学与技术学部专业：班级：题目：各种排序算法的设计和分析教师：2013年03月07日-12-一.课程设计报告的内容1.设计题目2.运行环境（软、硬件环境）3.算法设计的思想4.算法的流程图5.算法设计分析6.源代码7.运行结果分析8.收获及体会二.《数据结构》课程设计题目各种排序算法的设计和分析-12-1.设计题目（1）、需求分析利用随机函数产生N个随机整数（N=4000），利用直接插入排序、折半插入排序，起泡排序、快速排序、选择排序、堆排序，基数排序七种排序方法（可添加其它排序方法）进行排序（结果为由小到大的顺序），并统计每一

2、种排序所耗费的时间。把排序花的时间排在表格里面。（2）、程序的主要功能1.用户输入任意个数，产生相应的随机数2.用户可以自己选择排序方式（直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序）的一种3.程序给出原始数据、排序后从小到大的数据，并给出排序所用的时间。（3）、程序运行平台VisualC++6.0版本（4）、数据结构（5）、算法及时间复杂度（一）各个排序是算法思想：（1）直接插入排序：将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增加1的有序表。（2）折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现

3、，即为折半插入排序。（3）起泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。（4）快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序。（5）选择排序：通过N-I次关键字间的比较，从N-I+1

4、个记录中选出关键字最小的记录，并和第I（1<=I<=N）个记录交换。（6）堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束。（7）基数排序：按最低位优先法先对低位关键字进行排序，直到对最高位关键字排序为止，经过若干次分配和收集来实现排序-12-（二）时间复杂度分析排序算法最差时间时间复杂度是否稳定？插入排序O(n2)O(n2)稳定冒泡排序O(n2)O(n2)稳定快速排序O(n2)O(n*log2n)不稳定选择排序O(n2)O(n2)稳定堆排序O(n*log

5、2n)O(n*log2n)不稳定基数排序O(n*log2n)O(n2)稳定4000个数据的时间比较：算法名称用时直接插入排序0.062折半插入排序0.047起泡排序0.188快速排序0.000选择排序0.078堆排序0.000基数排序0.000（三）源代码：代码如下：#include#include#include#defineN4000voidInsertSort()//第一个插入排序-12-{inti,j,t;inta[N];for(i=0;i

6、}printf("");for(i=1;i=0&&t>a[t];j--){a[j+1]=a[j];a[j+1]=t;}}for(i=0;i

7、gh=i-1;while(low<=high){m=(low+high)/2;if(L[0]