排序

排序是计算机程序设计中的一种重要操作，在很多领域下都有广泛的应用。如各种升学考试的录取工作，日常生活的各类竞赛活动等都离不开排序。排序的一个主要目的是便于查找，从前面查找章节中可知，有序的顺序表可以采用查找效率更高的折半查找，又如创建树表（二叉排序树、B- 树等）的过程本身就是一个排序的过程。

人们设计了大量的排序算法以满足不同的需求。例如，著名计算机科学家 D.E.Knuth 在他的巨著《计算机程序艺术》第三卷《排序和查找》中，就给出了 25 种排序方法，并且指出，这只不过是现有排序方法的一小部分。本章仅讨论几种典型的、常用的排序方法。在学习中应该要注意的是，除了掌握算法本身以外，更重要的是了解该算法所依据的原则，以利于学习和创造新的算法。

基本概念

排序

排序（Sorting）是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。

假设含 $n$ 个记录的序列为

$$\{R_1,R_2,\dots ,R_n\}$$

其对应的关键字序列为

$$\{K_1,K_2,\dots ,K_n\}$$

需确定 $1,2,\dots ,n$ 的一种排列 $p_1,p_2,\dots ,p_n$，使其对应的关键字满足如下的非递减（或非递增）关系

$$K_{p1}⩽K_{p2}⩽\dots ⩽K_{pn}$$

即使得记录序列成为一个按关键字有序的序列

$$\{R_{p1},R_{p2},\dots ,R_{pn}\}$$

这样一种操作称为排序。

稳定性

当排序记录中的关键字 $K_i(i=1,2,\dots ,n)$ 都不相同时，则任何一个记录的无序序列经排序后得到的结果唯一；反之，当待排序的序列中存在两个或两个以上关键字相等的记录时，则排序所得的结果不唯一。假设 $K_i=K_j(1⩽i⩽n,1⩽j⩽n,i\ne j)$，且在排序前的序列中 $R_i$ 领先于 $R_j$（即 $i<j$）。若在排序后的序列中 $R_i$ 仍领先于 $R_j$，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中 $R_j$ 领先于 $R_i$，则称所用的排序方法是不稳定的。注意，排序算法的稳定性是针对所有记录而言的。也就是说，在所有待排序记录中，只要有一组关键字的实例不满足稳定性要求，则该算法就是不稳定的。虽然稳定的排序方法和不稳定的排序方法排序结果不同，但不能说不稳定的排序方法就不好，各有各的适用场景。

内部排序和外部排序

由于待排序记录的数量不同，使得排序过程中数据所占用的存储设备会有所不同。根据在排序过程中记录所占用的存储设备，可将排序方法分为两大类：一类是内部排序，指的是待排序记录全部存放在计算机内存中进行排序的过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中需要访问外存的排序过程。

内部排序方法的分类

内部排序的方法很多，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境（如记录的初始排列状态等）下使用。

内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，可以将排序记录区分为两个区域：有序序列和无序序列区。

使有序区中记录的数目增加一个或几个的操作称为一趟排序。

根据逐步扩大记录有序序列长度的原则不同，可以将内部排序分为以下几类。

1. 插入类：将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。主要包括直接插入排序、折半插入排序和希尔排序；
2. 交换类：通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。主要包括冒泡排序和快速排序；
3. 选择类：从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，一次方法增加记录的有序子序列的长度。只要包括简单选择排序、树形选择排序和堆排序；
4. 归并类：通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。2-路归并排序是最为常见的归并排序方法；
5. 分配类：是唯一一类不需要进行关键字之间比较的排序方法，排序时主要利用分配和收集两种基本操作来完成。基数排序是主要的分配类排序方法。

待排序记录的存储方式

1. 顺序表：记录之间的次序关系由其存储位置决定，实现排序需要移动记录；
2. 链表：记录之间的次序关系由指针指示，实现排序不需要移动记录，仅需修改指针即可。这种排序方式称为链表排序；
3. 待排序记录本身存储在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”，在排序结束之后在按照地址向量中的值调整记录的存储位置。这种排序方式称为地址排序。

在之后的讨论中，除基数排序外，待排序记录均按第一种方式存储，且为了讨论方便，假设记录的关键字均为整数。

待排序记录的数据类型定义为

export class Item {
  constructor(public key: number, public other?: Record<string, any>) {}
}

排序算法效率的评价指标

执行时间

对于排序操作，时间主要消耗在关键字之间的比较和记录的移动上（这里只考虑以顺序表方式存储待排序记录），排序算法的时间复杂度由这两个指标决定。因此可以认为，高效的排序算法的比较次数和移动次数都应该尽可能的少。

辅助空间

空间复杂度由排序算法所需的辅助空间决定。辅助空间是除了存放待排序记录占用的空间之外，执行算法所需要的其它存储空间。理想的空间复杂度是 $O(1)$，即算法执行期间所需辅助空间与待排序的数据量无关。

在后面讨论各种排序算法时，将给出有关算法的关键字比较次数和记录移动次数。有的排序算法执行时间不仅依赖于待排序的记录个数，还取决于待排序序列的初始状态。因此，对这样的算法，将给出其最好、最坏和平均情况下的 3 种时间性能评价。

在讨论排序算法的平均执行时间时，均假定待排序记录初始状态是随机分布的，即出现各种排列情况的概率是相等的。同时还假定各种排序的结果均是按关键字非递减排序。