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个关键已经有序,可以通过折半的方式找到插入点。
但是,虽然可以更快地找到插入点,但意义不大?
因为,找到插入点后还需要进行移动元素,并没有改变移动元素的次数,因此其时间复杂度并没有发生改变。

最近更新

2025年度农村旅游民宿建筑设计与施工合同 9页

2025年度农村房屋租赁合同房东免责条款规定 8页

2025年度农村房屋修建与环保建材供应合同 9页

2025年度农村房屋买卖与乡村旅游合作合同 9页

2025年度农村小产权房屋买卖资金监管及支付保.. 8页

麻醉前访视和准备 29页

2025年度农村土地纠纷调解合同示范文本 7页

2025年度农村土地流转承包经营权流转收益分配.. 8页

2025年度农村土地承包经营权流转与农业绿色生.. 9页

2025年度农村土地买卖合同系列:农村集体建设.. 9页

2025年度农村个人住宅施工质量保证金协议 8页

2025年度农机作业服务与农业市场拓展合作协议.. 10页

2025年度农家乐乡村旅游项目投资合同 8页

高阶表达训练精 60页

上海市市西初级中学2024-2025学年八年级下学期.. 22页

安徽省六安市第九中学2024-2025学年九年级下学.. 25页

2025年提升机合作协议书 49页

2025年数据中心合作协议书 59页

2025年年度假村项目合作计划书 57页

2025年抗生素类药品合作协议书 62页

2025年工业仪表项目合作计划书 39页

2025年干燥设备项目发展计划 57页

2025年成品窗帘项目建议书 64页

高等数学复习课件CH 33页

高等学校会计制度 35页

医药包装材料的环境影响评估-全面剖析 27页

多普勒雷达技术在交通事故快速响应中的角色-全.. 27页

最新部编版三年级下册语文全册教案 106页

村后备干部笔试试题及答案 5页

土地整理项目技术交底教学内容 4页