当前位置：文档之家 › 数据结构课件第十章

数据结构课件第十章

  • 格式：pptx
  • 大小：456.40 KB
  • 文档页数：59

下载文档原格式

  / 59

合集下载

数据结构第十章共48页PPT资料

数据结构第十章共48页PPT资料
3
.各节给出算法运行时间代价的大略估算一般都 按平均情况进行估算.对于那些受对象关键码序 列初始排列及对象个数影响较大的,需要按最好 情况和最坏情况进行估算.
.插入排序
.插入排序的基本思想每步将一个待排序的对象, 按其关键码大小,插入到前面已经排好序的一组 对象的适当位置上,直到对象全部插入为止.
Байду номын сангаас .内部排序:待排序的序列存放在计算机的内存 中进行的排序过程.
.外部排序:若待排序的记录量很大,以致内存中一 次不能容纳全部记录,在排序过程中需对外存进行 访问的排序过程.
.本章讨论内部排序,且所有关键字都是整数,待排 序的记录以顺序存储结构存储.
.排序的时间开销:排序的时间开销是衡量算法好 坏的最重要的标志.排序的时间开销可用算法执行 中的数据比较次数与数据移动次数来衡量.
21 25 49 25* 16 08
13
21 16 08 25* 25 49
i=2
012345
Gap = 2
21 16 08 25* 25 49
21 16 08 25* 25 49
08 16 21 25* 25 49
14
08 16 21 25* 25 49
i=3
012345
Gap = 1
08 16 21 25* 25 49
然后缩小间隔 gap,例如取 gap = gap/2,重复 上述的子序列划分和排序工作.
直到最后取 gap == 1,将所有对象放在同一个 序列中,排序就结束.
12
21 25 49 25* 16 08
i=1
012345
Gap = 3
21 25 49 25* 16 08
21 25 49 25* 16 08

数据结构-第十章-内部排序

数据结构-第十章-内部排序

0
1
2
3
4
5
6
7
8
i=5
MAXINT 49 2 3
MAXINT 49 6 3 MAXINT 49 6 3 MAXINT 49 6 8
38 1
38 1 38 1 38 1
65 97 5 0
65 5 65 5 65 5 97 0 97 0 97 0
76 4
76 4 76 4 76 4
13
27
49
i=6



最坏情况下,待排记录按关键字非递增有序 排列（逆序）时，第 i 趟时第 i＋1 个对象 必须与前面 i 个对象都做排序码比较, 并且 每做1次比较就要做1次数据移动。总比较 次 数 为 (n+2)(n-1)/2 次 ， 总 移 动 次 数 为 (n+4)(n-1)/2。 在平均情况下的排序码比较次数和对象移 动次数约为 n2/4。因此，直接插入排序的 时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。
折半插入排序 (Binary Insertsort)
基本思想 既然每个要插入记录之前的纪录 已经按关键字有序排列，在查找插入位 臵时就没有必要逐个关键字比较，可以 使用折半查找来实现。由此进行的插入 排序称之为折半插入排序。
折半插入排序的算法
void BInsertSort (SqList &L){ for (i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; //查找范围由1到i-1 while(low<=high){ m=(low+high)/2; if LT(L.r[0].key,L.r[m].key) high=m-1; else low=m+1; }//while 折半查找 for (j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; //折半查找结束后high+1位臵即为插入位臵 L.r[high+1]=L.r[0]; }//for }//BInsertSort

数据结构讲义第10章排序ppt课件

数据结构讲义第10章排序ppt课件

R[j]＝temp;
flag＝1;
}
}
2021精选ppt
25
10.3 交换排序
10.3.1冒泡排序(Bubble Sort)
4、算法分析： 起泡排序的最坏时间复杂度为O(n2)，平均时间复杂度为 O(n2)。 起泡排序算法中增加一个辅助空间temp，辅助空间为 S(n)=O(1)。 起泡排序是稳定的。
整个排序进行n-1趟插入。
2021精选ppt
10
10.2 插入排序
10.2.1直接插入排序
2、示例： 初始： [49] 38 65 97 76 13 27 49 i=1: [38 49] 65 97 76 13 27 49 i=2: [38 49 65] 97 76 13 27 49 i=3: [38 49 65 97] 76 13 27 49 i=4: [38 49 65 76 97] 13 27 49 i=5: [13 38 49 65 76 97] 27 49 i=6: [13 27 38 49 65 76 97] 49
此后，再对存放在R1,R2,R3,…,Rn-1中n-1个记录作同样处理,结果，最 大者在Rn-1中。
…。
n-1次起泡能完成排序。设置标志noswap表示本次起泡是否有交换， 若无交换，表示排序完成。
2021精选ppt
23
10.3 交换排序
10.3.1冒泡排序(Bubble Sort)
2、示例：
初始 1 2 3 4 5 6
r[lppt
16
10.2 插入排序
10.2.2折半插入排序
4、算法分析： 算法分析：
空间效率：同直接插入排序 时间效率：比较次数确定：
n log2i nlog2n i=1 移动记录次数：平均移动次数为O(n2) 时间复杂度为O(n2)

第十章_排序方法(数据结构ppt-严蔚敏)

第十章_排序方法(数据结构ppt-严蔚敏)

第二个问题解决方法——筛选
方法：输出堆顶元素之后，以堆中最后一个元素替代之；然 后将根结点值与左、右子树的根结点值进行比较，并与其中 小者进行交换；重复上述操作，直至叶子结点，将得到新的 堆，称这个从堆顶至叶子的调整过程为“筛选”
例 38 50 97 76
13 27 65 49 13 38
97 27 38 50 76
2 (n 4)(n 1) 记录移动次数： (i 1) 2 i 2
i 2 n
若待排序记录是随机的，取平均值 n2 关键字比较次数： T(n)=O(n² ) 4 记录移动次数：
空间复杂度：S(n)=O(1)
n2 4
折半插入排序
排序过程：用折半查找方法确定插入位置的排序叫~
初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp 交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录， 和rp交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有 一个记录为止
x 例 初始关键字： 27 49 i 完成一趟排序： ( 27 38 13 49 65 i 13) 49 97 76 j 97 49 13 j 97 65 49 27 50 j 50)
13 38
76 65 27 49
堆排序：将无序序列建成一个堆，得到关键字最小 （或最大）的记录；输出堆顶的最小（大）值后，使 剩余的n-1个元素重又建成一个堆，则可得到n个元素 的次小值；重复执行，得到一个有序序列，这个过程 叫~ 堆排序需解决的两个问题：
如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新 的堆？
按排序所需工作量

数据结构 chapter10

数据结构 chapter10

Department of Computer Science & Technology, Nanjing University
fall
DATA STRUCTURES
多级索引结构形成 m 路搜索树
Department of Computer Science & Technology, Nanjing University
第10章 文件组织、索引结构
文件组织 动态索引结构
Department of Computer Science & Technology, Nanjing University Data Structure
fall
10.1 文件组织
DATA STRUCTURES
文件的基本概念
什么是文件 文件是存储在外存上的数据结构。 文件分操作系统文件和数据库文件
是指向子树的指针，0 i n < m；Ki 是关键码， 1 i n < m。 Ki < Ki+1, 1 i < n。
▪ 在子树 Pi 中所有的关键码都小于 Ki+1，且大于 Ki， 0 < i < n。
▪ 在子树 Pn 中所有的关键码都大于Kn； ▪ 在子树 P0 中的所有关键码都小于 K1。 ▪ 子树 Pi 也是 m 路搜索树，0 i n。
Department of Computer Science & Technology, Nanjing University
fall
DATA STRUCTURES
索引表用于指示逻辑记录与物理记录间的对应关 系，它是按关键码有序的表。
索引顺序文件：主文件也按关键码有序。此时 可对主文件分组，一组记录对应一个索引项。 称这种索引表为稀疏索引。

数据结构chapter_10

数据结构chapter_10

typedef struct { //定义每个记录 数据元素) 定义每个记录( //定义每个记录(数据元素)的结构 KeyType key ; //关键字 //关键字 InfoType otherinfo; //其它数据项 //其它数据项 }RedType; //记录类型 //记录类型 typedef struct { //定义顺序表 定义顺序表L //定义顺序表L的结构 RecordType r [ MAXSIZE +1 ]; //存储顺序表的向量 //存储顺序表的向量 //r[0] r[0]一般作哨兵或缓冲区 //r[0]一般作哨兵或缓冲区 int length ; //顺序表的长度 //顺序表的长度 }SqList; //顺序表类型 //顺序表类型
void BInsertSort (SqList &L) {
// 对顺序表 作折半插入排序 对顺序表L作折半插入排序 for ( i=2; i<=L.length; ++i ) { L.r[0] = L.r[i]; // 将L.r[i]暂存到 暂存到L.r[0] 暂存到 low = 1; high = i-1; while (low<=high) { // 在r[low..high]中折半查找有序插入的位置 中折半查找有序插入的位置 m = (low+high)/2; // 折半 if (L.r[0].key < L.r[m].key) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 } // while for ( j=i-1; j>=low; --j ) L.r[j+1] = L.r[j]; // 记录后移 // 插入 L.r[high+1] = L.r[0]; } } // BInsertSort

数据结构(严蔚敏)完整第10章ppt课件


一般情况下，
假设含n个记录的序列为{ R1, R2, …， Rn } 其相应的关键字序列为 { K1, K2, …，Kn }
这些关键字相互之间可以进行比较，即在
它们之间存在着这样一个关系 ：
Kp1≤Kp2≤…≤Kpn
按此固有关系将上式记录序列重新排列为
{ Rp1, Rp2, …，Rpn }
的操作称作排序。
有序序列区 无 序 序 列 区
经过一趟排序
有序序列区 无 序 序 列 区
03.07.2020
.
11
基于不同的“扩大” 有序序列长 度的方法，内部排序方法大致可分 下列几种类型：
插入类 交换类 选择类
归并类 其它方法
03.07.2020
.
12
#待de排fin记e M录A的XS数IZ据E 类10型00定// 待义排如顺下序:表最大长度
03.07.2020
.
15
3. 选择类
从记录的无序子序列中“选择” 关键字最小或最大的记录，并将它 加入到有序子序列中，以此方法增 加记录的有序子序列的长度。
03.07.2020
.
16
4. 归并类
通过“归并”两个或两个以上的 记录有序子序列，逐步增加记录有 序序列的长度。
5. 其它方法
03.07.2020
.
5
03.07.2020
10.1 概述
10.2 插入排序
10.3 快速排序
10.4 堆排序 10.5 归并排序
10.6 基数排序
10.7 各种排序方法的综合比较
03.07.2020
10.8 外. 部排序
6
10.1 概 述
一、排序的定义 二、内部排序和外部排序 三、内部排序方法的分类

数据结构课件 第10章

数 据 结 构 第10章 内部排序10.1 概述•什么是排序？–排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

–若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

10.1 概述•待排序的数据类型#define MAXSIZE 1000 // 待排顺序表最大长度typedef int KeyType; // 关键字类型为整数类型typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项} RcdType; //记录类型typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; // 顺序表长度} SqList; // 顺序表类型#define MAXSIZE 1000 // 待排顺序表最大长度typedef int KeyType; // 关键字类型为整数类型typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项} RcdType; //记录类型typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; // 顺序表长度} SqList; // 顺序表类型10.1 概述•内部排序的类别–插入类：将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。

–交换类：通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。

–选择类：从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。

–归并类：通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。

数据结构第十章 排序

7
10.2 插入排序 插入排序
直接插入排序 折半插入排序 2-路插入排序 表插入排序 希尔排序
10.2.1 直接插入排序
基本操作：将一个记录插入到已排好序的有序表中， 从而得到一个新的、记录数增1的有序表。
例:有一组待排序的记录的关键字初始序列如下:
(49,38,65,97,76,13,27,49`)
（4）归并排序 （5）基数排序
按内排过程中所需的工作量分类：
（1）简单的排序方法，其时间复杂度为O(n×n)
（2）先进的排序方法，其时间复杂度为O(nlogn);
（3）基数排序，其时间复杂度为O(d(n+rd))
排序算法的两种基本操作：
（1）比较两个关键字的大小； （2）将记录从一个位置移至另一个位置；
算法实现的关键设计:
将d看成是一个循环数组,并设两个指针first和final分别指示排序过 程中得到的有序序列中的第一个记录和最后一个记录在d中的位置.
例:有一组待排序的记录的关键字初始排列如下:
(49,38,65,97,76,13,27,49`) 16
[初始关键字] 49 38 65 97 76 13 27 49`
18
10.2.3 希尔排序 从直接插入排序
待排序序列基本有序可提高效率 回顾 待排序序列的记录数n很小时可提高效率
希尔排序的基本思想:
先将整个待排记录序列分割成为若干子序列分别进行
直接插入排序,待整个序列中的记录“基本有序”时,再对 全
体记例录:有进一行组一待次排直序接的插记入录排的序关. 键字初始排列如下: (49,38,65,97,76,13,27,49`)
} 12
直接插入排序的性能分析: 10. 3
(1)空间:只需一个记录的辅助空间r[0].
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1
第十章 内部排序
9.1 概述 9.2 插入排序 9.3 交换排序 9.4 选择排序 9.5 归并排序 9.6 基数排序
2
10.1 概述
1、排序是计算机内经常进行的一种操作，其目的是将一 组“无序”的记录序列调整为“按关键字有序”的记录序 列。 52，49，80，36，14，58，61，23，97，75
例1：关键字序列T=（13，6，3，31，9，27，5，11），
请写出直接插入排序的中间过程序列。
【13】, 6, 3, 31, 9, 27, 5, 11 【6, 13】, 3, 31, 9, 27, 5, 11 【3, 6, 13】, 31, 9, 27, 5, 11 【3, 6, 13，31】, 9, 27, 5, 11 【3, 6, 9, 13，31】, 27, 5, 11 【3, 6, 9, 13，27, 31】, 5, 11 【3, 5, 6, 9, 13，27, 31】, 11 【3, 5, 6, 9, 11，13，27, 31】
d＝关键字的位数(长度)
8
9.2 插入排序
插入排序的基本思想是：每步将一个待排序的对象， 按其关键码大小，插入到前面已经排好序的一组对象 的适当位置上，直到对象全部插入为止。
简言之，边插入边排序，保证子序列中随时都是排好序的。
插入排序有多种具体实现算法： 1) 直接插入排序 2) 折半插入排序 3) 希尔排序
3
2、关键字
数据对象有多个属性域，即多个数据成员组成，其中有一个 属性域可以用来区分对象，作为排序依据，称为关键字。
关键字与记录之间是一对一的关系 称主关键字 关键字与记录之间是一对多的关系 称次关键字
4
3、排序的目的是什么？
—— 便于查找
4、排序算法的好坏如何衡量？
❖ 时间效率 —— 排序速度（即排序所花费的全部比较次数） ❖ 空间效率 —— 占内存辅助空间的大小 ❖ 稳定性 —— 若两个记录A和B的关键字相等，但排序后A，
6
6、排序主要做的工作： 比较 + 移动
7
7. 内部排序的算法有哪些？
——按排序的规则不同，可分为5类： • 插入排序 • 交换排序（重点是快速排序） • 选择排序 • 归并排序 • 基数排序
——按排序算法的时间复杂度不同，可分为3类： •简单的排序算法：时间效率低，O(n2) •先进的排序算法: 时间效率高，O( nlog2n ) •基数排序算算法：时间效率高，O( d×n)
时间效率：虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为O(n2) 。
空间效率： O（1） 稳定性：稳定
对应程序见教材P267（仅用于顺序表） 讨论：若记录是链表结构，用直接插入排序行否？折半插入排
序呢？ 答：直接插入不仅可行，而且还无需移动元素，时间效率更高！
但链表无法“折半”！
12
14，23，36，49，52，58，61，75，80，97
一般情况下， 假设含n个记录的序列为{R1，R2，……，Rn} 其相应的关键字序列为 {K1，K2，……，Kn} 这些关键字相互之间可以进行比较， 即在它们之间存在这样一个关系：Kp1<=Kp2<=…<=Kpn 按此固有关系将上式记录序列重新排列为{Rp1,Rp2,…,Rpn} 的操作称作排序
B的先后次序保持不变，则称这种排序算法是稳定的。
5
5、什么叫内部排序？什么叫外部排序
内部排序和外部排序的不同在于能否一次处 理完所有数据
—— 若待排序记录都在内存中，称内部排序 —— 若待排序记录一部分在内存，一部分在外存，则称为外 部排序。 注：外部排序时，要将数据分批调入内存来排序，中间结果 还要及时放入内存，显然外部排序要复杂得的多。
10
– 例题 对下列存放在数组A中的序列采用直接插 入排序法排序。
A[0]
49 38 65
A[1] A[2] A[3]
97
A[4]
76
A[5]
13 27 49
A[6] A[7] A[8]
2347178963 413938 33248879 4695 76946579 74966975 179367 297 49
9
1) 直接插入排序
最简单的排序法！
新元素插入到哪里？ 在已形成的有序表中线性查找，并在
适当位置插入，把原来位置上的元素向后顺移。
例1：关键字序列T=（13，6，3，31，9，27，5，11），
请写出直接插入排序的中间过程序列。
【13】, 6, 3, 31, 9, 27, 5, 11 【6, 13】, 3, 31, 9, 27, 5, 11 【3, 6, 13】, 31, 9, 27, 5, 11 【3, 6, 13，31】, 9, 27, 5, 11 【3, 6, 9, 13，31】, 27, 5, 11 【3, 6, 9, 13，27, 31】, 5, 11 【3, 5, 6, 9, 13，27, 31】, 11 【3, 5, 6, 9, 11，13，27, 31】
14
3）希尔（shell）排序（又称缩小增量排序）
基本思想：先将整个待排记录序列分割成若干子序列,分 别进行直接插入排序，待整个序列中的记录“基本有序” 时，再对全体记录进行一次直接插入排序。 技巧：子序列的构成不是简单地“逐段分割”，而是将 相隔某个增量dk的记录组成一个子序列,让增量dk逐趟 缩短（例如依次取5,3,1），直到dk＝1为止。 优点：让关键字值小的元素能很快前移，且序列若基本 有序时，再用直接插入排序处理，时间效率会高很多。
监视哨
待排元素待排元素待排元素待排元素待排元素待排元素待排元素
第 1234567 趟插入排序 排序趟数=数据个数-1 注 紫色 表示待排数据；蓝色 表示已经有序数据
11
2） 折半插入排序
新元素插入到哪里？在已形成的有序表中折半查找，并在适 当位置插入，把原来位置上的元素向后顺移。
优点：比较的次数大大减少，全部元素比较次数仅为 O(nlog2n)。
13
例：有6个记录，前5 个已排序的基础上，对第6个记录排序。 [ 15 27 36 53 69 ] 42
low
mid
( 42>36 )
[ 15 27 36 53
high
69 ] 42
[ 15 27 36
low high mid ( 42<53 )
53 69 ] 42
[ 15 27 36 42 53 69 ]