数据结构与算法内部排序

《数据结构与算法内部排序》由会员分享，可在线阅读，更多相关《数据结构与算法内部排序（322页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法 （C+语言版）第9章 内 部 排 序排序的基本概念1. 相关术语和概念 （1）排序所谓排序就是整理文件中的记录次序，使其按关键码递增 （或递减）次序进行排列，其形式化定义如下： 输入：n个记录R1, R2, , Rn，其相应的关键码分别为K1, K2, , Kn。 输出：R1, R2, , Rn，使得K1K2Kn（或 K1K2Kn）。 即R1, R2, , Rn为R1, R2, , Rn的一种排列，该排列按照其 相应的关键码满足K1K2Kn的条件生成。排序的基本概念（2）排序算法的稳定性在待排序文件中，若存在多个关键码相同的记录，经过排 序后，这些具有相同关键码的记录之间的相对

2、次序保持不 变，则称该排序方法是稳定的；否则，称这种排序方法是 不稳定的。 （3）排序算法的两种基本操作 比较两个关键码的大小；将记录从一个位置移动至另 一个位置。排序的基本概念2. 数据类型为了方便讨论，待排记录的数据类型定义如以下程序所示 ：排序的基本概念3. 排序算法的效率 评价排序算法的效率主要有两点。在数据规模一定的条 件下，算法执行所消耗的平均时间。对于排序操作，时间 主要消耗在关键码之间的比较和数据元素的移动上，因此 可认为高效率的排序算法应该有尽可能少的比较次数和尽 可能少的数据元素移动次数。在数据规模一定的条件下 ，执行算法所需要的辅助存储空间。辅助存储空间是除了 存放待排序

3、数据元素占用的存储空间之外，执行算法所需 要的其他存储空间。理想的空间效率是，算法执行期间所 需要的辅助空间与待排序的数据量无关。插 入 排 序插入排序（insertion sort）的基本思想是，将待排序的记录 ，按其关键码的大小插入到已经排好序的有序子表中，直 到全部记录插入完成为止。通常需要一个辅助空间来存储 当前待插入的记录，在插入时，需要移动已排序记录，为 新插入的元素提供空间。下面主要介绍直接插入排序、折 半插入排序、2路插入排序、表插入排序及希尔排序。插 入 排 序直接插入排序 1. 算法思想 直接插入排序（straight insertion sort）是一种比较简单的排 序方

4、法，基本思想是，依次将记录序列中的每一个记录插 入到有序段中，使其长度不断扩大。算法实现思路是，先 将待排序记录序列中的第一个记录作为一个有序段，将记 录序列中的第二个记录插入到上述段中形成的由两个记录 组成的有序段，再将记录序列中的第三个记录插入其中， 形成由三个记录组成的有序段，其余类推，直到所 有记录都插入为止。一共需要经过n1趟就可将初始序列的 n个记录重新排列成按关键码值大小排列的有序序列。具体 实现见以下程序，其中，监视哨为L.r0，它的作用是：保 存每趟排序过程中的L.ri的副本，防止在记录后移时丢失 L.ri的内容；在第二个do_while循环中“监视”下标变量j是 否越界，一

5、旦越界（即j=0），则循环判定条件不成立，结 束循环。插 入 排 序2. 算法实现例9-1已知待排序的一组记录的关键码初始排列：52, 43, 68, 89, 77, 16, 24, 52*, 80, 31。按程序进行直接插入排序的过程如图 所示。可看出对于相同的两个关键码52和52*，直接插入排 序后并没有改变原来的相对次序，因此该排算法是稳定的 。插 入 排 序3. 算法效率直接插入排序算法比较简单，从空间效率来看，仅用到一 个记录的辅助空间作为监视哨。从时间效率来看，排序的 基本操作主要为比较两个关键码的大小和移动记录，可分 以下三种情况进行分析。 最好情况：当待排序列中记录按关键码非递

6、减有序排序 （“正序”）时，所需进行关键码间比较的次数达最小值n1 （即 ），即记录不需移动。插 入 排 序 最坏情况：当待排序列中记录按关键码非递增有序排序 （“逆序”）时，总的比较次数达最大值(n+2)(n1)/2（即 ），记录移动的次数也达最大值(n+4)(n1)/2（即 ）。 平均情况：若待排序记录是随机的，即待排序列中的记 录可能出现的各种排列概率相同，则取上述最小值和最大 值的平均值，作为直接插入排序时所需进行关键码间的比 较次数和移动记录的次数，约为n2/4。 综上所述，直接插入排序的时间复杂度为O(n2)。插 入 排 序折半插入排序 由于插入排序的基本思想是将待插入的新记录插入

7、到已排 序的有序表中，因此可在查找插入位置时采用折半查找的 方法。折半插入排序（binary insertion sort）的查找过程就 是利用“折半查找”来实现的，算法实现过程见以下程序。 时间复杂度为O(n2)。插 入 排 序插 入 排 序2路插入排序 2路插入排序是在折半插入排序的基础上进行改进的，其目 的是减少排序过程中移动记录的次数。算法实现的思路是 ，设一个和L.r同类型的数组d，首先将L.r1赋值给d1，并 将d1看成在排好序的序列中处于中间位置的记录，然后从 L.r中第2个记录起依次插入到d1之前或之后的有序序列中 。先将待插入记录的关键码和d1的关键码进行比较，若 L.ri.

8、key L.r2.key），则将其交换，最终达 到有序化。其处理过程为：将整个待排序的记录序列划 分成有序区和无序区，初始状态时，有序区为空，无序区 包括所有待排序的记录；对无序区从前向后依次将相邻 记录的关键码进行比较，若逆序，则将其交换，从而使得 关键码值小的记录向上“飘浮”（左移），关键码值大的记 录向下“坠落”（右移）。每经过一趟冒泡排序，都使无序区中关键码值最大的记录 进入有序区，对于由n个记录组成的记录序列，最多经过n 1趟冒泡排序，就可将这n个记录重新按关键码顺序排列。 可看出，若“在一趟排序过程中没有进行过交换记录的操作 ”，则可结束整个排序过程。例9-5如图所示为冒泡排序的一

9、个示例。冒泡排序的效率分析： 若初始序列为“正序”序列，则只需进行一趟排序，在排 序过程中进行n1次关键码的比较，且不移动记录； 若初 始序列为“逆序”序列，则需进行n1趟排序，需进行 次比较。因此，总的时间复杂度为O(n2) 。交 换 排 序快速排序 快速排序（quick sort）是Hoare于1962年提出的一种分区交 换排序。它采用了一种分而治之的策略，是对冒泡排序的 一种改进。其算法思想是，首先将待排序记录序列中的所 有记录作为当前待排序区域，选取第一个记录的关键码值 为基准（轴值），从待排序记录序列左、右两端开始向中 间靠拢，交替与轴值进行比较，若左侧记录的关键码值大 于轴值，则将

10、该记录移到基准记录的右侧，若右侧记录的 关键码值小于轴值，则将该记录移到基准记录的左侧，最 后让基准记录到达它的最终位置，此时，基准记录将待排 序记录分成了左右两个区域，位于基准记录左侧的记录都 小于或等于轴值，位于基准记录右侧的所有记录的关键码 都大于或等于轴值，这就是一趟快速排序。交 换 排 序然后分别对左右两个新的待排序区域，重复上述一趟快速 排序的过程，其结果是分别让左、右两个区域中的基准记 录都到达它们的最终位置，同时将待排序记录序列分成更 小的待排序区域，再次重复对每个区域进行一趟快速排序 ，直到每个区域只有一个记录为止，此时所有的记录都到 达了它的最终位置，即整个待排序记录按关键

11、值有序排列 ，至此排序结束。 快速排序算法的描述：交 换 排 序快速排序算法：交 换 排 序一趟快速排序算法：例9-6以关键码序列21, 25, 49, 25*, 16, 08为例，一趟快速排序的 过程如（a）所示，整个序列的快速排序过程如（b）所示 。从本例可看出，快速排序方法是一个不稳定的排序方法。 快速排序通常被认为是具有相同数量级 的排序方法中平均 性能最好的方法，但是，如果初始序列中关键码是有序或 基本有序的，则快速排序方法与冒泡排序的效率接近，比 较低。选 择 排 序选择排序（selection sort）的基本思想是，每一趟从待排序 的记录中选出关键码最小的记录，顺序放在已排好序

12、的子 序列后面，直到全部记录排序完毕。简单选择排序 简单选择排序的算法思想是每一趟在ni+1（i=1, 2, 3, , n 1）个记录中选取关键码最小的记录作为有序序列中的第i个 记录。 具体操作步骤如下。 将整个记录序列划分为有序区域和无序区域，有序区域 位于最左端，无序区域位于右端，初始状态有序区域为空 ，无序区域含有待排序的所有n个记录。选 择 排 序 设置一个整型变量index，用于记录在一趟的比较过程中 ，当前关键码值最小的记录位置。开始将它设定为当前无 序区域的第一个位置，即假设这个位置的关键码最小，然 后用它与无序区域中其他记录进行比较，若发现有比它的 关键码还小的记录，就将in

13、dex改为这个新的最小记录位置 ，随后再用L.rindex.key与后面的记录进行比较，并根据比 较结果，随时修改index的值。一趟结束后，index中保留的 就是本趟选择的关键码最小的记录位置。 将index位置的记录交换到无序区域的第一个位置，使得 有序区域扩展了一个记录，而无序区域减少了一个记录。 不断重复步骤、，直到无序区域剩下一个记录为止， 此时所有的记录已经按关键码从小到大的顺序排列就位。 实现过程如以下程序所示。选 择 排 序简单选择排序的比较次数与待排序序列的初始状态无关， 在第i趟排序过程中需要进行ni次比较，因此总的比较次数 为O(n2)，总的移动次数为n1，因此它的平均

14、时间复杂度为 O(n2)。同时，简单选择排序也是不稳定的排序算法。选 择 排 序选 择 排 序堆排序 1. 定义下面先给出相关定义。 （1）堆是指n个元素的序列k1, k2, , kn当且仅当满足以下 关系时，称为堆，其中满足关系的称为最小堆，满足关 系的称为最大堆。选 择 排 序例如，下列两个序列为堆87, 46, 75, 23, 14, 39, 52, 08, 20 ，14, 26, 37, 32, 58, 71，对应的完全二叉树如下图所示。（2）堆排序（heap sort）是指若在输出堆顶的最大（小） 值之后，使得剩余n1个元素的序列重又建成一个堆，则得 到n个元素中的次大（小）值。如此

15、反复执行，便能得到一 个有序序列，这个过程称为堆排序。堆排序只需要一个记 录大小的辅助空间，每个待排序的记录仅占有一个存储空 间。选 择 排 序2. 最大堆与它的主要操作 以下程序给出了最大堆的类定义。其中，n是私有成员，代 表目前堆中元素的个数；MaxSize是堆的最大容量；heap为 存储堆元素的数组，默认堆的大小为10个元素。最小堆的 类实现与最大堆的类似。选 择 排 序选 择 排 序最大堆的构造函数见以下程序。构造函数只是简单地开辟 一个足够大的数组使之能够存储当元素个数达到最大值时 的所有元素，它并不处理由new引发的NoMem异常。析构 函数应删除此数组。size函数尤其简单，仅返

16、回CurrentSize 的值。另一个简单的函数是Max，如果最大堆为空，它将引 发OutOfBounds异常；如果不为空，则返回最大树的根的值 。选 择 排 序最大堆的插入算法见以下程序。选 择 排 序在插入代码中，i从新创建的叶结点位置CurrentSize开始， 对从该位置到根的路径进行遍历。对于每个位置i，都要检 查是否到达根（i=1）或在i处插入新元素不会改变最大堆的 性质（x.keyheapi/2.key）。只要这两个条件中有一个满 足，就可在i处插入x；否则，将执行while循环体，把位于 i/2处的元素移到i处并把i处元素移到父结点（i/2）处。对于 一个具有n个元素的最大堆（即