排序算法的时间性能比较
更新时间:2024-06-22 08:55:01 阅读量: 综合文库 文档下载
排序算法的时间性能比较
一、问题描述
给出一组实验来比较下列排序算法的时间性能: 快速排序、堆排序、冒泡排序
二、基本要求
(1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。
(2)实验数据应具有说服力,包括: 规模范围要大(如从100到10000), 数据的初始特性类型要多,因而需要具有随机性; 实验数据的组数要多,即同一规模的数组要多选几种不同类型的数据来实验。 实验结果要能以清晰的形式给出,如图、表等。 (3)算法所用时间必须是机器时间,也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清晰的方式来描述,如数学公式或图表等。
(5)要给出实验的方案及其分析。
三、工具/准备工作
Microsoft Visual C++ 6.0 软件。
四、分析与实现
1.快速选择排序
这个是冒泡排序的一种改进,他的基本思想就是在当前无序区R【1….H】中任取一个数据元素的基准用此基准将当前无序区划分成左右二个较小的无序去区,R【1……i-1】和R【i+1…..H】,且左边的元素序子区中的数据元素均小于等于基数元素,右边的元素序子区中的数据元素均大于等于基数元素。直到所有无序子区中的数据元素
均已排序为止。 2.堆排序
堆排序实质上就是具备有如下性质的完全二叉树:树中任一非子叶节点的关键字均大于等于其子孩子结点的关键字,它只要记录一个大小的辅助空间,每个待排序的记录只占有一个存储空间,一般记录数较小的。但对基数较大的文件还是很有效的,因为运行时间主要是小号在建初始堆和调整建新堆时进行的反复的筛选上的。 3.冒泡排序
这种排序的比较基本思想就是二二比较待排序的数据元素的大小,发现二个数据元素的次序相反时候,就进行交换,知道没有反序的数据为止。冒泡排序是一种一次比较出最小或最大值,然后将其放置序列的最后一位置,再将剩下的从打一个位置开始到N-1的位置进行重复的操作。
排序算法的时间空间复杂度 排序方法 快速排序 堆排序 冒泡排序 程序代码:
最坏情况 O(nlogn) O(nlogn) O(n2) 平均情况 O(n2) O(nlogn) O(nlogn) 最好情况 O(1) O(n) O(n) #include
#define MAXSIZE 50 typedef int KeyType; #define MAXNUM 100 typedef struct{
KeyType Key;} RedType;
RedType R[MAXNUM]; typedef struct{
RedType r[MAXSIZE+1];
int length;} Sqlist;
Sqlist L,L0,L1,L2,L3,L4,L5,L6,L7; typedef Sqlist HeadType; #define RADIX 10 #define MAX 8
#define MAX_SPACE 10000 typedef int KeysType; typedef struct {KeysType Keys [MAX]; int next;} SLCell; typedef struct {
SLCell rl[MAX_SPACE]; int Keynum; int recnum;} SLList;
typedef int ArrType[RADIX]; int compare[8]; int change[8]; void shuRu(Sqlist L){ int i=1,n;
printf(\请输入你输入的数据个数: \\n\scanf(\
printf(\请依次的输入各个数据值\\n\L.length=n; for(;i<=L.length;i++) {scanf (\}}
void shuChu(Sqlist L){ int i=1;
printf (\该顺序存储中的数据元素为:\for(;i } //=======快速排序========= int partition (Sqlist L,int low ,int high) { KeyType pivotKey; L.r[0]=L.r[low]; pivotKey=L.r[low].Key; change [4]++; while (low compare[4]++; compare[4]++; while (low while (low L.r[low]=L.r[0]; change [4]++; return low;} void Qsort (Sqlist L,int low,int high)
正在阅读:
排序算法的时间性能比较06-22
功德碑范文02-15
小猪找工作作文450字06-27
循证护理对慢性胆囊炎患者痛苦度的影响12-22
潘一矿课程设计101-04
《放牛班的故事》观后感06-09
小蚂蚁找秋天作文450字06-28
那一刻我真自信作文450字07-07
开展冬季防溺水安全教育专题班会参考范文08-05
上海斑马鱼饲养设备10-18
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 算法
- 排序
- 性能
- 比较
- 时间