没有合适的资源?快使用搜索试试~ 我知道了~
数据结构各种排序算法的时间性能..pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 1 下载量 170 浏览量
2022-07-14
20:12:26
上传
评论
收藏 1.84MB PDF 举报
温馨提示
试读
20页
数据结构各种排序算法的时间性能..pdf数据结构各种排序算法的时间性能..pdf数据结构各种排序算法的时间性能..pdf数据结构各种排序算法的时间性能..pdf数据结构各种排序算法的时间性能..pdf数据结构各种排序算法的时间性能..pdf
资源推荐
资源详情
资源评论
HUNAN UNIVERSIT Y
课程实习报告
题 目 排序算法的时间性能 ________________
学生姓名 ________________________________________________________
学生学号 ________________________________________________
专业班级 ________________________________________________
指导老师 ____________________
李晓鸿 ________________________
完成日期
设计一组实验来比较下列排序算法的时间性能
快速排序、堆排序、希尔排序、冒泡排序、归并排序
(
其他排序也可以作为 比较的对
象)
要求
(1)
时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时 间性能
等。
(2)
实验
100
数据应具有说服力,包括:数据要有一定的规模(如元素个数从
到
10000
);数据的初始特性类型要多,因而需要具有随机性;实验数据的组数 要多,即同
一规模的数组要多选几种不同类型的数据来实验。 实验结果要能以清 晰的形式给出,如
图、表等。
(3)
算法所用时间必须是机器时间,也可以包括比较和交换元素的次数。
(4)
实验分析及其结果要能以清晰的方式来描述,如数学公式或图表等。
(5)
要给出实验的方案及其分析。
说明
本题重点在以下几个方面:
理解和掌握以实验方式比较算法性能的方法; 掌握测试实验方案的设计; 理 解并实
现测试数据的产生方法; 掌握实验数据的分析和结论提炼; 实验结果汇报
、需求分析
(1)
输入的形式和输入值的范围:本程序要求实现各种算法的时间性能的比 较,由于
需要比较的数目较大,不能手动输入,于是采用系统生成随机数。
用户输入随机数的个数
n
,然后调用随机事件函数产生
n
个随机数,对这些 随机数进行
排序。于是数据为整数
(2)
输出的形式:输出在各种数目的随机数下,各种排序算法所用的时间和 比较次
数。
(3)
程序所能达到的功能:该程序可以根据用户的输入而产生相应的随机 数,然后对
随机数进行各种排序,根据排序进行时间和次数的比较。
(4)
测试数据:略
、概要设计
1.
抽象数据类型
数据对象
数据关系
基本操作
D
=
{ ai | ai
€
ElemSet, i=1,2,...,n,
n
>
0 } R1
=
{ vai-1 ,ai >|ai-1 ,ai
€
D, i=2,...,n }
ADT List
virtual void clear() = 0;
bool insert(const Elem&) = 0;
bool append(const Elem&) = 0;
lbool remove(Elem&) = 0;
void setStart() = 0;
void setEnd() = 0;
void prev() = 0;
void next() = 0;
int leftLength() const = 0;
int rightLength() const = 0;
bool setPos(int pos) = 0;
bool getValue(Elem&) const = 0;
void print() const = 0;
2.
程序的流程
1
)输入模块:输入要排序的数的数量
n
(2)
处理模块:系统产生
n
个随机数,对随机数进行排序
3
)输出模块:将排序的结果输出
3.
算法的基本思想
1
、
2
、
3
、
4
、
5
、
6
、
随机数的产生:利用
srand()
产生随机数。
快速排序:选定一记录
R
,将所有其他记录关键字
k
'与记录
R
的关键字
k
比较
,
若
k
'
<
则将记录换至
R
之前
,
若
k' >k
则将记录换至
R
之 后,继续对
R
前后
两部分记录进行快速排序,直至排序范围为
1
插入排序:逐个处理待排序的记录,每个新记录与前面已排序的子序列 进行比
较,将它插入到子序列中正确的位置
冒泡排序:比较并交换相邻的元素对,直到所有元素都被放到正确的地 方为止。
归并排序:将两个或者多个有序表归并成一个有序表
堆排序:首先将数组转化为一个满足堆定义的序列,然后将堆顶的最大
元素取出,再将剩下的数排成堆,再取堆顶数值, …。如此下去,直到
堆为空。到最后结束时,就排出了一个由小到大排列的数组。
三、详细设计
(
1
)产生随机数:直接调用函数
srand(),
以时间作为随机种子进行选择,并把 随机数装入
数组中
unsigned long int *Sort::setRan(unsigned long int num){
unsigned long int *ra;
ra=(unsigned long int*)malloc(num*sizeof(unsigned long int));
剩余19页未读,继续阅读
资源评论
- 2301_767827142023-06-13总算找到了想要的资源,搞定遇到的大问题,赞赞赞!
a66889999
- 粉丝: 35
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功