《数据结构》 第十章内部排序
《数据结构》 第十章 内部排序
第十章内部排序 第十章内部排序 内容和要求 排序及有关的概念,直接插入排序、三分法插入排 序、表插入排序,shel排序,直接选择排序、树形选择 排序、堆排序、冒泡排序和快速排序、基数排序、归并 排序。 要求通过学习,掌握排序的各种方法,为解决实际 问题奠定理论基础的技术基础。了解排序和排序码的概 熟悉直接插入排序、二分法插入排序、表插入排序 She排序的方法和时空复杂性 掌握堆排序、快速排序、基数排序、归并排序的基 一本思路,排序方法,算法的主要步骤和时空复杂性; 知道Mhe排序和树形选择排序方法 第2页
第十章 内部排序 第2页 第十章 内部排序 内容和要求 排序及有关的概念，直接插入排序、二分法插入排 序、表插入排序，shell排序，直接选择排序、树形选择 排序、堆排序、冒泡排序和快速排序、基数排序、归并 排序。 要求通过学习，掌握排序的各种方法，为解决实际 问题奠定理论基础的技术基础。了解排序和排序码的概 念， 熟悉直接插入排序、二分法插入排序、表插入排序 、Shell排序的方法和时空复杂性； 掌握堆排序、快速排序、基数排序、归并排序的基 本思路，排序方法，算法的主要步骤和时空复杂性； 知道 shell 排序和树形选择排序方法
●概述 第十章内部排序 如何对一大批按关键字无序的数据元 素或记录,高效率地将它们重新排列成 个按关键字有序的序列,是计算机应 用中的重要课题之一。 可以假定被排序的对象是由一组记录 组成的文件,而记录则由若干个数据项 (或字段、域)组成,其中有一项可用 来标识一个记录,称为关键字,它具关 键字值。关键字是排序操作的依据 第3页
第十章 内部排序 第3页 概 述 如何对一大批按关键字无序的数据元 素或记录，高效率地将它们重新排列成 一个按关键字有序的序列，是计算机应 用中的重要课题之一。 可以假定被排序的对象是由一组记录 组成的文件，而记录则由若干个数据项 （或字段、域）组成，其中有一项可用 来标识一个记录，称为关键字，它具关 键字值。关键字是排序操作的依据。 ⚫
●概述 第十章内部排序 定义1:假设含n个记录的序列为 {R1,R2…,Rn (10-1) 其相应的关键字序列为 K1,K2,…,K 需确定1,2,,n的一种排列P n 使其相应 的关键字满足如下的非递减(或非递增)关系 K<K 10-2 n 即使式(10-1)的序列成为一个按关键字有序的序列 RRoI, R Ron j (10-3) 这样一种操作称为排序。 显然,当待排记录的关键字均不相同时,则排序的结果 一是唯一的,否则排序的结果不一定唯一。特别地,按主关键 字进行排序,其排序的结果是唯一的。而若按次关键字进行 排序,结果不一定唯一 第4页
第十章 内部排序 第4页 定义1： 假设含 n 个记录的序列为 {R1，R2，···，Rn } (10-1) 其相应的关键字序列为 {K1，K2，···，Kn } 需确定 1,2,···,n 的一种排列 P1，P2，···，Pn ，使其相应 的关键字满足如下的非递减（或非递增）关系 Kp1≤Kp2 ≤ ··· ≤ Kpn (10-2) 即使式 (10-1) 的序列成为一个按关键字有序的序列 {Rp1，Rp2 ，···， Rpn } (10-3) 这样一种操作称为排序。 ⚫概 述 显然，当待排记录的关键字均不相同时，则排序的结果 是唯一的，否则排序的结果不一定唯一。特别地，按主关键 字进行排序，其排序的结果是唯一的。而若按次关键字进行 排序，结果不一定唯一
●概述 第十章内部排序 定义2:如果待排序的文件中,存在有多个关键字 相同的记录,经过排序后这些具有相同关键字的记录之 间的相对次序保持不变,则称这种排序方法是稳定的; 反之,若具有相同关键字的记录之间的相对次序发生变 化,则称这种排序方法是不稳定的。 定义3:在排序过程中,若整个文件都是放在内存 中处理,排序时不涉及数据的内、外存交换,则称为内 部排序,筒称内排序;反之,若排序过程中要进行数据 的内、外存交换,则称之为外部排序,筒称外排序字。 第5页
第十章 内部排序 第5页 定义2： 如果待排序的文件中，存在有多个关键字 相同的记录，经过排序后这些具有相同关键字的记录之 间的相对次序保持不变，则称这种排序方法是稳定的； 反之，若具有相同关键字的记录之间的相对次序发生变 化，则称这种排序方法是不稳定的。 定义3 ： 在排序过程中，若整个文件都是放在内存 中处理，排序时不涉及数据的内、外存交换，则称为内 部排序，简称内排序；反之，若排序过程中要进行数据 的内、外存交换，则称之为外部排序，简称外排序。 ⚫概 述
●概述 第十章内部排序 各种排序方法可以按照不同的原则加以分类 内部排序方法的分类: 按所用策略进行分类 (1)插入排序 (2)交换排序 (3)选择排序 (4)归并排序 (5)计数排序 二、按所鼎工作量进行分类 1)简单的排序方法O(m2) (2)先进的排序方法O( nlogn) (3)基数排序 o(don) 第6页
第十章 内部排序 第6页 ⚫概 述 各种排序方法可以按照不同的原则加以分类。 内部排序方法的分类： 一、按所用策略进行分类 (1) 插入排序 (2) 交换排序 (3) 选择排序 (4) 归并排序 (5) 计数排序 二、按所需工作量进行分类 (1) 简单的排序方法 O(n 2 ) (2) 先进的排序方法 O(nlogn) (3) 基数排序 O(d•n)
●概述 第十章内部排序 在排序的过程中需进行的巫种基本操作 )比较两个关键字的大 (2)将记录从一个位置移动至另一个位置。 前一个操作对大多数排序方法来说都是必要的,而 后一种操作可以通过改变记录的存储方式来予以避免。 排序的时间开销是算法好坏的最重要的标志。排序 的时间开销主要可以用算法热行中关键字的比较次数和 记录的移动次数来衡量。 第7页
第十章 内部排序 第7页 在排序的过程中需进行的两种基本操作： (1) 比较两个关键字的大小； (2) 将记录从一个位置移动至另一个位置。 前一个操作对大多数排序方法来说都是必要的，而 后一种操作可以通过改变记录的存储方式来予以避免。 ⚫概 述 排序的时间开销是算法好坏的最重要的标志。排序 的时间开销主要可以用算法执行中关键字的比较次数和 记录的移动次数来衡量
●概述 第十章内部排序 一三种存储方式: (1)待排序记录存放在地址连续的存储单元上。 (2)待排序记录存以静态链表存储,记录间的次序由指针指示。 (3)待排序记录存放在在连续存储单元中,另设指向各个记录地 址的指针向量 设待排记录的数据类型为 define MAX SIZE 20 typedef int KeyType typedef struct KeyType keyi InfoType otherInfoi RecType typedef struct RecType r [MAX SIZE 1] int Length I SoListi 第8页
第十章 内部排序 第8页 ⚫概 述 设待排记录的数据类型为 #define MAX_SIZE 20 typedef int KeyType typedef struct { KeyType key; InfoType otherInfo; } RecType; typedef struct { RecType r[MAX_SIZE + 1]; int Length; }SqList; 三种存储方式： （1）待排序记录存放在地址连续的存储单元上。 （2）待排序记录存以静态链表存储，记录间的次序由指针指示。 （3）待排序记录存放在在连续存储单元中，另设指向各个记录地 址的指针向量
●插入排序 第十章内部排序 插入排序的基本思想是:每次将一个待排序的记 录,按其关键字的大小插入到前面已经排好序的表或 文件中的适当位置,直到全部插入完为止 直接插入推序 一基本操作是将一个记录插入到已排好序的有序表中, 从而得到一个新的、记录数增1的有序表。 直接插入排序分趙进行,一般情况下,第i趟直接 插入排序的操作为:在含在i1个记录的有序子序列 r1i11中,首先查找r的插入位置,使得 reKey≤ ri. key<r+key(0≤ji 在m之后插入一个记录r,得到含有i个记录的有序 子序列r1.il 第9页
第十章 内部排序 第9页 插 入 排 序 插入排序的基本思想是：每次将一个待排序的记 录，按其关键字的大小插入到前面已经排好序的表或 文件中的适当位置，直到全部插入完为止。 ⚫ 直接插入排序 基本操作是将一个记录插入到已排好序的有序表中， 从而得到一个新的、记录数增1的有序表。 直接插入排序分趟进行，一般情况下，第 i 趟直接 插入排序的操作为：在含在 i-1 个记录的有序子序列 r[1..i-1] 中，首先查找r[i]的插入位置j，使得 r[j].key r[i].key< r[j+1].key (0 j<i) 在r[j]之后插入一个记录 r[i] ，得到含有 i 个记录的有序 子序列 r[1..i]
直接插入排序 第十章内部排序 示例1设待排关键字集合为 49,38,65,97,76,13,27,49} 「初始关键字(49)38659776132749 i=2(38)(3849)659776132749 i=3(65)(384965)9776132749 i=4(97)(38496597)76132749 i=5(76)(3849657697)132749 i6(13)(133849657697)2749 i=7(27)(13273849657697)49 i=8(49) (1327384949657697) 个监视哨图10.1直接插入排序示例 第10页
第十章 内部排序 第10页 示例1 设待排关键字集合为 {49，38，65，97，76，13，27，49} [初始关键字] (49) 38 65 97 76 13 27 49 i=2 (38) (38 49) 65 97 76 13 27 49 i=3 (65) (38 49 65) 97 76 13 27 49 i=4 (97) (38 49 65 97) 76 13 27 49 i=5 (76) (38 49 65 76 97) 13 27 49 i=6 (13) (13 38 49 65 76 97) 27 49 i=7 (27) (13 27 38 49 65 76 97) 49 i=8 (49) (13 27 38 49 49 65 76 97) ↑监视哨 图 10.1 直接插入排序示例 直接插入排序