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年八年级生物预防传染病攻略苏科版深度解.. 65页

二零二五年度个体工商户新能源产品销售代理合.. 9页

二零二五年度个人车辆公司租赁及使用管理合同.. 8页

2025年儿童胰腺炎急救与防治攻略 14页

二零二五年度个人租车安全责任保障合同 8页

2025年情侣暖心个性签名 20页

2025年情人节秀恩爱说说大全 9页

二零二五年度个人服装销售合作协议 9页

二零二五年度个人房产置换合同范本 8页

二零二五年度个人对公司基础设施建设借款合同.. 8页

二零二五年度个人创业项目融资协议书 8页

二零二五年度个人入股绿色农业发展基金投资合.. 8页

2025年低钾血症护理要点与查房实战攻略 31页

二零二五年度专业市场摊位租赁管理范本 8页

公共事业收费制度改革-全面剖析 24页

2025年传染病科普知识 14页

2025年传染病上报关键要点指南 13页

2025年怎么写读书笔记才好 5页

二零二五年度三人合作开设高端美容院合作协议.. 8页

2025年怎么写好工作年末自我鉴定 6页

二零二五年个人肖像权游戏角色配音演员授权使.. 8页

2025年怀孕辞职申请书范文 4页

二零二五中途入股合同——农业科技项目股权合.. 8页

事业单位解除聘用合同员工权益保障及过渡期服.. 8页

中高管聘用合同(2025年度):企业战略发展关.. 7页

2025年快乐的寒假作文2025 7页

2025年骶髂关节炎CT扫描诊断要点 44页

2025年安徽省初中学业水平考试名校联考(一)数.. 2页

初三毕业班2025届中考数学复习计划2 5页

2024年江苏泰州兴化市事业单位招考公开招聘历.. 241页