排序概念

稳定性

排序算法的 稳定性 是指：在排序过程中，如果两个元素的键值相等，排序后它们的 相对顺序保持不变，那么这个排序算法就是 稳定的排序算法。

比如排序前的数组是这样：[... A ... B ...]，并且 A 和 B 的值相同。

如果排序后的数组是这样：[... B A ...]，那么排序算法就是不稳定的，反之排序算法就是 稳定的。

补充

可以通过以下方式对排序算法的 稳定性 进行记忆：

速度比较快的算法（时间复杂度 O(nlogn) ）一般都不稳定，除了 归并排序，因为它需要占额外的空间。

速度比较慢的算法（时间复杂度 O(n2) ）一般都稳定，除了 选择排序。

除此之外，桶排序 和 基数排序 都是 稳定的。

元素移动次数

排序算法中的 元素移动次数，指的是在排序过程中对 数组元素进行位置变换的次数。

下表列出了各排序算法的 元素移动次数：

趟特征

在排序算法中，一趟（pass） 通常指 完成一次从头到尾（或部分范围）对数组进行处理的过程，这一过程中可能会比较、移动、插入或交换若干元素。

换句话说，一趟就是排序算法中最小的完整“循环工作单元”，通常对应于外层循环的一次执行。

内部排序

排序元素的内存中直接使用

外部排序

排序元素需要在内外存之间交换使用

冒泡排序

冒泡排序（Bubble Sort）是一种 简单的排序算法，通过反复遍历数组，比较相邻元素并交换位置，将较大的（或较小的）元素逐步“冒泡”到数组的一端。过程如下：

从数组开头开始，比较相邻的两个元素，如果顺序不对（例如前者大于后者，假设升序排序），则交换它们。
遍历一遍后，最大（或最小）的元素会被“冒泡”到数组末尾（或开头）。
对剩余的未排序部分重复上述步骤，每次遍历的范围减少一个元素，直到数组完全排序。

在升序排序中，较大的元素像气泡一样逐渐“浮”到数组的末端（或较小的元素“沉”到开头），每次遍历都将一个元素推到正确的位置，形似气泡在水中上升的过程，因此得名 “冒泡排序”。

比如，对于数组 5, 1, 4, 2, 8的前两次冒泡过程如下：

插入排序

插入排序可以分为直接插入排序和折半插入排序，其不同点在于 寻找插入位置时 使用的是 从后向前顺序查找 还是 折半查找。

插入排序适合 大部分元素有序 的场景，因为这种情况下进行插入比较的次数较少，排序算法执行更加高效。

直接插入

插入排序（Insertion Sort）将数组分为 未排序部分 和 已排序部分，每次选取未排序部分的第一个元素作为插入元素，在已排序序列中 从后向前 扫描，找到相应位置并插入。

对于数组 4, 3, 2, 10, 12, 1, 5, 6 执行插入排序的过程：

直接插入排序适合链式存储和顺序存储的线性表

折半插入

同直接插入排序一致，只有在寻找插入位置时会减少一点对比次数。

因为折半查找相当于随机查找，因此该算法仅适用于顺序存储的线性表

希尔排序(缩小增量排序)

希尔排序（Shell Sort）是一种 基于插入排序 的改进算法，通过分组和逐步减小步长来提高效率。

基本思想

把待排序表相隔几个元素分割成几个子表
对每个子表分别进行直接插入排序
整个表中的元素已基本有序时，在对全体记录进行一次直接插入排序

提示

每 n（步长）个元素组成的子表是要保持有序的（后头还有数字）

希尔排序是不稳定的

因为局部的两个子表进行插入排序，可能会导致全局中两个相同的元素交换了位置

希尔排序的过程如下所示：

确定初始步长（增量）：
- 选择一个初始步长（gap），通常可以 取数组长度的一半（例如 gap = n/2）。
分组插入排序：
- 将数组按步长 gap 分成若干 (gap组) 组，每组内的元素相距 gap 个位置。
- 对每组进行插入排序。例如，若 gap=4，比较和排序索引为 0,4,8... 的元素，1,5,9... 的元素，依此类推。
减小步长：
- 将步长缩小（通常除以 2 或按增量序列递减），例如 gap = gap/2。
- 重复步骤 2，对新的分组进行插入排序。
重复直到步长为 1：
- 当步长减小到 1 时，相当于对整个数组进行一次标准插入排序。此时数组已接近有序，插入排序的效率较高。
排序完成：
- 步长为 1 的插入排序完成后，数组完全有序。

注意

虽然希尔最初提出时建议初始 gap（增量序列）为 n/2 并逐步折半，但在实践中 gap 的选取是灵活的，并不强制要求必须为数组长度的一半。

仅适用于顺序存储的线性表

选择排序

归并排序

归并排序（Merge Sort）是一个典型的 分而治之 策略的应用。它将一个大问题分解成若干小问题分别解决，然后将这些小问题的解合并为大问题的解。归并排序的主要思想是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

基本思想

分解：分解待排序的数据数组为两个长度相等（或几乎相等）的子数组。
递归：递归地排序两个子数组。
合并：合并（归并）两个已排序的子数组以产生排序好的数据数组。

代码

每趟归并的时间复杂度： $O (n)$ ，相比较归并的时间而言分割子表的时间复杂度太小忽略不计。

归并的趟数： $O (lo g_{2} n)$ 由上图可知，总分割次数等于二叉树的树高。

故：归并的总时间复杂度为： $O (n lo g n)$

 
void mergesort(int l, int r)  {
 
 
 
	if(l >= r) return; // 归类到 只有一个数时 本层归类不执行， 改为执行前面未完成的合并操作
 
	int mid = (l + r) >> 1; // >> 优先级低于 +、- 一般写题 还是加上括号
 
	mergesort(l, mid);
 
	mergesort(mid + 1, r);
 
	
 
	int i = l, j = mid + 1, k = 0;
 
 
 
	while (i <= mid && j <= r) {
 
	
 
		if(p[i] < p[j]) m[k ++] = p[i ++];
 
		else  m[k ++] = p[j ++];
 
	
 
	}
 
 
 
	while (i <= mid) m[k ++] = p[i ++];
 
	while (j <= r) m[k ++] = p[j ++];
 
	// 合并为有序数列
 
	k = 0;
 
	for (int i = l; i <= r; i ++)
 
	p[i] = m[k ++];
 
	// 对应原数组下标将 排好序的 数列 拷贝到 原数组中
 
}
 
// 归并：顾名思义 先归类 再合并
 
// 算法上 必须采用一个 n （输入数量） 长度的辅助空间，将排好序的临时数组拷贝到 原数组中去

快速排序

快速排序（Quick Sort）的核心思想和归并排序一样，也是 分而治之，其步骤如下：

选择一个基准元素（Pivot）：从数组中选择一个元素作为基准。
分区（Partition）：重新排列数组，使得所有小于基准的元素都在其左侧，所有大于基准的元素都在其右侧。在这个分区结束之后，该基准就处于数组的最终排序位置。
递归地排序子序列：递归地对基准左侧和右侧的子数组进行快速排序。

代码

填坑法（常考算法思想）

 
void quicksort(int l, int r) // 填坑法 快排 比较基础{
 
	
 
	if(l >= r) return;
 
	int i = l, j = r, base = p[l];
 
	do{ // 核心 逻辑
 
	
 
		while(p[j] > base && i < j) j --;
 
			p[i] = p[j];
 
		while(p[i] < base && i < j) i ++;
 
			p[j] = p[i];
 
		
 
	}while(i < j);
 
		
 
	p[i] = base; // 补上 最后的 坑, 也就是 中间值
 
	
 
	quicksort(l, i - 1); // 这个和任意取 的 i j 不一样，会有 i = j 的可能
 
	quicksort(i + 1, r);
 
	// 这里也是 如果 i 或者 j 不动，则有可能会出现 quicksort(l, r) = quicksort(i, r); or quicksort(l, r) = quicksort(l, j)
 
	
 
	// 况且 你的 p[i] 已经 到了最终位置了 因此 不参与 后续的 排序！！！
 
}

Hoare 基础版（统考不用）

 
void quicksort(int l, int r)  
 
 
 
{
 
 
 
	int base = p[l + r >> 1], i = l, j = r;
 
	
 
	do{
 
	
 
		while (p[i] < base) i ++;
 
		while (p[j] > base) j --;
 
		if (i <= j) swap(p[i], p[j]), i ++, j --; // 防止 p[i] = p[j] = base 死循环
 
	/* 要么
 
	
 
	int i = l - 1, r = r + 1, base = q[r + l >> 1];
 
	
 
	while(i < j) {
 
	
 
		do i ++; while (q[i] < base);
 
		do j --; while (q[j] > base);
 
 
 
		if(i < j) swap(q[i], q[j]);
 
	}
 
	quicksort(l, j);
 
	quicksort(j + 1, r);
 
	*/
 
	// 总之 一定要让 指针i 和 指针j 错开,防止死循环
 
	}
 
	while (i <= j);
 
	
 
	if(l < j) quicksort(l, j);
 
	if(i < r) quicksort(i, r);
 
 
 
}

空间复杂度

快排的空间复杂度为什么是 O(logn)

快速排序是原地排序算法，唯一的空间开销来自递归调用栈，理想情况下：

每次把数组分成近似相等的两半；

整个递归树的深度是 $l o g_{2} n$ ；

所以最多同时存在 $l o g_{2} n$ 层的递归调用；

每一层调用中局部变量空间是常数（ $O (1)$ ）；

因此，空间复杂度是： $O (l o g n$ ) （递归深度） × $O (1)$ （每层开销） = $O (l o g n)$

堆排序

堆

在二叉树一节中我们提到，二叉树的存储方式包含 链接存储 和 顺序存储 两种。关键

堆就是采用 顺序存储 的方式，在这种方式中，我们使用一个数组来模拟一颗二叉树，二叉树中的结点操作被转化为数组元素操作。

满足以下性质的树被称为堆（Heap）：

结构性质：堆总是一颗 完全二叉树，即除了最后一层之外的其他每一层都被元素填满，且最后一层的元素都尽可能地靠左排列。
有序性质：树中的每个结点相对于子结点都保证有序关系，要么父结点的值都 大于等于 子结点的值，要么都 小于等于 子结点的值，按照这种有序关系堆可以分为两种类型：
- 大根堆（Max Heap）：堆中的任意结点，其值都 ≥ 其子结点的值。这意味着 根结点是最大值。
- 小根堆（Min Heap）：堆中的任意结点，其值都 ≤ 其子结点的值。这意味着 根结点是最小值。

基于这些性质，堆常常被用于实现 优先队列。对于大根堆，我们总是可以在 O(1) 的时间内得到最大的元素（即根结点），而对于小根堆，我们总是可以在 O(1) 的时间内得到最小的元素。

实现

重点关注 down 函数中建立初始化堆的递归性，交换完一次后还得关注后续交换到下面的结点的动向

插入

非常简单，只需要从子结点的父亲开始比较，如果需要交换则继续与祖父比较，重复此操作

结束条件满足堆的定义

代码

down 函数

 
void down(int u) {
 
 
 
int t = u;
 
 
 
if(2 * u <= cnt && h[2 * u] <= h[u]) t = 2 * u; 
 
if(2 * u + 1 <= cnt && h[2 * u + 1] <= h[t]) t = 2 * u + 1; 
 
if(t != u)  swap(h[u], h[t]), down(t);
 
 
 
}

输出主函数

 
int main() {
 
	int h[N], n, cnt;
 
	
 
	cin >> n;
 
	cnt = n;
 
 
 
	for(int i = 1; i <= n; i ++)  cin >> h[i];
 
 
 
	for(int i = n / 2; i; i --)  down(i);
 
 
 
	for(int i = 1; i <= n; i ++) {
 
		cout << h[1] << ' ';
 
		h[1] = h[cnt];
 
		cnt --;
 
		down(1);
 
	}
 
}

基数排序

基数排序（Radix Sort）的核心思想是将整数分解为单独的数字，然后进行多轮排序，最终使数据有序。

基数排序分为 低位优先（LSD，Least Significant Digit first）和 高位优先（MSD，Most Significant Digit first）两种方案。这里重点掌握 LSD 的方案，MSD 的方式了解即可。

升序 or 降序

从 $0 \sim 9$ 收集得到的是升序序列，若是 $9 \sim 0$ 则是降序序列. （前提）用的是 LSD

低位优先

实现

先按照最低位进行 桶排序（或计数排序）。
然后按照次低位进行 桶排序，但保持上一轮的相对顺序（稳定排序）。
依次进行，直到最高位排序完成。

结果

首先对最低位排序，然后对次低位排序，最后对最高位排序。通过三轮排序，可以保证结果序列是有序的。

高位优先

MSD（高位优先）基数排序的核心思想是从最高位开始，对数据进行递归分类栈模拟

直到所有数字或字符串都排好序。

先发制人会导致后续排序混乱，只能分而治之

如上图所示，MSD 首先根据最高位对数据进行分组，然后再根据次高位对数据进行分组，以此类推，递归直到每组中只有一个元素。

重要结论

MSD 基数排序适用于 字符串或变长数据，因为它先处理最高位，可以提前分组。适合 字典序排序，如 IP 地址、文件名、长整型数值等。

小结

桶排序

桶排序（bucket sort）核心思想是将数据映射到不同的桶中，然后对每个桶内部排序，最后合并所有桶中的数据。

桶排序的步骤如下：

选择合适桶数，并将数据放入桶中
桶内数据排序
合并所有桶

举个例子，对 12, 9, 24, 4, 19, 21, 14, 6, 2, 16 进行桶排序的过程如下：

时空复杂度

表格对比

不稳定算法口诀：选艾希、堆攻速

外部排序

中优先级

其实外部排序不是高频考点，但是遭不住 23 年考了一道置换选择排序的大题，所以还是得掌握下 外部排序的过程。这也给了我们一个启示：涉及到算法过程的知识点，都要留一个心眼，也许之前不考察但是今年就冷不丁地来一道大题。

核心公式

T_{外部排序} = T_{内部排序} + T_{外存读 / 写} + T_{内部归并}

后续所做的所有算法优化都是基于以上时间公式进行的

简单排序流程

当待排序的数据量大到无法一次性全部装入内存时，就必须采用 外部排序。外部排序的基本思路是：先将整个数据集划分成若干能够装入内存的子块，对每个子块在内存中完成内部排序；随后再把这些已排序的子块逐步合并，最终得到整体有序的结果。这样既克服了内存容量的限制，又能高效地对海量数据完成排序。

外部排序的整体过程通常可以划分为两个关键阶段：

生成初始归并段

先采用 置换选择排序 对原始的无序文件进行扫描。置换选择能够在一次扫描中尽可能长地生成有序子文件，这些子文件即称为 初始归并段。每个归并段都是内部有序的，且长度尽量大，以减少后续合并的轮数。
多路归并

将所有 初始归并段 以多路归并的方式逐步合并。每一次归并都会把若干归并段合并成一个更长的有序段，重复此过程直至只剩下一个完整的有序文件，从而得到最终的排序结果。

通过上述两步，外部排序能够在 磁盘与内存之间 高效地完成大规模数据的排序。

生成初始归并段

置换选择排序（Replacement Selection Sort）是 外部排序 的一个步骤，用于生成 初始归并段，其核心功能是在 内存缓冲区 有限的情况下，尽可能地生成较长的 初始归并段。

置换选择排序 通过维护一个 工作区 来实现这一目标，工作区是一个 小根堆。

其算法步骤如下：

初始化：
- 将待排序文件中的前 M 个记录读入 工作区，建立一个 最小堆（M 为 工作区 的大小）。
生成归并段：
- 判断是否有 初始归并段
  - 如果不存在任何 初始归并段 的话，创建一个 初始归并段，并添加 工作区 中的最小元素加入其中。
  - 否则将 工作区 中的元素与上一个 初始归并段 的最大值 MAXV 进行比较。
    - 如果 工作区 中的所有元素都 ≤ MAXV 的话，创建一个新的 初始归并段，并添加 工作区 中的最小元素加入其中。
    - 否则找到第一个 > MAXV 的元素，将其添加到上一个 初始归并段 的末尾。
- 从输入文件中读取下一个值加入 工作区。

置换选择排序 核心思想 的如下：

判断工作区：如果工作区中所有记录的键值都小于当前输出文件（即已生成的有序段）中最后一个记录的键值，则需要新建一个输出文件，并将这些记录写入该文件，开启新的有序段。
继续合并：如果工作区中存在键值不小于当前输出文件末尾记录的记录，则 不断将这些记录追加到已有的输出文件中。这样可以确保输出文件始终保持递增有序，从而形成一个完整的有序序列。

通过上述两步的交替执行，置换选择排序能够在外部存储环境下有效地生成有序文件，适用于大型数据集的排序任务。

例子

举一个实际的例子，假设一个输入文件 FI 的内容为 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100。

我们可以通过 置换选择排序 生成 3 个 初始归并段，分别为 {37, 51, 63, 92, 94, 99} ，{14, 15, 23, 31, 48, 56, 60, 90, 166} ，{8, 17, 43, 100} 。

算法执行的过程如下表所示：

最佳归并树

先前利用置换选择排序，得到了 长度不等的初始归并段 。

由于不同的归并顺序也会导致磁盘的 I/O 次数不同，因此需要确定一个算法可以保证每次归并顺序最优。

根据哈夫曼树的特性可以很好的构造出一个 结点权值累加最小的 $m$ 叉树。

问 · 题

因为不是每次得到的初始归并段都满足 m 叉排序的需求，为了能让归并树的结构更接近哈夫曼树的最优形态—— 权值较小的段（包括虚段）被安排在最底层，避免过早参与归并

所以引入若干长度为 0 的 ”虚段“

计算”虚段个数“公式

设度为 0 的结点（初始归并段）有 $n_{0}$ 个，度为 $k$ 的结点有 $n_{k}$ 个，归并树的总结点数有 $n$

则有

n n = n_{k} + n_{0} (总结点数 = 度为 k 的结点数 + 度为 0 的结点数) = k n_{k} + 1 (总结点数 = 所有结点的度数之和 + 1)

对于严格的 $k$ 叉树，有

\frac{n - 1}{k - 1} = n_{k} (商) (n - 1) % (k - 1) = u

为了弥补这 $u$ 个多余的初始归并段，我们可以再添加 $(k - 1 - u)$ 个为 ”0“ 的虚段

即 $n_{k}^{'} = \frac{n - 1 + k - 1 - u}{k - 1} = n_{k} + 1$

多路归并

多路归并 的目标是将多个已经排序的 初始归并段（子文件）合并成一个更大的有序文件。

其核心思想是从若干 归并段 中每次选取一个最小的元素加入 工作区（小根堆），然后从 工作区 中选取最小的元素添加到 输出文件 中，通过这种方式可以保证每次添加到 输出文件 中的值是当前的最小值。

例子

继续用上文中通过 置换选择算法 生成的三个 初始归并段 {37, 51, 63, 92, 94, 99} ，{14, 15, 23, 31, 48, 56, 60, 90, 166} ，{8, 17, 43, 100} 作为例子。对于这三个 初始归并段，多路归并 的过程如下（假设采用三路归并的话）：

胜者树

在进行 k 路归并（如外排序）时，我们需要从多个有序子序列中 快速找出当前最小元素，然后将其输出并替换为该序列的下一个元素。

最简单的做法就是每次遍历序列头部元素，找到最小值。该方法的时间复杂度为 O(k) ，效率比较低，尤其是当 k 比较大 时。

树形结构优化（胜者树/败者树）优化的目的就是优化这个过程：

用一棵完全二叉树维护每一轮比较的结果，使得我们可以在 $O (l o g k)$ 时间内完成最小值查找与更新。

在 胜者树 中，每个 内部结点 记录的是该轮比较的胜者（较小的元素），而 叶子节点 表示每个输入归并段的当前值。因此，整棵树的 根节点 就表示 全局最小值。

当某个归并段输出了最小值并更新为下一个元素时，需要 从该叶子节点向上，逐层与兄弟节点重新比较，构建新的胜者路径，最终将新的最小值更新到根节点。

败者树

败者树 可以理解为 败者记录的升降赛模型：类比体育比赛中每场比赛将败者淘汰出局但保留记录，胜者则继续晋级下一轮，最终全局胜者脱颖而出，但 不会被记录在树中，而是单独保留，以便快速访问。

在 败者树 中，每个 内部结点 记录的是该轮比较的败者（较大的元素），而 叶子节点 同样表示每个输入归并段的当前值。最终的全局胜者（最小值） 不保存在树中，而是单独保存在一个外部变量中。

当某个归并段输出了最小值并更新为下一个元素时，需要 从该叶子节点出发，沿着路径向上与路径上的败者重新比较，并在每一层更新败者信息。

补充

胜者树更加直观，败者树的优势在哪？

在用 胜者树 的时候，每个新元素上升时，首先先和兄弟结点比较，然后再更新父结点（访存 2 次）。

在使用 败者树 的时候，每个新元素上升时，只需要获得父节点并比较即可（访存 1 次）。

所以总的来说，减少了访存的时间，进而 提高了程序运行的效率。

Quartz 5

Explorer

8. 排序

排序概念

稳定性

元素移动次数

趟特征

内部排序

外部排序

冒泡排序

插入排序

直接插入

折半插入

希尔排序(缩小增量排序)

基本思想

选择排序

归并排序

基本思想

代码

快速排序

代码

空间复杂度

堆排序

堆

实现

插入

代码

基数排序

低位优先

实现

结果

高位优先

小结

桶排序

时空复杂度

表格对比

外部排序

核心公式

简单排序流程

生成初始归并段

例子

最佳归并树

问 · 题

计算”虚段个数“公式

多路归并

例子

胜者树

败者树

Graph View

Table of Contents