排序、搜索与算法设计

排序、搜索与算法设计

排序和搜索是最基础的算法操作。本文件涵盖排序算法、二分查找模式、分治、贪心算法、动态规划和回溯。

• 每种数据结构都支撑着算法，每个算法又依赖数据结构。本文件讲的是设计范式（design paradigm）：解决问题的高层策略。一旦你认出该用哪个范式，实现就水到渠成了。

排序算法

• 排序是计算机科学里被研究得最多的问题。理解这些算法能帮你建立对递归、分治和复杂度分析的直觉。

• **稳定（stable）**指相等的元素保持它们原有的相对顺序。这在按多个键排序时很重要。

• 基于比较的排序的下界是 \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 个数），计数排序会浪费内存。

模式：二分查找

• 二分查找通过反复把搜索空间砍半，在 O(\log n) 内于有序数组中找到目标。但二分查找远不只是「在有序数组里找一个数」。通用模式是：在一个单调条件上搜索。

• 模板（能避免差一错误的那个）：

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 target 的元素）：

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 最优都为真，或对所有 x \geq 最优都为假），那就在 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）算法在每一步都做局部最优的选择，希望这能导向全局最优。当问题具有贪心选择性质（greedy choice property）（局部最优导向全局最优）和最优子结构（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]）。

模式：动态规划

• 动态规划（DP）通过把问题拆成重叠的子问题、每个子问题只求解一次并存下结果来解题。当问题具有最优子结构和重叠子问题时有效。

• 两种做法：

  • 自顶向下（记忆化，top-down / memoisation）：先写自然的递归解法，再用字典缓存结果。
  • 自底向上（制表法，bottom-up / 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）。求最小值的比较只有在不可达状态是无穷大时才正确。

中等：最长公共子序列

• 题目：给定两个字符串，求它们最长公共子序列的长度。

• 状态：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，在不超过 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]
​

• 陷阱：一维版本里从左往右迭代会让物品 i 被多次使用（无界背包）。从右往左才能保证每个物品最多用一次。

模式：回溯

• 回溯是带剪枝的穷举搜索。逐步构造解，一旦部分解不可能导向一个合法的完整解就放弃（回溯）。

• 模板：

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)。

常见陷阱汇总

编程练习（使用 CoLab 或 notebook）

以下题目可在 NeetCode 的题目列表中练习。

二分查找

• Binary Search（二分查找）—— 标准模板
• Search a 2D Matrix（搜索二维矩阵）—— 把矩阵摊平后二分
• Koko Eating Bananas（爱吃香蕉的 Koko）—— 对答案二分
• Search in Rotated Sorted Array（搜索旋转排序数组）—— 识别有序的一半
• Find Minimum in Rotated Sorted Array（寻找旋转排序数组中的最小值）—— 二分找拐点
• Median of Two Sorted Arrays（两个有序数组的中位数）—— 基于划分的二分

贪心

• Jump Game（跳跃游戏）—— 追踪最远可达
• Jump Game II（跳跃游戏 II）—— BFS 式的层级追踪
• Merge Intervals（合并区间）—— 排序 + 合并
• Insert Interval（插入区间）—— 找重叠区域
• Non-overlapping Intervals（无重叠区间）—— 按结束时间排序

动态规划

• Climbing Stairs（爬楼梯）—— 斐波那契 DP
• House Robber（打家劫舍）—— 取或跳的 DP
• House Robber II（打家劫舍 II）—— 环形：跑两次
• Coin Change（零钱兑换）—— 无界背包
• Longest Common Subsequence（最长公共子序列）—— 两个字符串上的二维 DP
• Word Break（单词拆分）—— 带集合查找的 DP
• Longest Increasing Subsequence（最长递增子序列）—— O(n^2) DP 或用二分做到 O(n \log n)
• Edit Distance（编辑距离）—— 经典二维 DP
• Partition Equal Subset Sum（分割等和子集）—— 0/1 背包变体

回溯

• Subsets（子集）—— 枚举所有子集
• Combination Sum（组合总和）—— 允许复用的回溯
• Permutations（全排列）—— 带已用集合的回溯
• Subsets II（子集 II）—— 跳过重复
• Word Search（单词搜索）—— 网格回溯
• Palindrome Partitioning（分割回文串）—— 回溯 + 回文判断
• N-Queens（N 皇后）—— 约束传播