第2章 起步：排序

导读

排序是计算机科学中最基本也是研究最深入的问题之一。排序算法不仅是学习算法分析的起点，更是理解算法设计思想的重要载体。本章将从排序问题入手，引入算法分析的基本工具和方法。我们将详细学习两种经典的排序算法——插入排序和归并排序，并通过它们来理解算法正确性证明、时间复杂度分析等核心概念。

排序算法的选择和分析方法贯穿整个算法学习的始终。通过本章的学习，你将掌握如何描述和分析算法，理解不同算法在不同场景下的优劣，并建立起严格的算法分析思维。

核心概念详解

2.1 排序问题

排序问题的定义非常直观：给定一个包含n个元素的序列⟨a₁, a₂, ..., aₙ⟩，求该序列的一个重排⟨a'₁, a'₂, ..., a'ₙ⟩，使得a'₁ ≤ a'₂ ≤ ... ≤ a'ₙ。

虽然排序问题的定义简单，但它在实际应用中极为广泛：

• 数据库查询结果的有序显示
• 搜索引擎结果的相关性排序
• 数据压缩中的预处理步骤
• 算法设计中的子程序（如二分查找要求输入有序）

排序算法的分类方式多种多样：

• 内部排序 vs 外部排序：数据是否能全部放入内存
• 比较排序 vs 非比较排序：是否基于元素间的比较操作
• 稳定排序 vs 不稳定排序：相等元素的相对顺序是否保持不变
• 原地排序 vs 非原地排序：是否需要额外的存储空间

2.2 插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，其工作原理类似于我们整理扑克牌的方式：从第二张牌开始，将每张牌插入到前面已经排好序的牌中的正确位置。

算法描述：

INSERTION-SORT(A)
for j = 2 to A.length
    key = A[j]
    i = j - 1
    while i > 0 and A[i] > key
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key

工作原理：

从第二个元素开始，依次将当前元素与前面已排序的元素比较

将大于当前元素的已排序元素向后移动一位

找到正确位置后，将当前元素放入

重复上述过程，直到所有元素都排好序

正确性证明（循环不变式）：

插入排序的正确性可以通过循环不变式来证明。在for循环的每次迭代开始时，变量j指向当前待插入的元素。循环不变式为：

• 初始化：循环第一次迭代前，j = 2，子数组A[1..j-1] = A[1..1]只包含一个元素，自然是有序的。
• 保持：每次迭代中，我们将A[j]插入到已排序的子数组A[1..j-1]中的正确位置，因此A[1..j]变为有序的。
• 终止：当循环结束时，j = n+1，子数组A[1..n]包含整个数组，且是有序的。

时间复杂度分析：

• 最好情况：输入已经有序。每次只需要比较一次，不需要移动元素。总时间 = O(n)。
• 最坏情况：输入逆序。每次需要比较和移动前面所有元素。总时间 = O(n²)。
• 平均情况：对于随机排列，每个元素平均需要移动前面一半的元素。总时间 = O(n²)。

空间复杂度：O(1)，原地排序。

稳定性：稳定排序。当相等元素时，不会交换位置。

2.3 归并排序

归并排序（Merge Sort）是分治策略的经典应用。它将数组分成两半，分别排序，然后将两个有序的子数组合并成一个有序的数组。

算法描述：

MERGE-SORT(A, p, r)
if p < r
    q = ⌊(p + r) / 2⌋
    MERGE-SORT(A, p, q)
    MERGE-SORT(A, q + 1, r)
    MERGE(A, p, q, r)

MERGE(A, p, q, r)
n₁ = q - p + 1
n₂ = r - q
创建L[1..n₁+1]和R[1..n₂+1]
for i = 1 to n₁
    L[i] = A[p + i - 1]
for j = 1 to n₂
    R[j] = A[q + j]
L[n₁ + 1] = ∞
R[n₂ + 1] = ∞
i = 1, j = 1
for k = p to r
    if L[i] ≤ R[j]
        A[k] = L[i]
        i = i + 1
    else
        A[k] = R[j]
        j = j + 1

工作原理：

分解（Divide）：将n个元素的数组分成两个各含n/2个元素的子数组

解决（Conquer）：递归地对两个子数组进行归并排序

合并（Combine）：将两个已排序的子数组合并为一个有序数组

递归分析：

归并排序的时间复杂度可以通过递归树来分析。设T(n)为排序n个元素所需的时间：

• 分解：计算中点，O(1)
• 解决：递归排序两个n/2的子数组，2T(n/2)
• 合并：合并两个n/2的数组，O(n)

因此递归式为：T(n) = 2T(n/2) + O(n)

通过递归树分析：

• 第0层（根）：代价为cn
• 第1层：两个子问题，每个代价为c(n/2)，总代价为cn
• 第2层：四个子问题，每个代价为c(n/4)，总代价为cn
• ...
• 第log n层：n个子问题，每个代价为c，总代价为cn

总共有log n + 1层，每层代价为cn，因此T(n) = cn(log n + 1) = O(n log n)。

2.4 分治策略

分治策略（Divide and Conquer）是算法设计中最重要的策略之一。其基本思想是：

分解（Divide）：将原问题分解为若干个规模较小的子问题

解决（Conquer）：递归地求解子问题。如果子问题规模足够小，则直接求解

合并（Combine）：将子问题的解合并为原问题的解

分治策略的关键在于：

• 子问题之间应该是相互独立的
• 子问题应该是原问题的缩小版本
• 分解和合并的操作应该是高效的

归并排序是分治策略的完美体现：

• 分解：将数组一分为二（O(1)）
• 解决：递归排序（2T(n/2)）
• 合并：合并两个有序数组（O(n)）

2.5 递归式求解

递归式是分析递归算法时间复杂度的核心工具。求解递归式的常用方法有：

代入法（Substitution Method）：

猜测解的形式

用数学归纳法证明猜测正确

例如，对于T(n) = 2T(n/2) + cn，猜测T(n) = O(n log n)：

• 假设T(k) ≤ ck log k对所有k < n成立
• T(n) = 2T(n/2) + cn ≤ 2c(n/2)log(n/2) + cn = cn(log n - 1) + cn = cn log n
• 因此猜测成立

递归树法（Recursion Tree Method）：

将递归式的展开画成树形结构，计算每层的代价，然后求和。这种方法直观且易于理解。

主方法（Master Method）：

对于形如T(n) = aT(n/b) + f(n)的递归式，可以直接套用主定理：

• 情况1：若f(n) = O(n^(log_b(a)-ε))，则T(n) = Θ(n^(log_b a))
• 情况2：若f(n) = Θ(n^(log_b a))，则T(n) = Θ(n^(log_b a) · log n)
• 情况3：若f(n) = Ω(n^(log_b(a)+ε))且满足正则条件，则T(n) = Θ(f(n))

对于归并排序：a = 2, b = 2, f(n) = n, log_b(a) = 1，属于情况2，因此T(n) = Θ(n log n)。

2.6 插入排序与归并排序的对比

2.7 算法分析中的数学基础

算法分析需要一定的数学基础，主要包括：

求和公式：

• 等差数列求和：∑(i=1 to n) i = n(n+1)/2
• 等比数列求和：∑(i=0 to n) r^i = (r^(n+1) - 1)/(r - 1)
• 调和级数：∑(i=1 to n) 1/i ≈ ln n

整数性质：

• 取整函数：⌊x⌋（向下取整）和⌈x⌉（向上取整）
• 模运算：a mod n = a - n⌊a/n⌋

概率基础：

• 期望的线性性：E[∑Xᵢ] = ∑E[Xᵢ]
• 条件概率和贝叶斯定理

重要知识点

知识点1：循环不变式的证明方法

循环不变式是证明迭代算法正确性的有力工具。证明分为三步：

初始化：证明在循环第一次迭代前不变式成立

保持：证明如果某次迭代前不变式成立，则下次迭代前仍然成立

终止：证明循环终止时，不变式给出了有用的性质

知识点2：原地操作与非原地操作

原地操作（In-place）是指算法只需要常数级别的额外空间。原地排序算法（如插入排序）在空间受限的环境中更有优势。非原地操作（如归并排序的合并步骤）需要额外的存储空间，但可能带来更好的时间性能。

知识点3：算法的渐进分析

渐进分析关注的是当输入规模趋向无穷大时，算法性能的变化趋势。它忽略了常数因子和低阶项，专注于增长率。这种分析方法的优势在于：

• 与机器和编程语言无关
• 关注大规模输入的行为
• 简化了算法比较

知识点4：递归深度的理解

递归深度是指递归调用栈的最大深度。对于归并排序，递归深度为log n。递归深度直接影响空间复杂度（调用栈空间）和可能导致的栈溢出问题。在实际实现中，对于深度递归需要特别注意栈空间的使用。

知识点5：混合排序策略

实际系统中的排序算法往往采用混合策略：

• Timsort（Python、Java使用）：结合归并排序和插入排序
• Introsort（C++ std::sort）：结合快速排序、堆排序和插入排序
• 基本思想：根据数据特征和规模自动选择最合适的算法

常见误区

误区1：插入排序总是比归并排序慢

在以下情况下，插入排序可能比归并排序更快：

• 输入规模很小（n < 50左右）
• 输入基本有序
• 对空间有严格限制

这也是为什么许多混合排序算法在小规模子问题上使用插入排序的原因。

误区2：O(n²)的算法没有实用价值

插入排序虽然是O(n²)，但在以下场景中仍然非常有用：

• 作为混合排序算法的基础组件
• 处理小规模数据
• 数据几乎有序的情况
• 实现在线排序（数据逐个到达）

误区3：归并排序的空间复杂度可以优化到O(1)

标准的归并排序需要O(n)的额外空间用于合并操作。虽然存在原地归并的算法，但它们的时间复杂度会增加到O(n log² n)或实现极其复杂。空间和时间之间的权衡在归并排序中体现得很明显。

误区4：递归一定比迭代慢

递归和迭代的性能差异主要来自于函数调用的开销。在现代编译器优化下，尾递归可以被优化为迭代。更重要的是，递归带来的代码清晰性和正确性往往比微小的性能差异更有价值。

误区5：主方法可以解决所有递归式

主方法只适用于形如T(n) = aT(n/b) + f(n)的递归式，且f(n)需要满足特定条件。对于更复杂的递归式（如T(n) = T(n-1) + T(n-2) + O(1)），需要使用其他方法（如特征方程法）。

实践应用

应用1：数据库中的排序

数据库系统在处理查询结果排序时，需要考虑：

• 外部排序：当数据量超过内存时，使用外部归并排序
• 索引排序：利用B树等索引结构避免显式排序
• 多键排序：按多个字段进行排序
• 排序优化：利用数据的部分有序性减少排序时间

应用2：文件系统排序

操作系统中的文件列表排序需要考虑：

• 自然排序：按人类直觉排序（file2在file10之前）
• 多属性排序：按名称、大小、日期等多维度排序
• 增量排序：新文件加入时高效更新排序
• 大规模目录：包含数百万文件的目录的高效排序

应用3：搜索引擎结果排序

搜索引擎的结果排序涉及复杂的算法：

• 相关性评分：TF-IDF、BM25等算法计算文档与查询的相关度
• PageRank：基于链接分析评估网页权威性
• freshness：考虑内容的时效性
• 个性化排序：根据用户历史和偏好调整排序

应用4：排序在算法设计中的角色

排序经常作为其他算法的预处理步骤：

• 二分查找：要求输入有序
• 去重：先排序，再扫描去除相邻重复元素
• 中位数查找：可以利用排序或更高效的算法
• 区间查询：排序后可以使用二分查找加速

应用5：排序算法的并行化

在多核和分布式环境中，排序算法的并行化是重要的研究方向：

• 并行归并排序：将数据分成多个块，并行排序后归并
• 并行快速排序：并行分区，递归处理子问题
• 样本排序：通过采样实现负载均衡的并行排序
• 分布式排序：在MapReduce等框架中实现大规模数据排序

2.8 排序算法的更多细节

插入排序的详细分析：

插入排序的比较次数和移动次数：

• 最好情况（已排序）：n-1次比较，0次移动
• 最坏情况（逆序）：n(n-1)/2次比较和移动
• 平均情况：n(n-1)/4次比较和移动
• 逆序对数 = 移动次数

逆序对：

如果i < j但A[i] > A[j]，则(A[i], A[j])是一个逆序对。插入排序的移动次数等于逆序对数。

归并排序的合并步骤优化：

• 哨兵值（∞）可以避免检查数组边界
• 但实际实现中通常使用显式边界检查，避免特殊值
• 合并的空间复杂度为O(n)，可以通过原地归并优化到O(1)，但时间增加到O(n log n)

2.9 排序算法的稳定性深入分析

为什么稳定性重要：

• 多键排序：先按次要键排序，再按主要键排序
• 如果排序算法稳定，次要键的相对顺序在主要键排序后保持
• 例如：先按名字排序，再按年龄排序（稳定排序保证同年龄的人名字仍然有序）

各排序算法的稳定性：

• 稳定：插入排序、归并排序、计数排序
• 不稳定：选择排序、堆排序、快速排序（标准版本）

2.10 混合排序策略的深入分析

Timsort（Python和Java的默认排序）：

• 结合归并排序和插入排序
• 检测数据中的自然有序段（run）
• 对短run使用插入排序扩展
• 使用归并排序框架合并run
• 最优情况O(n)（已排序数据），最坏O(n log n)

Introsort（C++ std::sort）：

• 开始时使用快速排序
• 递归深度超过2·⌊log₂ n⌋时切换到堆排序
• 子数组小于16个元素时切换到插入排序
• 保证O(n log n)最坏情况

本章小结

本章通过排序问题深入引入了算法分析的基本方法和工具。我们学习了：

插入排序：一种简单直观的排序算法，时间复杂度为O(n²)，但在小规模或基本有序的数据上表现良好。通过循环不变式证明了其正确性。移动次数等于逆序对数。

归并排序：分治策略的经典应用，时间复杂度始终为O(n log n)，但需要O(n)额外空间。

分治策略：将问题分解为子问题、递归求解、合并结果的重要算法设计策略。

递归式求解：代入法、递归树法和主方法是分析递归算法时间复杂度的三种主要工具。

算法分析基础：渐进分析、最好/最坏/平均情况分析、空间复杂度分析等方法。

稳定性：稳定排序在多键排序中的重要性。

混合排序：Timsort和Introsort等实际系统中的混合排序策略。

排序算法不仅是实用的工具，更是理解算法设计思想的窗口。通过深入学习排序算法，我们为后续章节中更复杂的算法打下了坚实的基础。

关键术语

思考题

修改插入排序使其按降序排列，分析修改后的时间复杂度是否改变。

在归并排序中，如果已知两个子数组的元素范围不重叠（一个子数组的所有元素都小于另一个），能否优化合并过程？

设计一个算法，在O(n log n)时间内判断一个数组中是否存在重复元素。

分析当输入已经按序排列时，插入排序和归并排序各自的实际运行时间。