几种常见内部排序算法比较
更新时间:2023-05-28 10:13:01 阅读量: 实用文档 文档下载
- 内部排序法常见的有哪几类推荐度:
- 相关推荐
这是在我大学期间学习C语言时学到的几种常见的内部排序算法的。在大学期间,计算机相关专业的同学,只要掌握这几种排序算法就已经足够了!
常见内部排序算法比较
排序算法是数据结构学科经典的内容,其中内部排序现有的算法有很多种,究竟各有什么特点呢?本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序,直接插入排序,简单选择排序,快速排序,堆排序,针对关键字的比较次数和移动次数进行测试比较。
问题分析和总体设计
ADT OrderableList
{
数据对象:D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0}
数据关系:R1={〈ai-1,ai〉|ai-1, ai∈D, i=1,2,…,n}
基本操作:
InitList(n)
操作结果:构造一个长度为n,元素值依次为1,2,…,n的有序表。 Randomizel(d,isInverseOrser)
操作结果:随机打乱
BubbleSort( )
操作结果:进行起泡排序
InserSort( )
操作结果:进行插入排序
SelectSort( )
操作结果:进行选择排序
QuickSort( )
操作结果:进行快速排序
HeapSort( )
操作结果:进行堆排序
ListTraverse(visit( ))
操作结果:依次对L种的每个元素调用函数visit( )
}ADT OrderableList
待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果.
要求对结果进行分析.
这是在我大学期间学习C语言时学到的几种常见的内部排序算法的。在大学期间,计算机相关专业的同学,只要掌握这几种排序算法就已经足够了!
详细设计
1、起泡排序
算法:核心思想是扫描数据清单,寻找出现乱序的两个相邻的项目。当找到这两个项目后,交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。
bubblesort(struct rec r[],int n)
{
int i,j;
struct rec w;
unsigned long int compare=0,move=0;
for(i=1;i<=n-1;i++)
for(j=n;j>=i+1;j--)
{
if(r[j].key<r[j-1].key)
{
w=r[j];
r[j]=r[j-1];
r[j-1]=w;
move=move+3;
}
compare++;
}
printf("\nBubbleSort compare= %ld,move= %ld\n",compare,move); }
2、直接插入排序
算法:经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤ L[i],则L[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j+1]时为止。
insertsort(struct rec r[],int n)
{
int i,j;
unsigned long int compare=0,move=0;
这是在我大学期间学习C语言时学到的几种常见的内部排序算法的。在大学期间,计算机相关专业的同学,只要掌握这几种排序算法就已经足够了!
for(i=2;i<=n;i++)
{compare++;
r[0]=r[i];
move++;
j=i-1;
while(r[0].key {r[j+1]=r[j];
j--;
move++;
++compare;}
r[j+1]=r[0];
move++;
}
printf("\nInsertSort compare= %ld,move= %ld\n",compare,move); }
3、简单选择排序
算法:首先找到数据清单中的最小的数据,然后将这个数据同第一个数据交换位置;接下来找第二小的数据,再将其同第二个数据交换位置,以此类推。
selectsort(struct rec r[],int n)
{
unsigned long int compare=0,move=0;
int i,j,k;
struct rec w;
for(i=1;i<=n-1;i++)
{ k=i;
for(j=i+1;j<=n;j++)
{ if(r[j].key>r[k].key) {k=j; compare++; }
w=r[i];
r[i]=r[k];
r[k]=w;
move=move+3;
}
}
printf("\nSelectSort compare= %ld,move= %ld\n",compare,move); }
4、快速排序
这是在我大学期间学习C语言时学到的几种常见的内部排序算法的。在大学期间,计算机相关专业的同学,只要掌握这几种排序算法就已经足够了!
算法:首先检查数据列表中的数据数,如果小于两个,则直接退出程序。如果有超过两个以上的数据,就选择一个分割点将数据分成两个部分,小于分割点的数据放在一组,其余的放在另一组,然后分别对两组数据排序。通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过,你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多。
q(struct rec r[],int s,int t)
{
int i=s,j=t;
if(s<t)
{
r[0]=r[s]; ++a; c++;
do{
while(j>i&&r[j].key>=r[0].key)
{j--;
++a; }
if(i<j)
{ r[i]=r[j];
i++;
c++; }
while(i<j&&r[i].key<=r[0].key)
{i++;
++a; }
if(i<j)
{ r[j]=r[i];
j--;
c++; }
} while(i<j);
r[i]=r[0];
c++;
q(r,s,j-1);
q(r,j+1,t);
}
}
5. 堆排序
基本思想:堆排序是一树形选择排序,在排序过程中,将R[1..N]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
(2)堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆,当且仅当该序列满足特性:
这是在我大学期间学习C语言时学到的几种常见的内部排序算法的。在大学期间,计算机相关专业的同学,只要掌握这几种排序算法就已经足够了!
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])
sift(struct rec r[],int l,int m)
{
int i,j;
struct rec w;
i=l; j=2*i;
w=r[i];
while(j<=m)
{
if(j<m&&r[j].key<r[j+1].key) { j++;
}
if(w.key<r[j].key)
{
r[i]=r[j];
i=j;
j=2*i;
}
else j=m+1;
}
r[i]=w;
}
heapsort(struct rec r[],int n)
{
unsigned long int compare=-1,move=-1;
struct rec w;
int i;
int a;
for(i=n/2;i>=1;i--) a=sift(r,i,n);
compare++;
move++;
for(i=n;i>=2;i--)
{
w=r[i];
r[i]=r[1];
r[1]=w;
a=sift(r,1,i-1);
compare+=a;
move+=a;
}
}
这是在我大学期间学习C语言时学到的几种常见的内部排序算法的。在大学期间,计算机相关专业的同学,只要掌握这几种排序算法就已经足够了!
小结:
1.学会使用随机函数randomize( )为数组赋初值要在头文件中添加#include 。
2.在做此程序之前基本上是在理解了各种排序过程以后完成的。
3.对排序算法的总结:
(1)若n较小(如n≤50),可采用直接插入或直接选择排序。当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;
(3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
正在阅读:
几种常见内部排序算法比较05-28
专题03 形容词和副词(押题专练)-2017年高考英语二轮复习精品资料03-08
2013年68套全国各地物理中考题分类汇编—家庭电路与安全用电 - 图文12-29
动物类中药02-01
换热器冷却水出口温度组态监控系统设计09-18
2015年山东省德州市中考数学试题及解析08-19
AAAA适合三四年级学生阅读的课外书06-12
17.1.2反比例函数的图象和性质(2)04-23
古诗词鉴赏专题卷(最终定稿)05-06
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 算法
- 排序
- 内部
- 常见
- 比较
- 关于纸箱报价的前提条件
- 公司的企业文化心得体会
- 投标报价的技巧和策略
- 纳子峡水电站大坝安全监测及成果分析
- 承台施工技术交底
- 电气控制技术在工业生产中的应用
- 【资格考试】2019最新整理-注册会计师税法二讲义(一)
- 机械制造企业发票和收据使用管理制度
- 压力管道施工管理的要点
- 钒钛磁铁矿项目可行性研究报告
- 护理查对制度流程
- 小学人教版数学五年级上册5.2解简易方程练习卷(含答案解析)
- 9电势能和电势-小班
- Agilent 1100型高效液相色谱仪操作规程
- 关于电脑保养的小知识保养
- 第四章综合指标2009.9.28
- LED显示屏购销合同
- 2009-2013年全国花画工艺品制造行业财务指标分析年报
- 砧用南瓜种质资源形态学性状与SSR标记分析
- 教育技术学本科专业人才培养模式创新研究