1 / 33
文档名称:

数据结构排序算法.ppt

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

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

分享

预览

数据结构排序算法.ppt

上传人:wc69885 2015/5/22 文件大小:0 KB

下载得到文件列表

数据结构排序算法.ppt

相关文档

文档介绍

文档介绍:第九章排序
本章要求
【教学目的】掌握内排序方法的插入排序;选择排序;交换排序;基数排序;归并排序;排序的存储方式:连续地址、静态链表、索引;稳定的和不稳定的排序方法的判定方法,常见的稳定的排序方法和的不稳定的排序方法。了解外部排序的方法以及外部排序方法的特点。
【教学重点】每种排序方法的算法及算法的性能分析
【教学难点】排序方法的比较及稳定性的确定
第八章查找
一、基本概念
二、插入排序
三、交换排序
四、选择排序
五、归并排序
一、基本概念
排序的目的
排序是为了通过关键字高效的查找相关的记录
排序
就是要调整原文件中的记录顺序,使之按关键字递增(或递减)次序排列起来。其形式化定义描述如下:
输入:n个记录r1,r2,…,rn,其相应的关键字分别为k1,k2,…,kn
输出:rl′,r2′,…,rn′,使得k1′≤k2′≤…≤kn′。
(或k1′≥k2′≥…≥kn′) //有序升序或者降序
一、基本概念
排序的数据结构
待排序的记录采用顺序存储,待排序记录的定义为:
#define MAXSIZE 100 /*假定顺序表的最大长度为100 */
typedef int KeyType; /* 假定关键字类型为整数类型*/
typedef struct {
KeyType key;/* 关键字项*/
OtherType other;/* 其他项*/
}DataType;/* 数据元素类型*/
typedef struct {
DataType r[MAXSIZE +1];
/* r[0]闲置或充当哨兵*/
int length;/* 顺序表长度*/
} SqList;/* 顺序表类型*/
一、基本概念
排序的数据结构
排序的稳定性:若存在关键字相同的多个记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;否则则称这种排序方法是不稳定的。
排序的分类:按是否涉及数据的内、外存交换分类:内排序、外排序。
内部排序方法有:插入排序、选择排序、交换排序、归并排序
排序的效率分析:时间代价和空间代价
二、插入排序
基本思想
通过构建有序序列,将待排序的数据,在已排好序的序列中从后向前扫描,找到其相应位置并进行插入操作。
直接插入排序
二分法插入排序
Shell排序
二、插入排序
直接插入排序
算法思想: 将待插入子序列元素逐步插入到有序子序列中,设有一待排序序列S={r1,r2,r3,…,ri,…,rn},其中{r1,r2,…,ri}(1≤i≤n)是按照关键字{k1≤k2≤…≤ki}有序的子序列,序列{ ri+1,…,rn } 无序。从序列{ ri+1,…,rn }的第一个元素ri+1开始取数据元素,每取一个元素就将其插入到前面的有序序列中,并使插入后的序列有序,直到所有元素插入完成,得到一个有序序列。
二、插入排序
直接插入排序
算法:
void StraightInsertSort(SqList *S)
{ /* 对顺序表s中的s->r[1..length]作直接插入排序*/
for(i=2;i<=S->length;i++)
{ S->r[0]=S->r[i]; /*复制为哨兵*/
j= i-1;
while (S->r[0].key < S->r[j].key)
{ S->r[j+1]=S->r[j];
j-- ;
} /*记录后移*/
S->r[j+1]=S->r[0]; /*插入到正确位置*/
}
}
能不能
改为<=?
二、插入排序
直接插入排序
效率分析:
空间效率:用了一个辅助单元r[0],因此辅助空间为O(1)
时间效率:
最好情形:待排序序列中各数据元素在排序前已按关键字大小排好序,总的比较次数=n-1次,总的移动次数=n-1次,所以时间复杂度为O(n)
最坏情形:待排序序列中各数据元素为逆序状态时,
直接插入排序是稳定的排序算法
二、插入排序
二分插入排序
算法思想:在插入第i个关键码时,前i-1个关键已经有序,可以通过折半的方式找到插入点。
但是,虽然可以更快地找到插入点,但意义不大?
因为,找到插入点后还需要进行移动元素,并没有改变移动元素的次数,因此其时间复杂度并没有发生改变。

最近更新

主要养殖鱼类的生物学 85页

2025年度智慧交通系统人工费投入合同 9页

2025年度旅游行业导游劳务劳动合同书电子版 8页

2025年度旅游团意外伤害及工伤赔款协议 8页

2025年度新能源车干股分红与充电设施建设协议.. 7页

为老年人提供适宜居住环境 15页

2025年度新材料研发对赌技术突破合同 9页

2025年度文化创意产业委托招商代理协议 8页

2025年度文化产业增资扶持协议 9页

2025年度数据中心机房工装装饰施工协议 8页

2025年度教育行业劳动合同得定义与教师权益保.. 8页

2025年度教育培训机构教职工年度劳动合同示范.. 8页

2025年度教育咨询外包合同终止协议书 7页

2025年度手术室装修工程与医疗废弃物处理服务.. 9页

2025年度房产租赁不过户管理服务协议 8页

2025年度成年子女父母离婚协议书:子女监护权.. 8页

2025年度建筑项目专用商品混凝土供应协议 9页

2025年度店铺员工劳动合同续签与变更 7页

2025年度广告媒体资源整合与营销合同 9页

2025年度幼儿园教师聘用协议(幼儿教育创新项.. 9页

2025年度幼儿园与亲子游服务机构合作亲子旅游.. 8页

2025年度带小孩保姆家庭育儿指导与生活助手服.. 8页

2025年度工程项目验收与移交咨询服务合同 8页

2025年度工厂员工社会责任与雇佣劳务合同模板.. 9页

2025年度工业厂房租赁与智能化改造升级合同 8页

实用的周记高中作文锦集10篇 15页

2025年度山地农业租赁经营合同 8页

2025年度屋顶光伏发电设备安装与智能化监控服.. 9页

2025年度小学生托管安全防护及紧急救援服务合.. 9页

小学生竞选演讲稿200字(29篇) 27页