1 / 55
文档名称:

常用排序算法.ppt

格式:ppt   大小:568KB   页数:55页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

常用排序算法.ppt

上传人:文库新人 2018/9/30 文件大小:568 KB

下载得到文件列表

常用排序算法.ppt

文档介绍

文档介绍:内部排序: 指的是待排序记录存放在计算机随机存储器中进行的排序过程。
外部排序: 指的是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程。
内部排序与外部排序
假设 Ki = Kj ,且排序前序列中 Ri 领先于 Rj ;
若在排序后的序列中 Ri 仍领先于 Rj ,则称排序方法是稳定的。
若在排序后的序列中 Rj 仍领先于 Ri ,则称排序方法是不稳定的。
例,序列 3 15 8 8 6 9
若排序后得 3 6 8 8 9 15
稳定的
若排序后得 3 6 8 8 9 15
不稳定的
排序衡量指标——稳定性
排序衡量指标——时间复杂度
排序过程主要是对记录的排序码进行比较和记录的移动过程。
排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。
当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少,则认为该方法的时间复杂性就越好,分析一种排序方法,不仅要分析它的时间复杂性,而且要分析它的空间复杂性、稳定性等。
按照排序过程中所依据的原则的不同可以分类为:
插入排序
交换排序(快速排序)
选择排序
归并排序
基数排序
二叉排序树排序
内部排序
思想: 利用有序表的插入操作进行排序
有序表的插入: 将一个记录插入到已排好序的有序表中,从而得到一个新的有序表。
例,序列 13 27 38 65 76 97
插入 49
13 27 38 49 65 76 97
插入排序——直接插入排序
直接插入排序——算法描述
例,序列 49 38 65 97 76 13 27
初始,S = { 49 } ;
{ 38 49 }
初始,令第 1 个元素作为初始有序表;
依次插入第 2 , 3 , …, k 个元素构造新的有序表;
直至最后一个元素;
{ 38 49 65 }
{ 38 49 65 97 }
{ 38 49 65 76 97 }
{ 13 38 49 65 76 97 }
{ 13 27 38 49 65 76 97 }
直接插入排序算法主要应用比较和移动两种操作。
void Insert(ArrNode * pnum)
{
for (i = 1; i < Len; i++) {
tmp = pnum[i];
for (j = i; j > 0 && < pnum[j - 1].key; j--) {
pnum[j] = pnum[j - 1];
}
pnum[j] = tmp;
}
}
直接插入排序——算法描述
时间复杂度分析:
外层循环要进行n-1次插入,每次插入最少比较一次(正序),移动两次;最多比较i次,移动i+2次(逆序)(i=1,2,…,n-1)。
Cmin=n-1 M min=2(n-1)
Cmax=1+2+…+n-1=(n2-n)/2
M max=3+4+…+n+1=(n2+3n-4)/2
Cave=(n2+n-2)/4
M max=(n2+7n-8)/4
因此,直接插入排序的时间复杂度为O(n2)。
直接插入算法的元素移动是顺序的,该方法是稳定的。
直接插入排序的效率分析
由于直接插入排序算法利用了有序表的插入操作,故顺序查找操作可以替换为折半查找操作。
例,序列 49 38 65 97 76 13 27
设已形成有序表{ 38 49 65 97 76 }
插入元素 13
折半插入排序
void BinaryInsertSort( ArrNode *pnum ,int L)
{ for(int i=1; i<L; i++) //共进行n-1次插入
{int left=0,right=i-1; temp=pnum[i];
while(left<=right)
{ int middle=(left+right)/2; //取中点
if(temp<pnum[middle])
right=middle-1; //取左区间
else
left=middle+1; //取右区间
} for(int j=i-1;j>=left;j--)
pnum[j+1]=pnum[j]; //元素后移空出插入位
pnum[left]=temp;
}
}
折半插入排序——算法描述

最近更新

2025年度土地承包经营权转让及种植项目合作协.. 9页

2025年度国际贸易居间合伙人佣金结算与供应链.. 9页

2025年度国际会议组织服务合同份 9页

数字身份认证中的唯一标识技术研究-全面剖析 27页

2025年度商铺分租及新能源技术应用合同 9页

2025年度商品陈列效果评估与消费者行为研究协.. 8页

2025年度商业综合体商铺转租合同协议书 8页

2025年度品牌设计项目委托合同 8页

2025年度员工租房补贴及住房贷款还款协议模板.. 8页

2025年度员工入职培训与考核协议范本 8页

2025年度吊装作业安全培训及应急演练协议 8页

2025年度合同买卖纠纷管辖权变更执行协议 8页

2025年度合伙协议书:适用于教育培训机构联合.. 9页

2025年度双方约定付款协议书:虚拟现实教育培.. 8页

2025年度危险化学品运输行业安全生产培训合同.. 9页

2025年度单位用工协议(太空探索项目) 9页

2025年度医院病理科与检验试剂生产企业合作合.. 9页

2025年度医疗纠纷协议书式五份,针对新生儿护.. 8页

2025年度医疗卫生机构医护人员技能提升委托培.. 9页

2025年度区块链技术应用劳动合同签收台账编制.. 8页

2025年度劳动合同法在环保产业的执行与保障 9页

2025年度劳务借工安全责任协议范文 7页

2025年度办公文具及礼品定制采购合同 9页

2025年度制造业企业员工就业合同范本 9页

2025年度分手后双方共同财产清算及税务处理协.. 9页

2025年度出租房租赁期间租赁物租赁权抵押合同.. 8页

2025年度冷链物流公路运输全程跟踪合同 8页

2025年度农民工劳务合同协议专业版(社会福利.. 8页

2025年度农村耕地流转监管合同 8页

2025年度农村房屋土地租赁合同——农村房屋租.. 8页