考研笔记-计算机之数据结构:排序(基础概览)

——如阅读体验不佳，可转为横屏阅读；如微信无法横屏，可尝试文末方法。

排序：将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。

若关键字是主关键字（唯一），则排序后得到的有序序列唯一；若关键字是次关键字（不唯一），则排序后得到的有序序列不唯一。

假设关键字K_i= K_j，（i ≠j）且排序前的序列中记录R_i领先于R_j（即i < j），若在排序后的有序序列中R_i仍领先于R_j，则称所用的排序方法是稳定的；若在排序后的有序序列中可能使R_j领先于R_i，则称所用的排序方法是不稳定的。

一般，排序过程中的“比较”是在“两个相邻记录的关键字”间进行的排序方法是稳定的。

稳定性是方法本身决定的，对不稳定的排序方法而言，不管其描述形式如何，总能举出一个说明不稳定的实例来。反之，对稳定的排序方法而言，总能找到一种不引起不稳定的描述形式。

在某描述形式下，只要有一个实例不稳定，则说明该描述形式下的排序方法不稳定，只有所有实例均稳定，才说明该描述形式下的排序方法稳定。

稳定排序方法：存在一种描述形式，使得排序方法在该描述形式下稳定。

不稳定排序方法：对任意一种描述形式，排序方法在该描述形式下均不稳定。

排序过程中需要进行两种基本操作：比较关键字；移动记录。比较关键字的操作是必须的，而移动记录的操作可通过改变记录的存储方式来避免。

待排序记录可以有三种存储方式：

（1）记录使用顺序表存储，排序过程中需移动记录；

（2）记录使用静态链表存储，排序过程中不需移动记录，仅需修改指针（游标）；

（3）记录本身使用顺序表存储，记录的地址使用另一顺序表存储，排序过程中不需移动记录而是移动记录对应的地址，排序结束后，根据地址的顺序移动记录。

按排序过程中依据的原则，内部排序方法可分为插入排序、交换排序、选择排序、归并排序和基数排序五类：

（1）插入排序：如何在有序表中寻找插入点，基本操作为比较和插入。

（2）交换排序：两元素的大小顺序不对则交换，基本操作为比较和交换。

（3）选择排序：根据什么规则选择最小/大元素，基本操作为比较和选择。

（4）归并排序：将多个有序表合并为一个有序表，基本操作为比较和合并。

（5）基数排序：多关键字排序，基本操作为分配和收集。

按排序过程中所需的工作量，内部排序方法可分为简单的排序方法、先进的排序方法和基数排序方法三类：

（1）简单的排序方法：时间复杂度为。

（2）先进的排序方法：时间复杂度为。

（3）基数排序方法：时间复杂度为（d为每个记录的关键字的个数，r为每个关键字的取值范围）。

描述排序过程的判定树

描述排序过程的判定树：判定树为二叉树，判定树的每个非终端结点表示两个关键字间的一次比较，其左、右子树分别表示这次比较所得的两种结果；判定树的每个终端结点（叶子结点）表示所有关键字的一种可能的最终排序结果。判定树上进行的每一次比较都是必要的，因此该判定树足以描述通过“比较”进行的排序过程。

每个初始序列经排序达到有序所需进行的“比较”次数，恰为从树根到和该有序序列相应的叶子结点的路径长度，故任意序列经排序达到有序所需进行的最少“比较”次数为描述其排序过程的判定树的深度。由于含n个关键字的序列可能出现的初始状态有n!个，则描述n个关键字排序过程的判定树必须有n!个叶子结点。由高度为h的二叉树的叶子结点的个数不超过，可得含有n个结点的二叉树的最小深度为，进而描述n个关键字排序的判定树（含n!个叶子结点）上必定存在一条长度为的路径。由此可得，任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少为。

由Stirling公式可得，借助“比较”进行排序的算法在最坏情况下能达到的最好的时间复杂度为。快速排序的平均时间为knlog₂n，其中k为某个常数，经验证明，在所有同数量级的此类（先进）排序方法中，快速排序的常数因子k最小，因此，就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。

内部排序：待排序记录全部存放在计算机随机存储器中进行的排序过程。

外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

文章合集：