发布时间 : 星期五 文章(最新版)数据结构毕业课程设计_排序算法比较【完整版】更新完毕开始阅读
XXXXXX大学
《数据结构》课程设计报告
1 目 录
排序算法比较
一、需求分析 二、程序的主要功能 三、程序运行平台 四、数据结构
五、算法及时间复杂度 六、测试用例 七、程序源代码
二 感想体会与总结
排序算法比较
一、需求分析
利用随机函数产生N个随机整数(N = 500,1000,1500,2000,2500,…,30000),利用直接插入排序、折半插入排序,起泡排序、快速排序、选择排序、堆排序,基数排序七种排序方法(可添加其它排序方法)进行排序(结果为由小到大的顺序),并统计每一种排序所耗费的时间(统计为图表坐标形式)。
二、程序的主要功能
1.用户输入任意个数,产生相应的随机数
2 2.用户可以自己选择排序方式(直接插入排序、折半插入排序、起泡排序、快速排序、选择排序、堆排序、基数排序)的一种
3.程序给出原始数据、排序后从小到大的数据,并给出排序所用的时间。
三、程序运行平台
Visual C++ 6.0版本
四、数据结构
本程序的数据结构为线形表,线性顺序表、线性链表。 。
1、结构体: typedef struct {
int *r; r指向线形表的第一个结点。 r[0]闲置,不同的算法有不同
的用处,如用作哨兵等。
int length; 顺序表的总长度 }Sqlist; 2、空线性表
Status InitSqlist(Sqlist &L) {
L.r=(int *)malloc(MAXSIZE*sizeof(int)); 分配存储空间
if(!L.r) {
printf(\存储分配失败!\
3 }
exit(0);
} 存储分配失败 L.length=0;初始长度为0 return OK;
五、算法及时间复杂度
(一)各个排序是算法思想:
(1)直接插入排序:将一个记录插入到已排好的有序表中,从而得到一
个新的,记录数增加1的有序表。
(2)折半插入排序:插入排序的基本插入是在一个有序表中进行查找和
插入,这个查找可利用折半查找来实现,即为折半插入排序。 (3)起泡排序:首先将第一个记录的关键字和第二个记录的关键字进行
比较,若为逆序,则将两个记录交换,然后比较第二个记录和第三个记录的关键字。依此类推,直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序,其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序,对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序。
(4)快速排序:通过一趟排序将待排记录分割成独立的两部分,其中一
部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,已达到整个序列有序。
(5)选择排序:通过N-I次关键字间的比较,从N-I+1个记录中选出关
键字最小的记录,并和第I(1<=I<=N)个记录交换。
(6)堆排序:在堆排序的算法中先建一个大顶堆,既先选得一个关键字
作为最大的记录并与序列中最后一个记录交换,然后对序列中前N-1
4