没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
数据结构课程设计——排序算法比较
XXXXXX 大学
《数据结构》课程设计报告
第 1 页 共 66 页
数据结构课程设计——排序算法比较
目 录
排序算法比较
一、需求分析
二、程序的主要功能
三、程序运行平台
四、数据结构
五、算法及时间复杂度
六、测试用例
七、程序源代码
二 感想体会与总结
排序算法比较
一、需求分析
利用随机函数产生 N 个随机整数(N =
500,1000,1500,2000,2500,…,30000),利用直接插入排序、折半
插入排序,起泡排序、快速排序、选择排序、堆排序,基数排序七种排序
方法(可添加其它排序方法)进行排序(结果为由小到大的顺序),并统
计每一种排序所耗费的时间(统计为图表坐标形式)。
二、程序的主要功能
1.用户输入任意个数,产生相应的随机数
2.用户可以自己选择排序方式(直接插入排序、折半插入排序、起泡
排序、快速排序、选择排序、堆排序、基数排序)的一种
3.程序给出原始数据、排序后从小到大的数据,并给出排序所用的时
间。
第 2 页 共 66 页
数据结构课程设计——排序算法比较
三、程序运行平台
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("存储分配失败!");
exit(0);
} //存储分配失败
L.length=0;//初始长度为 0
return OK;
}
五、算法及时间复杂度
(一)各个排序是算法思想:
(1)直接插入排序:将一个记录插入到已排好的有序表中,从而得到一
个新的,记录数增加 1 的有序表。
(2)折半插入排序:插入排序的基本插入是在一个有序表中进行查找和
插入,这个查找可利用折半查找来实现,即为折半插入排序。
(3)起泡排序:首先将第一个记录的关键字和第二个记录的关键字进行
比较,若为逆序,则将两个记录交换,然后比较第二个记录和第三个
记录的关键字。依此类推,直到第 N-1 和第 N 个记录的关键字进行
过比较为止。上述为第一趟排序,其结果使得关键字的最大纪录被安
排到最后一个记录的位置上。然后进行第二趟起泡排序,对前 N-1
个记录进行同样操作。一共要进行 N-1 趟起泡排序。
第 3 页 共 66 页
数据结构课程设计——排序算法比较
(4)快速排序:通过一趟排序将待排记录分割成独立的两部分,其中一
部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部
分记录继续进行排序,已达到整个序列有序。
(5)选择排序:通过 N-I 次关键字间的比较,从 N-I+1 个记录中选出关
键字最小的记录,并和第 I(1<=I<=N)个记录交换。
(6)堆排序:在堆排序的算法中先建一个大顶堆,既先选得一个关键字
作为最大的记录并与序列中最后一个记录交换,然后对序列中前 N-1
记录进行选择,重新将它调整成一个大顶堆,如此反复直到排序结束。
(7)基数排序:按最低位优先法先对低位关键字进行排序,直到对最高
位关键字排序为止,经过若干次分配和收集来实现排序
(二)时间复杂度分析
排序算法 最差时间 时间复杂度 是否稳定?
插入排序
O(n
2
) O(n
2
)
稳定
冒泡排序
O(n
2
) O(n
2
)
稳定
快速排序
O(n
2
) O(n*log
2
n)
不稳定
选择排序
O(n
2
) O(n
2
)
稳定
堆排序
O(n*log
2
n) O(n*log
2
n)
不稳定
基数排序
O(n*log
2
n) O(n
2
)
稳定
10000 个数据的时间比较:
算法名称 用时
直接插入排序
0.25
折半插入排序
0.219
起泡排序
0.704
快速排序
0.016
选择排序
0.39
堆排序
0.0001
基数排序
0.016
第 4 页 共 66 页
数据结构课程设计——排序算法比较
六、测试用例
1、首先选择需要排序的数字个数,比如输入 5000。
2、系统显示出随机产生的随机数。
用户选择排序方式,比如选择 1.直接插入排序
第 5 页 共 66 页
剩余63页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 79
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功