递归与排序

1. 从循环到递归

我们之前学过的循环：

for i in range(x):
    # do something

是一种迭代（iteration）的方式。它通过重复执行同一段代码来完成任务。这很好，但有时候，我们需要一种反向的思维方式来解决问题，这就是递归（recursion）。用数学家的语言来说，递归就是：把一个问题分解成更小的同类问题来解决。

递归的核心思想是：问题解决自己。也就是说，一个函数在调用自己的过程中，逐渐逼近问题的解。比如，计算阶乘：

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

在这个例子中，factorial 函数调用了自己来计算 n 的阶乘。每次调用都会把 n 减小，直到达到基准情况（n == 0），此时返回 1。在计算 factorial(n) 时，我们不需要关心 factorial(n - 1) 具体是多少，我们只需要相信它会正确地返回结果，这就像是把工作交给了未来的自己来完成，而我们只需要专注于局部的逻辑。

2. 我怎么知道什么时候用递归？

递归适用于那些可以被分解成更小的同类问题的问题，我们可以把递归看作是完成游戏里的一个任务：想要和NPC对话，你需要先完成一个任务；想要完成那个任务，你又需要完成另一个更小的任务……直到你完成了最基本的任务，最终再一路回去完成所有的任务。

注意这里有两个限制：

• 递归必须有一个基准情况（base case），也就是当问题足够小的时候，我们可以直接解决它，而不需要再继续递归下去。否则，递归就会无限进行下去，导致程序崩溃。
• 递归的每一步都必须向基准情况靠近，也就是说，每次递归调用都应该使问题变得更小，不能中途回到之前的状态，否则同样会导致无限递归。

3. 想不出递归的解法怎么办？以汉诺塔(Hanoi)为例

我们以这次作业的汉诺塔问题为例，来看看如何从一个问题出发，逐步构建出递归的解法。

题目的描述是：汉诺塔有三根柱子，第一根柱子上有 n 个盘子，盘子从小到大叠在一起。目标是把所有盘子从第一根柱子移动到第三根柱子，但每次只能移动一个盘子，并且不能把大盘子放在小盘子上。

你可以在 这里 动手玩一玩！传说中，当你完成了 64 个盘子的汉诺塔，你就会获得世界的统治权。

现在让我们想象一下，如果我们需要移动 n 个盘子，在移动的过程中，至少有一刻，我们需要把最大的盘子（也就是最底下的盘子）移动到目标柱子上。为了做到这一点，我们必须先把上面的 n-1 个盘子移动到另一个柱子上（比如第二根柱子），这样我们才能把最大的盘子移动到第三根柱子上。

此时，我们如果把第二根柱子视为第一根柱子，那么我们就又回到了原来的问题：把 n-1 个盘子从第一根柱子移动到第三根柱子上。这个过程和我们最初的目标是一样的，只不过盘子的数量变少了。因此，我们就可以把这个过程看作是一个递归调用。

伪代码如下：

def hanoi(n, source, target, auxiliary):
    if n == 0:
        # 基准情况：没有盘子需要移动
        return
    # 先把 n-1 个盘子从 source 移动到 auxiliary
    hanoi(n - 1, source, auxiliary, target)
    # 再把第 n 个盘子从 source 移动到 target
    print(f"Move disk {n} from {source} to {target}")
    # 最后把 n-1 个盘子从 auxiliary 移动到 target
    hanoi(n - 1, auxiliary, target, source)

另外，当 n 增长时，递归调用的次数也会呈指数级增长，也就是 \(O(2^n)\) 的复杂度。这是因为每个盘子都需要被移动两次（一次从源柱子到辅助柱子，一次从辅助柱子到目标柱子），所以总的移动次数是 \(2^n - 1\)。从伪代码中我们也同样可以推出：\(S(n) = 2S(n-1) + 1\)，解出 \(S(n) = O(2^n)\)。如果你想完成 64 个盘子的汉诺塔，那么你需要进行 \(2^{64} - 1\) 次移动，这个数字大约是 \(1.84 \times 10^{19}\)，即使你每秒钟移动一个盘子，也需要数十亿年才能完成！

希望这个Hanoi的例子能够帮助你理解递归的思维方式：把一个大问题分解成更小的同类问题来解决，并且通过基准情况来终止递归。作业中另一道约瑟夫环问题也是类似的思路，你可以试着自己来构建递归的解法。

约瑟夫环问题提示，如果你实在不会（点击展开）

约瑟夫环问题的描述是：有 `n` 个人围成一圈，从第一个人开始报数，每报到第 `k` 个人就把他淘汰掉，然后从下一个人开始继续报数，直到最后只剩下一个人。你的任务是找出最后剩下的人的位置。
我们可以把这个问题看作是一个递归问题。首先，我们知道当 `n` 只有一个人时，最后剩下的人的位置就是 0（因为我们从 0 开始编号）。这是我们的基准情况。
当 `n` 大于 1 时，我们可以把第 `k` 个人淘汰掉，然后剩下的 `n-1` 个人继续报数。此时，我们需要把剩下的人的位置重新编号，使得被淘汰掉的人不再参与编号（这一步，像不像Hanoi问题中，我们把第二根柱子上 `n-1` 个盘子视为新的源柱子？）。具体来说，如果我们把被淘汰掉的人的位置记为 `m`，那么剩下的人的位置就会从 `m+1` 开始重新编号，直到 `m+k-1`（因为每次报数到第 `k` 个人就淘汰掉）。因此，我们可以把这个问题看作是一个递归调用：

def josephus(n, k):
    if n == 1:
        return 0
    else:
        # 淘汰掉第 k 个人，剩下 n-1 个人继续报数
        # TODO: 被淘汰掉的人的位置 m, 你需要根据 k 和 n 来计算出 m 的值
        m = ?  # 提示：你需要使用 % 取余运算来计算出 m 的值

        # TODO: 递归调用，找出剩下 n-1 个人中最后剩下的人的位置
        survivor = josephus(?, ?)
        # 把 survivor 的位置重新编号
        # 你需要把 survivor 的位置重新编号，使得它对应于原来 n 个人中的位置
        return (survivor + m + 1) % n  

4. 为什么要学排序？

把无序的东西变得有序，是计算机科学中一个非常重要的问题。在现实生活中，我们经常会无意识地进行排序，比如在打牌的时候，我们会把牌按照花色和数字排序；在买东西的时候，我们会按照价格或者评分来排序商品。在上一次作业中，我们学到了二分搜索，这个算法的前提是数据必须是有序（或局部有序）的。

你可以用这个网站来可视化各种排序算法的过程，看看它们是如何把一堆乱七八糟的数字变得井井有条的。

5. 朴素的排序算法

5.1 选择排序（Selection Sort）

选择排序的思想很简单：既然我们已经学会了如何找到一个列表中的最大/最小值，那么我们就可以利用这个能力来排序：

• 首先，我们找到列表中的最小值，并把它放到列表的开头。
• 然后，我们在剩下的元素中找到最小值，并把它放到第二个位置。
• 以此类推，直到整个列表都被排序。

伪代码如下：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 假设当前元素是最小的
        min_index = i
        for j in range(i + 1, n):
            # 如果找到更小的元素，更新最小值的索引
            if arr[j] < arr[min_index]:
                min_index = j
        # 交换当前元素和最小值所在位置的元素
        arr[i], arr[min_index] = arr[min_index], arr[i]

很明显，选择排序的时间复杂度是 \(O(n^2)\)，因为我们需要进行两层循环：外层循环遍历每个元素，内层循环寻找剩余元素中的最小值。不过即使我们的列表已经是有序的或者近似有序的，选择排序仍然需要进行 \(O(n^2)\) 的比较，因为它总是需要检查剩余元素来找到最小值。

5.2 插入排序（Insertion Sort）

插入排序其实更加接近我们平时打牌的时候的排序方式：我们保证自己手里的扑克牌始终是有序的，然后每次新发到一张牌，我们就把它插入到正确的位置上。具体来说：

• 从第二个元素开始，逐个遍历列表。
• 对于每个元素，我们将它与前面已经排序的部分进行比较，并将它插入到正确的位置上。

伪代码如下：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # 将 key 插入到已排序的部分中
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

插入排序的时间复杂度也是 \(O(n^2)\)，因为在最坏的情况下（当列表是逆序的），每个元素都需要与前面所有已经排序的元素进行比较和移动。不过，如果列表已经是有序的或者近似有序的，插入排序的时间复杂度可以降到 \(O(n)\)，因为每个元素只需要与前一个元素进行一次比较就可以确定它的位置。

5.3 冒泡排序（Bubble Sort）

冒泡排序的名字来源于它的工作原理：在每一轮比较中，较大的元素会像气泡一样逐渐浮到列表的末尾。具体来说：

• 从第一个元素开始，逐个比较相邻的两个元素。
• 如果前一个元素比后一个元素大，就交换它们的位置。
• 重复这个过程，直到没有元素需要交换为止。

伪代码如下：

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 标志位，判断这一轮是否有交换发生
        swapped = False
        for j in range(0, n - i - 1):
            # 如果前一个元素比后一个元素大，交换它们
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # 如果没有交换发生，说明列表已经有序，可以提前结束
        if not swapped:
            break

冒泡排序的时间复杂度是 \(O(n^2)\)，因为它需要进行多轮比较和交换。不过，如果列表已经是有序的或者近似有序的，冒泡排序的时间复杂度可以降到 \(O(n)\)，因为只需要一轮遍历就可以确定列表已经有序。

6. 归并排序

归并排序是我们第一次接触到的分治算法（divide and conquer）。它的核心思想是：把一个大问题分解成两个或多个更小的同类问题，直到这些问题足够简单以至于可以直接解决，然后再把这些小问题的解合并起来得到原来大问题的解（和递归的思想非常相似）。具体来说：

• 首先，我们把列表分成两半，分别对这两半进行排序（divide）。
• 然后，我们把已经排序的两半合并成一个有序的列表（conquer）。

举个例子，假设我们有一个列表 [8, 2, 4, 1, 3]：

• 首先，我们把列表分成两半：[8, 2] 和 [4, 1, 3]。
• 然后，我们对这两半分别进行排序：
• 对于 [8, 2]，我们把它分成 [8] 和 [2]，这两个列表已经是有序的了，所以我们直接合并成 [2, 8]。
• 对于 [4, 1, 3]，我们把它分成 [4] 和 [1, 3]，其中 [4] 已经是有序的了。对于 [1, 3]，我们把它分成 [1] 和 [3]，这两个列表已经是有序的了，所以我们直接合并成 [1, 3]。最后，我们把 [4] 和 [1, 3] 合并成 [1, 3, 4]。
• 最后，我们把 [2, 8] 和 [1, 3, 4] 合并成 [1, 2, 3, 4, 8]。

伪代码如下：

def merge(left, right):
    result = []
    i = j = 0
    # 合并两个有序列表
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # 如果 left 列表还有剩余元素，添加到结果中
    result.extend(left[i:])
    # 如果 right 列表还有剩余元素，添加到结果中
    result.extend(right[j:])
    return result

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    return merge(left_half, right_half)

归并排序的时间复杂度是 \(O(n \log n)\)，因为我们每次对半劈开，所以一共需要进行 \(\log n\) 轮分割，每轮分割需要 \(O(n)\) 的时间来合并两个有序列表。无论输入列表的初始状态如何，归并排序的时间复杂度都是 \(O(n \log n)\)，因为它总是需要进行相同数量的分割和合并操作。

Interesting fact: 其实 \(O(n \log n)\) 是排序算法的一个下界（lower bound），也就是说，任何比较排序算法（comparison-based sorting algorithm）都不可能在平均情况下比 \(O(n \log n)\) 更快。这是因为比较排序算法需要通过比较元素来确定它们的相对顺序，而在最坏的情况下，需要进行 \(O(n \log n)\) 次比较才能确定所有元素的正确位置。

7. 快速排序

既然我们已经学会了 \(O(n \log n)\) 而且是理论最优的归并排序，那么为什么还需要快速排序呢？在实际应用中，我们还需要考虑的一个因素是空间复杂度，与时间复杂度类似，空间复杂度丈量的是算法执行过程中所需的额外空间。归并排序在递归调用过程中需要额外的空间来存储合并后的结果，因此它的空间复杂度是 \(O(n)\)。这对于大规模的数据来说是一个不小的负担。

快速排序的核心思想是：选择一个元素作为“基准”（pivot），然后把列表分成两部分：一部分是所有比基准小的元素，另一部分是所有比基准大的元素。接着，我们对这两部分分别进行递归排序，最后把它们合并起来得到有序的列表。

伪代码如下：

def quick_sort(arr, low, high):
    if low < high:
        # 分区操作，返回基准元素的正确位置
        pi = partition(arr, low, high)
        # 递归排序基准元素左右两部分
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

def partition(arr, low, high):
    # 选择最后一个元素作为基准
    pivot = arr[high]
    i = low - 1  # 较小元素的索引
    for j in range(low, high):
        # 如果当前元素小于等于基准
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    # 将基准元素放到正确位置
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

由于原地交换元素，快速排序的空间复杂度低于归并排序。对于时间复杂度，快速排序在平均情况下是 \(O(n \log n)\)，但在最坏的情况下（当分为两部分时，每次都选择了最小或最大的元素作为基准，也就导致算法退化为选择排序），时间复杂度会变成 \(O(n^2)\)。不过，通过选择更好的基准（比如随机选择或者使用“三数取中”法），我们可以大大降低最坏情况发生的概率，使得快速排序在实际应用中表现得非常好。

Interesting fact: 当你知道了别人的快速排序的pivot选取策略后，你就可以针对性地构造输入来让它退化成 \(O(n^2)\) 的情况，这就是所谓的“快速排序的炸弹”（quick sort bomb）。比如，如果别人的快速排序总是选择最后一个元素作为基准，那么你可以输入一个已经有序或者逆序的列表，这样每次分区都会导致一个子列表为空，另一个子列表包含所有剩余元素，从而导致时间复杂度退化为 \(O(n^2)\)；又或者别人的快排策略是随机选择一个元素作为基准，且你可以控制随机数生成器的种子，那么你就可以构造一个输入，使得每次随机选择的基准都是最小或最大的元素，从而同样导致时间复杂度退化为 \(O(n^2)\)。

8. 一些不太可用的排序算法

• 猴子排序（Monkey Sort）：如果你有一只猴子在键盘上随机敲打，那么它敲出一本完整的莎士比亚作品集的可能性并不为零。因此我们可以直接随机打乱列表，检查它是否已经排序，如果没有就继续打乱，直到它有序为止。虽然这个算法看起来很有趣，但它的时间复杂度是无穷大，因为我们可能需要无限次的随机打乱才能得到一个有序的列表。

• 睡眠排序（Sleep Sort）：对于每个要排序的数字，创建一个线程，让它睡眠对应的时间（比如数字 5 就睡 5 秒），然后在醒来时输出这个数字。虽然这个算法看起来很有创意，但它的时间复杂度也是无穷大，因为它依赖于系统的调度和时间精度，可能会出现线程永远不会醒来的情况。

• 灭霸排序（Thanos Sort）：如果列表已经有序，那么直接返回；如果列表没有有序，那么随机删除列表中的一半元素，然后继续检查剩下的元素是否有序，直到列表变得有序为止。虽然这个算法看起来很有趣，但会让你的数据丢失！

• 川普排序（Trump Sort）：如果列表已经有序，那么直接返回；如果列表没有有序，那么直接声称列表已经有序了。虽然这个算法看起来很有趣，但它完全没有排序的功能！

• 斯大林排序（Stalin Sort）：从左到右遍历列表，如果当前元素比前一个元素小，那么就把它抹除掉，直到遍历完整个列表为止。既然解决不了问题，那就直接把问题解决掉！

• 奇迹排序（Miracle Sort）：如果列表已经有序，那么直接返回；如果列表没有有序，那么直接~~祈祷上帝~~祈祷宇宙中的高能粒子穿透你的计算机，随机地翻转寄存器和内存中的位，直到列表变得有序为止。

评论