【学习】《算法图解》第四章学习笔记：分而治之与快速排序

前言

《算法图解》第四章引入了一种强大的算法设计策略——分而治之 (Divide and Conquer, D&C)。这种策略将复杂问题分解为更小、更易于管理的部分，然后递归地解决这些部分，最终合并结果。作为 D&C 策略的经典应用，本章详细介绍了快速排序 (Quicksort) 算法，它是一种非常高效且广泛使用的排序方法。本笔记将梳理 D&C 的核心思想以及快速排序的实现原理与性能分析。

一、分而治之 (Divide and Conquer, D&C)

分而治之是一种解决问题的范式，其核心思想是将一个难以直接解决的大问题，分割成一些规模较小的相同或相似的子问题，以便各个击破，分而治之。

（一）D&C 的工作原理

使用 D&C 解决问题通常包含以下两个步骤：

  1. **找出基线条件 (Base Case)**：确定问题可以被分解到的最小规模，这种规模的问题可以直接解决，无需进一步分解。这是递归的出口。
  2. **分解与递归 (Divide & Recur)**：描述如何将问题分解成更小的子问题，以及如何递归地解决这些子问题，直到达到基线条件。

书中通过几个例子阐述了 D&C 的思想：

  • 农场分地：将一块矩形土地均匀地分割成尽可能大的方块。基线条件是一条边的长度是另一条边的整数倍。递归步骤是不断从大矩形中切出以短边为边长的正方形，然后对剩余的小矩形重复此过程。
  • 数组求和：计算一个数组中所有元素的和。基线条件是数组为空（和为0）或只包含一个元素（和即为该元素）。递归步骤是将数组的第一个元素与剩余部分数组的和相加。

D&C 的策略非常适合用递归来实现。

（二）D&C 与递归

递归是实现 D&C 策略的自然方式。在 D&C 过程中：

  • 分解（Divide）：将原问题划分为若干子问题。
  • 解决（Conquer）：递归地求解各个子问题。若子问题规模足够小，则直接求解（达到基线条件）。
  • 合并（Combine）：将子问题的解合并成原问题的解（这一步在某些 D&C 算法中可能很简单，甚至没有）。

二、快速排序 (Quicksort)

快速排序是由 C.A.R. Hoare 在1960年提出的一种高效的排序算法，它完美地体现了分而治之的思想。

（一）算法原理

快速排序的步骤如下：

  1. **选择基准值 (Pivot)**：从数组中挑选一个元素作为基准值。这个选择可以有多种方式，例如选择第一个元素、最后一个元素、中间元素，或者随机选择一个元素。《算法图解》中的简单实现通常选择第一个元素。
  2. **分区 (Partitioning)**：重新排列数组，所有小于等于基准值的元素都移到基准值的左边，所有大于基准值的元素都移到基准值的右边。完成分区后，基准值就位于其在有序数组中的最终位置。
  3. **递归排序 (Recursive Sort)**：对基准值左边和右边的两个子数组分别递归地应用快速排序。

（二）基线条件

快速排序的基线条件是：当待排序的数组为空或只包含一个元素时，它自然就是有序的，无需再进行任何操作，直接返回即可。

（三）Python 代码示例

《算法图解》中提供了一个简洁的快速排序实现：

def quicksort(array):
    if len(array) < 2:
        return array  # 基线条件：为空或只包含一个元素的数组是"有序"的
    else:
        pivot = array[0]  # 递归条件：选择第一个元素作为基准值
        # 由所有小于等于基准值的元素组成的子数组 (不包括基准值自身，所以用 array[1:])
        less = [i for i in array[1:] if i <= pivot]
        # 由所有大于基准值的元素组成的子数组
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

# 测试
my_list = [10, 5, 2, 8, 7, 1, 9, 4, 3, 6]
print(f"Original array: {my_list}")
sorted_list = quicksort(my_list)
print(f"Sorted array: {sorted_list}")
# Output:
# Original array: [10, 5, 2, 8, 7, 1, 9, 4, 3, 6]
# Sorted array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

注意：这个实现非常简洁，易于理解 D&C 的思想，但在实际应用中，为了效率和处理重复元素，分区的实现通常更为复杂（例如使用双指针法进行原地分区）。书中的这个版本会创建新的列表，空间复杂度较高。

（四）图解快速排序过程（以 [3, 6, 2, 1, 5, 4] 为例，选择第一个为基准）

  1. quicksort([3, 6, 2, 1, 5, 4])

    • pivot = 3
    • less = [2, 1]
    • greater = [6, 5, 4]
    • 返回 quicksort([2, 1]) + [3] + quicksort([6, 5, 4])

  2. quicksort([2, 1]) (左子数组)

    • pivot = 2
    • less = [1]
    • greater = []
    • 返回 quicksort([1]) + [2] + quicksort([])

  3. quicksort([1]) (左孙子数组)

    • len < 2，返回 [1] (基线条件)

  4. quicksort([6, 5, 4]) (右子数组)

    • pivot = 6
    • less = [5, 4]
    • greater = []
    • 返回 quicksort([5, 4]) + [6] + quicksort([])

  5. quicksort([5, 4]) (左孙子数组)

    • pivot = 5
    • less = [4]
    • greater = []
    • 返回 quicksort([4]) + [5] + quicksort([])

  6. quicksort([4]) (左曾孙子数组)

    • len < 2，返回 [4] (基线条件)

  7. quicksort([]) (右曾孙子数组)

    • len < 2，返回 [] (基线条件)

    此时，步骤2返回 [1] + [2] + [] = [1, 2]。

  8. quicksort([5, 4]) (右孙子数组)

    • pivot = 5
    • less = [4]
    • greater = []
    • 返回 quicksort([4]) + [5] + quicksort([])

  9. 最终，步骤1返回 [1, 2] + [3] + [4, 5] = [1, 2, 3, 4, 5]。

三、再谈大 O 表示法与快速排序的性能

快速排序的性能分析是理解其为何”快速”的关键。

（一）平均情况 (Average Case)

在平均情况下，如果每次选择的基准值都能大致将数组分成两个大小相近的子数组（不一定是严格的一半对一半），那么递归树的深度大约是 O(log n)。在递归的每一层，分区操作都需要遍历当前层的所有元素，总共是 O(n) 的工作量。因此，快速排序的平均时间复杂度是 **O(n log n)**。

（二）最坏情况 (Worst Case)

最坏情况发生在每次选择的基准值都是当前数组中最小或最大的元素。例如，如果数组已经是有序的（或逆序的），并且总是选择第一个元素作为基准值：

  • 第一次分区后，一个子数组为空，另一个子数组包含 n-1 个元素。
  • 第二次分区后（对 n-1 个元素的数组），一个子数组为空，另一个包含 n-2 个元素。
  • 以此类推，递归树会变成一条链，深度为 O(n)。

在这种情况下，每一层递归仍然需要 O(n)（或接近 O(n)）的操作来分区，总的时间复杂度就变成了 O(n) * O(n) = **O(n²)**。这与选择排序等效率较低的算法相当。

（三）随机选择基准值的重要性

为了避免最坏情况的发生，一个有效的策略是随机选择基准值。随机化使得算法的性能不再依赖于输入数据的初始顺序，从而使得出现最坏情况的概率极低。在实际应用中，随机选择基准值的快速排序几乎总能达到 O(n log n) 的性能。

另一种常见的优化是”三数取中法”，即从数组的开头、中间、结尾选择三个元素，取其中位数作为基准值。

（四）与合并排序 (Merge Sort) 的比较

  • 合并排序的时间复杂度在所有情况下都是 O(n log n)，表现更稳定。
  • 快速排序的平均时间复杂度也是 O(n log n)，但在最坏情况下是 O(n²)。
  • 常数因子：尽管大 O 表示法忽略了常数因子，但在实际运行中，快速排序的常数因子通常比合并排序小。这意味着在数据量相同时，平均而言，快速排序的实际执行速度往往比合并排序更快。
  • 空间复杂度：
    • 合并排序通常需要 O(n) 的额外空间来辅助合并操作（非原地排序）。
    • 快速排序（如果采用原地分区策略，如Lomuto或Hoare分区方案）的空间复杂度主要是递归栈的深度。平均情况下是 O(log n)，最坏情况下是 O(n)。书中的简单实现由于每次都创建新列表，空间复杂度会更高。

因此，虽然合并排序在最坏情况下的性能更有保障，但快速排序因其平均情况下的优异表现和较低的常数因子，在实践中被广泛使用，并且是很多标准库排序函数的实现基础（通常会结合其他排序算法如插入排序进行优化）。

四、总结

分而治之 (D&C) 是一种强大的、递归式的问题解决策略，它鼓励我们将大问题分解成小问题来处理。快速排序是 D&C 思想的一个光辉典范，它通过巧妙地选择基准值和分区，实现了高效的排序。虽然快速排序在最坏情况下性能不佳，但通过随机化等策略可以有效规避，使其平均性能达到 O(n log n)，并在实践中通常表现优于其他 O(n log n) 排序算法。

五、参考资料