没有合适的资源?快使用搜索试试~ 我知道了~
数据结构课程设计报告_排序算法比较.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 44 浏览量
2021-10-06
08:20:44
上传
评论
收藏 196KB DOC 举报
温馨提示
试读
20页
数据结构课程设计报告_排序算法比较.doc
资源推荐
资源详情
资源评论
- .
XXXXXX 大学
?数据构造?课程设计报告
目录
排序算法比拟
一、需求分析
二、程序的主要功能
三、程序运行平台
四、数据构造
五、算法及时间复杂度
六、测试用例
七、程序源代码
二 感想体会与总结
. -可修遍-
排序算法比拟
一、需求分析
利用随机函数产生 N 个随机整数〔N =
500,1000,1500,2000,2500,…,30000〕,利用直接插入排序、
折半插入排序,起泡排序、快速排序、选择排序、堆排序,基数排序七种
排序方法〔可添加其它排序方法〕进展排序〔结果为由小到大的顺序〕,
并统计每一种排序所消耗的时间〔统计为图表坐标形式〕。
二、程序的主要功能
1.用户输入任意个数,产生相应的随机数
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("存储分配失败!");
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
记录进展选择,重新将它调整成一个大顶堆,如此反复直到排序完毕。
〔7〕基数排序:按最低位优先法先对低位关键字进展排序,直到对最高
位关键字排序为止,经过假设干次分配和收集来实现排序
〔二〕时间复杂度分析
排序算法 最差时间 时间复杂度 是否稳定?
插入排序
O(n
2
) O(n
2
)
稳定
- - word.zl-
冒泡排序
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
六、测试用例
1、首先选择需要排序的数字个数,比方输入 5000。
在平时的测量工作中,他积极做好传、帮、带工作,热心地把自己学到和掌握好的操作技艺毫无保存地传授给徒弟 !"#$ %&'#($) #*$+,- ).!#$, /'
剩余19页未读,继续阅读
资源评论
gjmm89
- 粉丝: 13
- 资源: 19万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功