排序、搜索与算法设计¶

一句话总结：本节梳理排序、二分搜索、贪心、动态规划 (Dynamic Programming, DP) 与回溯五大算法设计范式，用模板与陷阱把常见题型讲透。

排序与搜索是最基础的算法操作。本节涵盖排序算法、二分搜索模式、分治、贪心算法、动态规划以及回溯。

每种数据结构都为算法服务，每种算法都依赖数据结构。本节讲的是设计范式：解决问题的高层策略。一旦你能认出题目属于哪种范式，代码实现就自然而然写得出来。

排序算法¶

排序是计算机科学里被研究得最透的问题。掌握这些算法能建立起对递归、分治与复杂度分析的直觉。

算法	最好	平均	最坏	空间	稳定？
冒泡排序 (bubble sort)	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	是
插入排序 (insertion sort)	\(O(n)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	是
归并排序 (merge sort)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n)\)	是
快速排序 (quick sort)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n^2)\)	\(O(\log n)\)	否
堆排序 (heap sort)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(n \log n)\)	\(O(1)\)	否
计数排序 (counting sort)	\(O(n + k)\)	\(O(n + k)\)	\(O(n + k)\)	\(O(k)\)	是
基数排序 (radix sort)	\(O(d(n + k))\)	\(O(d(n + k))\)	\(O(d(n + k))\)	\(O(n + k)\)	是

稳定是指相等的元素在排序后仍保持它们原来的相对顺序。当你要按多个 key 依次排序时，这一点至关重要。
基于比较的排序有一个下界 \(\Omega(n \log n)\)。证明用到决策树 (见第 13 章)：任何比较排序都必须区分所有 \(n!\) 种排列，因此至少需要 \(\log_2(n!) = \Omega(n \log n)\) 次比较。计数排序和基数排序之所以能突破这个下界，是因为它们不做元素比较。

归并排序¶

把数组从中间一分为二，递归排序左右两半，然后合并已排好序的两半。永远是 \(O(n \log n)\)，额外空间 \(O(n)\).

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

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
    result.extend(left[i:])
    result.extend(right[j:])
    return result

陷阱：合并时把 <= 写成 < 就会破坏稳定性 (来自右半段的相等元素会跑到左半段之前).

快速排序¶

选一个枢轴 (pivot)，把元素分成"小于枢轴"与"大于枢轴"两组，递归排序每一组。平均 \(O(n \log n)\)，最坏 \(O(n^2)\) (当枢轴总是最小或最大元素时).

def quicksort(arr, lo=0, hi=None):
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return

    pivot_idx = partition(arr, lo, hi)
    quicksort(arr, lo, pivot_idx - 1)
    quicksort(arr, pivot_idx + 1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]  # Lomuto 方案: 取最后一个元素作枢轴
    i = lo
    for j in range(lo, hi):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

枢轴策略：最后一个元素 (简单，但对已排序输入很糟糕)、随机选 (期望 \(O(n \log n)\))、三数取中 (实际中的常见选择)。面试里永远优先选随机枢轴，免得被追问最坏情况。
陷阱：快排的 \(O(n^2)\) 最坏情况会在"已排序数组 + 首/末枢轴"的组合下出现。实际工程里，随机枢轴或三数取中就能消除这个问题。

计数排序¶

当数值都是已知范围 \([0, k)\) 内的整数时，统计出现次数再重建数组即可：时间 \(O(n + k)\)。它不基于比较，所以能突破 \(O(n \log n)\).

def counting_sort(arr, k):
    count = [0] * k
    for x in arr:
        count[x] += 1
    result = []
    for val in range(k):
        result.extend([val] * count[val])
    return result

什么时候用：范围 \(k\) 与 \(n\) 差不多大的时候。若 \(k = O(n)\)，整体就是 \(O(n)\)。若 \(k \gg n\) (比如在 \([0, 10^9]\) 范围内排 10 个数)，计数排序就是在浪费内存。

模式：二分搜索¶

二分搜索 (binary search) 在有序数组里以 \(O(\log n)\) 找到目标，靠的是反复把搜索区间对半砍。但二分搜索远不止"在有序数组里找一个数"这么简单。它的通用模式是：在单调条件上搜索.
模板 (能避开 off-by-one 错误的那一个):

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2  # 在其他语言中可避免溢出
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1  # 未找到

下界搜索 lower bound (第一个 \(\geq\) 目标的元素):

def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

陷阱: lo <= hi 和 lo < hi 的区别，以及 hi = mid 和 hi = mid - 1 的区别，决定了你找到的是精确匹配还是边界。用一个 2 元素数组画一画就能验证清楚。

简单：二分搜索¶

标准题，直接套上面的模板。

中等：在旋转有序数组中搜索¶

问题：一个有序数组在某个枢轴处被旋转过，找目标值。
模式：每一步，总有一半是有序的。判断哪一半有序，再看目标是否落在这一半里。

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid

        # 左半段有序
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # 右半段有序
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1

    return -1

陷阱: nums[lo] <= nums[mid] 里的 <= (而不是 <) 至关重要。当 lo == mid (只剩 2 个元素) 时，必须正确识别出哪一半是有序的。

困难：两个有序数组的中位数¶

问题：在 \(O(\log(m + n))\) 时间内找出两个有序数组的中位数。
模式：在较短那个数组的划分点上做二分搜索。划分要保证两数组左边所有元素都不大于右边所有元素。

def find_median(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1  # 确保 nums1 是较短的

    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
    half = (m + n + 1) // 2

    while lo <= hi:
        i = (lo + hi) // 2          # nums1 的划分点
        j = half - i                 # nums2 的划分点

        left1 = nums1[i - 1] if i > 0 else float('-inf')
        right1 = nums1[i] if i < m else float('inf')
        left2 = nums2[j - 1] if j > 0 else float('-inf')
        right2 = nums2[j] if j < n else float('inf')

        if left1 <= right2 and left2 <= right1:
            # 划分正确
            if (m + n) % 2 == 1:
                return max(left1, left2)
            return (max(left1, left2) + min(right1, right2)) / 2
        elif left1 > right2:
            hi = i - 1
        else:
            lo = i + 1

这是二分搜索里最难的题之一。关键洞察是：你不是在搜一个值，而是在搜一个满足某条件的划分点.

元模式：在答案上做二分搜索¶

很多题看着不像二分搜索，但可以在答案上做二分。如果答案是个数字，而你能写出一个单调的 is_feasible(x) (要么对所有 \(x \geq\) 最优值为 True，要么对所有 \(x \geq\) 最优值为 False)，那就在 \(x\) 上二分。
例: "在 \(d\) 天内送完所有包裹，船的最小运力是多少？" 在运力上二分。对每一个候选运力，贪心检查能不能在 \(d\) 天内送完。

def ship_within_days(weights, days):
    lo, hi = max(weights), sum(weights)

    while lo < hi:
        mid = (lo + hi) // 2
        # 运力为 mid 时, 能否在 <= days 天内送完?
        current_load, num_days = 0, 1
        for w in weights:
            if current_load + w > mid:
                num_days += 1
                current_load = 0
            current_load += w

        if num_days <= days:
            hi = mid
        else:
            lo = mid + 1

    return lo

模式：贪心算法¶

贪心 (greedy) 算法在每一步都做当前看起来最优的选择，期望这能导向全局最优解。贪心奏效的前提是问题满足贪心选择性质 (局部最优能推出全局最优) 和最优子结构 (optimal substructure，全局最优解由子问题的最优解构成).

中等：跳跃游戏¶

问题：给定数组，nums[i] 表示在位置 \(i\) 能跳的最大步数，判断能否到达最后一个下标。

def can_jump(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False  # 到不了这个位置
        max_reach = max(max_reach, i + jump)
    return True

贪心为何成立：我们只需知道能到达的最远位置。如果当前位置已经超过了最远可达，就卡住了；否则就更新最远可达。

中等：合并区间¶

问题：把重叠的区间合并起来。

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

模式：先按起点排序，再贪心合并。若当前区间与上一个已合并区间重叠，就扩展它；否则新起一段。
陷阱：写成 merged[-1][1] = end 而不是 merged[-1][1] = max(merged[-1][1], end)，就漏掉了"一个区间完全被另一个包含"的情况 (比如 [1, 10] 和 [2, 5]).

模式：动态规划¶

动态规划 (Dynamic Programming, DP) 把问题拆成互相重叠的子问题，每个子问题只解一次并把结果存起来。当问题同时具有最优子结构和重叠子问题 (overlapping subproblems) 时，DP 就适用。
两种写法:
- 自顶向下 (记忆化 memoisation)：先写自然的递归解，再把结果缓存到字典里。
- 自底向上 (制表 tabulation)：从最小子问题开始，逐层填出一张表。
怎么识别是不是 DP：问题要求最优 (min/max)、计数或存在性，且当前决策依赖前面的决策。如果你画出递归树能看到重复的子问题，那就是 DP.

简单：爬楼梯¶

问题：有 \(n\) 级台阶，一次能爬 1 或 2 级，有多少种不同走法？
这就是斐波那契：\(f(n) = f(n-1) + f(n-2)\).

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

时间 \(O(n)\)，空间 \(O(1)\)。整张记忆化表其实用不着，因为每个状态只依赖前两个。

中等：零钱兑换¶

问题：给一组硬币面额和目标金额，求凑出金额所需的最少硬币数。
状态: dp[amount] = 凑出 amount 所需的最少硬币数。
转移：对每种硬币，dp[amount] = min(dp[amount - coin] + 1).
基础情形: dp[0] = 0.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a and dp[a - coin] + 1 < dp[a]:
                dp[a] = dp[a - coin] + 1

    return dp[amount] if dp[amount] != float('inf') else -1

陷阱：初始值一定要是 float('inf') (不是 0 也不是 -1)。取最小值的比较，只有当"不可达状态"是正无穷时才成立。

中等：最长公共子序列¶

问题：给两个字符串，求它们的最长公共子序列 (Longest Common Subsequence, LCS) 的长度。
状态: dp[i][j] = text1[:i] 与 text2[:j] 的 LCS 长度。
转移：若 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

困难：0/1 背包¶

问题：给定若干物品的重量和价值，以及容量 \(W\)，求在不超容量的前提下能装到的最大价值。
状态: dp[i][w] = 用前 \(i\) 件物品，容量为 \(w\) 时的最大价值。
转移: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) (跳过或拿第 \(i\) 件).

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]  # 跳过第 i 件
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])

    return dp[n][capacity]

空间优化：由于每一行只依赖前一行，可以只用一维数组，并让 \(w\) 从右往左遍历:

def knapsack_optimised(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):  # 从右到左!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

陷阱：一维版本如果从左到右遍历，就允许同一件物品被拿多次 (无界背包)。从右到左才能保证每件物品最多用一次。

模式：回溯¶

回溯 (backtracking) 是带剪枝的穷举搜索。逐步构造解，一旦发现当前的部分解不可能扩展成合法完整解，就立刻放弃 (回溯).
模板:

def backtrack(candidates, path, result):
    if is_solution(path):
        result.append(path[:])  # 记得拷贝!
        return

    for candidate in get_candidates(path):
        if is_valid(candidate, path):
            path.append(candidate)     # 选
            backtrack(candidates, path, result)  # 探
            path.pop()                 # 撤 (回溯)

中等：子集¶

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

中等：组合总和¶

问题：找出所有和为目标值的不同组合 (元素可以重复使用).

def combination_sum(candidates, target):
    result = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # 剪枝: 已排序, 后面的候选都太大
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # 传 i 而不是 i+1: 允许复用
            path.pop()

    candidates.sort()  # 排序以便剪枝
    backtrack(0, [], target)
    return result

陷阱: backtrack(i, ...) 允许复用同一个元素，backtrack(i + 1, ...) 则跳到下一个 (不允许复用)。写错这一处是回溯里最常见的 bug.

困难：N 皇后¶

问题：在 \(n \times n\) 的棋盘上放 \(n\) 个皇后，使得两两不能互相攻击。

def solve_n_queens(n):
    result = []
    cols = set()
    pos_diag = set()  # / 对角线上 (row + col) 相同
    neg_diag = set()  # \ 对角线上 (row - col) 相同

    board = [['.' ] * n for _ in range(n)]

    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return

        for col in range(n):
            if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
                continue

            cols.add(col)
            pos_diag.add(row + col)
            neg_diag.add(row - col)
            board[row][col] = 'Q'

            backtrack(row + 1)

            cols.remove(col)
            pos_diag.remove(row + col)
            neg_diag.remove(row - col)
            board[row][col] = '.'

    backtrack(0)
    return result

核心洞察：对角线编码。对 / 对角线，row + col 是常数；对 \ 对角线，row - col 是常数。用集合跟踪列和两条对角线，合法性检查就是 \(O(1)\).

常见陷阱小结¶

陷阱	例子	修法
二分搜索里 `lo <= hi` vs `lo < hi`	边界上差 1	根据 `hi` 是闭还是开来选
一维背包从左到右	物品被重复选	0/1 背包一律从右到左
回溯里没有拷贝 path	`result.append(path)` — 所有条目指向同一个列表	用 `result.append(path[:])` 或 `path.copy()`
`backtrack(i)` vs `backtrack(i+1)`	允许复用 vs 不允许复用	对齐题面要求
排序回溯里漏掉 `break`	会去枚举太大的候选	排序 + 候选超出剩余量时 `break`
DP 初始化	`dp[0]` 错 → 后面全错	仔细定义基础情形
用了贪心却没证明	贪心不一定成立	验证贪心选择性质
多 key 排序用了不稳定排序	相等元素的相对顺序丢失	用稳定排序 (归并排序、Python 的 `sorted`)

课后练习 (NeetCode)¶

二分搜索¶

Binary Search — 标准模板
Search a 2D Matrix — 把矩阵拉平后二分
Koko Eating Bananas — 在答案上二分
Search in Rotated Sorted Array — 判定有序半段
Find Minimum in Rotated Sorted Array — 二分找拐点
Median of Two Sorted Arrays — 基于划分的二分

贪心¶

Jump Game — 追踪最远可达
Jump Game II — BFS 式的层级跟踪
Merge Intervals — 排序 + 合并
Insert Interval — 找重叠区
Non-overlapping Intervals — 按结束时间排序

动态规划¶

Climbing Stairs — 斐波那契式 DP
House Robber — 拿或跳 DP
House Robber II — 环形：跑两遍
Coin Change — 无界背包
Longest Common Subsequence — 双字符串 2D DP
Word Break — DP + 集合查找
Longest Increasing Subsequence — \(O(n^2)\) DP 或用二分 \(O(n \log n)\)
Edit Distance — 经典 2D DP
Partition Equal Subset Sum — 0/1 背包变体

回溯¶

Subsets — 枚举所有子集
Combination Sum — 允许复用的回溯
Permutations — 用 used 集合的回溯
Subsets II — 跳过重复
Word Search — 网格回溯
Palindrome Partitioning — 回溯 + 回文判断
N-Queens — 约束传播

📌 本节要点¶

排序下界：基于比较的排序时间下界为 \(\Omega(n \log n)\)，由决策树论证。
稳定性：归并排序稳定、快速排序不稳定；多 key 排序时必须选稳定排序。
计数/基数排序：不做比较，值域小时可达 \(O(n + k)\)，突破 \(n \log n\) 下界。
二分搜索本质：在单调条件上砍半，而非仅限有序数组找数。
答案上二分：若可行性函数单调，就把答案空间当作搜索区间。
贪心成立条件：需同时具备贪心选择性质与最优子结构，不成立时必须证伪。
DP 识别法：求最优/计数/存在，且子问题重叠出现，就用 DP.
背包一维优化: 0/1 背包必须从右到左更新，否则退化成无界背包。
回溯三步曲：选 → 探 → 撤；记得对结果 path[:] 拷贝，别共用引用。
对角线编码: N 皇后中用 row + col / row - col 常数性做 \(O(1)\) 合法性检查。