经典算法专栏 #02：排序与搜索

本文覆盖十大排序算法对比、快排/归并排序原理与实现、二分查找的 4 种变体，以及动态规划入门（0-1 背包/最长公共子序列）。

目录

排序算法总览

稳定性：值相同的元素排序后保持原有相对顺序。稳定排序在多关键字排序中非常重要——例如先按姓名排序，再按年龄稳定排序，能保证同年龄者仍按姓名有序。

O(n²) 排序

冒泡排序

每次比较相邻元素，将较大元素"冒泡"到末尾。

public void bubbleSort(int[] a, int n) {
    for (int i = 0; i < n; ++i) {
        boolean flag = false;
        for (int j = 0; j < n - i - 1; ++j) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
                flag = true;
            }
        }
        if (!flag) break; // 没有交换，说明已有序，提前退出
    }
}

插入排序

将未排序区间的元素逐一插入到已排序区间的正确位置（移动而非交换）。

public void insertionSort(int[] a, int n) {
    for (int i = 1; i < n; ++i) {
        int value = a[i];
        int j = i - 1;
        for (; j >= 0; --j) {
            if (a[j] > value) a[j + 1] = a[j]; // 移动，不是交换
            else break;
        }
        a[j + 1] = value;
    }
}

为什么插入排序优于冒泡排序？

两者时间复杂度相同，但插入排序每次移动只需 1 次赋值，冒泡排序每次交换需 3 次赋值（tmp 中转），常数系数更小，实际性能更好。

小数组（n < 16）时，插入排序甚至优于快排——Java Arrays.sort 对小数组就使用插入排序。

O(nlogn) 排序

归并排序

分治思想：将数组从中间分成两半，分别排序，再合并。

void mergeSort(int[] a, int p, int r) {
    if (p >= r) return;
    int q = (p + r) / 2;
    mergeSort(a, p, q);
    mergeSort(a, q + 1, r);
    merge(a, p, q, r);
}

void merge(int[] a, int p, int q, int r) {
    int[] tmp = new int[r - p + 1];
    int i = p, j = q + 1, k = 0;
    while (i <= q && j <= r) {
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++]; // <= 保证稳定性
    }
    while (i <= q) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int x = 0; x < tmp.length; x++) a[p + x] = tmp[x];
}

• 时间复杂度：任何情况都是 O(nlogn)
• 空间复杂度：O(n)（需要额外数组，非原地）
• 稳定性：稳定（<= 保证相等元素不交换）

快速排序

分治思想：选择 pivot，将数组分为小于 pivot 和大于 pivot 两部分，递归排序。

void quickSort(int[] a, int p, int r) {
    if (p >= r) return;
    int q = partition(a, p, r);
    quickSort(a, p, q - 1);
    quickSort(a, q + 1, r);
}

int partition(int[] a, int p, int r) {
    int pivot = a[r];   // 选末尾为 pivot
    int i = p;          // i 指向已处理区间末尾
    for (int j = p; j < r; ++j) {
        if (a[j] < pivot) {
            int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++;
        }
    }
    int tmp = a[i]; a[i] = a[r]; a[r] = tmp; // pivot 放到正确位置
    return i;
}

• 平均时间复杂度：O(nlogn)
• 最坏情况（已有序数组选末尾为 pivot）：O(n²)
• 空间复杂度：O(logn)（递归调用栈）
• 原地排序，不稳定

优化 pivot 选择：随机选择 pivot，或三数取中法（取首、中、尾三数的中位数），避免退化到 O(n²)。

归并 vs 快排

为什么快排实际更快？ 快排原地排序，访问连续内存，缓存命中率高；归并需要额外数组，内存分配有开销。

线性排序

线性排序不是基于比较的排序，绕过了比较排序 O(nlogn) 的下界，但有使用前提。

计数排序

适用于数据范围 k 不大的整数排序。

public void countingSort(int[] a, int n) {
    int max = Arrays.stream(a).max().getAsInt();
    int[] c = new int[max + 1]; // 计数数组
    for (int x : a) c[x]++;
    for (int i = 1; i <= max; i++) c[i] += c[i - 1]; // 前缀和：计算每个值的最终位置
    int[] r = new int[n];
    for (int i = n - 1; i >= 0; i--) r[--c[a[i]]] = a[i]; // 从后往前保证稳定
    System.arraycopy(r, 0, a, 0, n);
}

• 时间复杂度：O(n+k)
• 适用场景：数据范围小（如年龄排序、成绩排序）

桶排序

将数据分到有限数量的桶中，每个桶内单独排序，再合并。

• 时间复杂度：O(n)（数据均匀分布时）
• 适用场景：数据均匀分布，如外部排序（数据不能全部载入内存时）

基数排序

按位数从低位到高位依次排序，每次用稳定排序（计数排序）。

• 时间复杂度：O(dn)，d 为位数
• 适用场景：手机号排序、日期排序（位数固定、范围大但位数少）

二分查找

二分查找针对有序数组，每次与区间中间元素对比，将查找范围缩小为一半。时间复杂度 O(logn)。

为什么只适合数组？ 二分依赖随机访问（O(1) 下标访问），链表不支持，只能顺序遍历。

基础实现

public int bsearch(int[] a, int n, int value) {
    int low = 0, high = n - 1;
    while (low <= high) {                    // 注意：<=，不是 <
        int mid = low + ((high - low) >> 1); // 防止 (low+high) 溢出，用位运算
        if (a[mid] == value) return mid;
        else if (a[mid] < value) low = mid + 1;  // 注意：+1，不是 mid
        else high = mid - 1;                      // 注意：-1，不是 mid
    }
    return -1;
}

三个易错点：

1. 循环退出条件：low <= high（不是 <，否则漏掉 low==high 的情况）
2. mid 计算：low + ((high - low) >> 1)（防止整数溢出）
3. low/high 更新：mid+1 和 mid-1（不是 mid，否则死循环）

4 种变体

变体一：查找第一个等于给定值的元素

public int findFirst(int[] a, int n, int value) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] > value) high = mid - 1;
        else if (a[mid] < value) low = mid + 1;
        else {
            if (mid == 0 || a[mid - 1] != value) return mid; // 左邻不等，是第一个
            else high = mid - 1; // 继续往左找
        }
    }
    return -1;
}

变体二：查找最后一个等于给定值的元素

public int findLast(int[] a, int n, int value) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] > value) high = mid - 1;
        else if (a[mid] < value) low = mid + 1;
        else {
            if (mid == n - 1 || a[mid + 1] != value) return mid; // 右邻不等，是最后一个
            else low = mid + 1; // 继续往右找
        }
    }
    return -1;
}

变体三：查找第一个大于等于给定值的元素

public int findFirstGe(int[] a, int n, int value) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] >= value) {
            if (mid == 0 || a[mid - 1] < value) return mid; // 第一个 >=
            else high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

变体四：查找最后一个小于等于给定值的元素

public int findLastLe(int[] a, int n, int value) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (a[mid] <= value) {
            if (mid == n - 1 || a[mid + 1] > value) return mid; // 最后一个 <=
            else low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

四种变体的核心模式

二分查找的局限性

动态规划入门

动态规划（DP） 适合求解最优问题（最大值/最小值），通过将问题分解为多个阶段，记录每个阶段的状态，避免重复计算。

核心思想：空间换时间。

0-1 背包问题

问题：n 个物品，重量为 weight[]，背包最大承重为 W，每个物品只能选一次，求能放入的最大重量。

public int knapsack(int[] weight, int n, int w) {
    boolean[] dp = new boolean[w + 1]; // dp[j] 表示重量 j 是否可达
    dp[0] = true;
    if (weight[0] <= w) dp[weight[0]] = true;

    for (int i = 1; i < n; ++i) {
        for (int j = w - weight[i]; j >= 0; --j) { // 从后往前，避免重复选
            if (dp[j]) dp[j + weight[i]] = true;
        }
    }

    for (int i = w; i >= 0; --i) {
        if (dp[i]) return i;
    }
    return 0;
}

• 时间复杂度：O(n×W)
• 空间复杂度：O(W)（一维数组优化）

最长公共子序列（LCS）

问题：求两个字符串 s1、s2 的最长公共子序列长度（子序列不要求连续）。

状态定义：dp[i][j] 表示 s1 前 i 个字符和 s2 前 j 个字符的 LCS 长度。

状态转移方程：

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

public int lcs(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

• 时间复杂度：O(m×n)
• 空间复杂度：O(m×n)，可优化到 O(min(m,n))

DP 三要素

适用 DP 的问题特征

1. 最优子结构：问题的最优解包含子问题的最优解
2. 无后效性：当前状态一旦确定，不受后续状态影响
3. 重叠子问题：子问题被反复计算（可用备忘录/DP 表优化）

动态规划进阶

在入门的 0-1 背包和 LCS 基础上，这里给出五大 DP 类型的状态转移方程框架，供快速查阅。详细讲解和例题见 06 动态规划.md。

五大 DP 类型框架

线性 DP 框架

dp[i] = max/min over j < i of { dp[j] + transition(j, i) }

经典套路：从左到右遍历，每个 dp[i] 从前面某个状态转移来。

区间 DP 框架

for length in 2..n:          // 枚举区间长度
  for i in 0..n-length:      // 枚举左端点
    j = i + length - 1
    for k in i..j-1:         // 枚举分割点
      dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + cost(i,j,k))

背包 DP 框架

// 0-1 背包（一维优化，从后往前）
for i in items:
  for j from W downto w[i]:
    dp[j] = max(dp[j], dp[j - w[i]] + v[i])

// 完全背包（一维优化，从前往后）
for i in items:
  for j from w[i] to W:
    dp[j] = max(dp[j], dp[j - w[i]] + v[i])

树形 DP 框架

dfs(u):
  dp[u][1] = val[u]          // 选 u
  dp[u][0] = 0               // 不选 u
  for child v of u:
    dfs(v)
    dp[u][1] += dp[v][0]     // 选 u 则子节点不能选
    dp[u][0] += max(dp[v][0], dp[v][1])  // 不选 u 则子节点任意

状态压缩 DP 框架（TSP）

dp[1 << n][n]  // mask 表示已访问城市集合，i 表示当前城市
dp[1][0] = 0   // 初始在城市 0
for mask in 1..(1<<n):
  for i in 0..n:
    if mask & (1 << i):
      for j in 0..n:
        if not mask & (1 << j):
          dp[mask | (1<<j)][j] = min(..., dp[mask][i] + dist[i][j])

参考资料

• 《数据结构与算法之美》— 11~16、40~42 章节
• 极客时间《动态规划面试宝典》— 卢誉声
• 极客时间《业务开发算法 50 讲》— 微扰君