算法与数据结构（三）：排序与查找
导语：排序是面试中"必须能手写"的少数几个算法之一。本篇先给出一张复杂度与稳定性总表，再逐个手写实现（冒泡、选择、插入、希尔、归并、快排、计数、桶、基数），最后覆盖二分查找的四个坑与两种变体、快速选择与外部排序。所有算法均给出可运行的 Java 代码。共 13 题。
一、排序总览
1. 常见排序算法的复杂度与稳定性对比？什么是稳定性？
答： 稳定性指排序前后值相等的元素保持原有的相对顺序。
为什么稳定性重要：
- 多字段排序：先按次要字段排、再按主要字段排（稳定排序能保留上一次的次序）；
- 业务语义：按时间排序的日志、按价格排序的商品，相等元素应保持原始插入顺序，否则用户会觉得"数据乱跳"。
总表（重点记忆前 7 行的勾选情况）：
| 算法 | 最好 | 平均 | 最坏 | 额外空间 | 稳定性 | 是否比较排序 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 是 |
| 希尔排序 | O(n log n) | 约 O(n^1.3) | O(n²) | O(1) | 不稳定 | 是 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 是 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n)~O(n) | 不稳定 | 是 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 是 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 稳定 | 否 |
| 桶排序 | O(n + k) | O(n + k) | O(n²) | O(n + k) | 稳定 | 否 |
| 基数排序 | O(n × d) | O(n × d) | O(n × d) | O(n + k) | 稳定 | 否 |
一句话记忆："快排不稳、归并稳、堆排不稳但空间 O(1)"；
O(n²)三种里只有选择排序不稳定（因为它做的是远距离交换，会把相等元素的相对次序打乱）。
二、O(n²) 排序
2. 冒泡排序如何实现？（含优化）
答： 相邻两两比较，把较大值"冒"到末尾，每趟确定一个最大值的位置。
public void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean swapped = false; // 优化标记
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) { // 用 > 而非 >=，相等不交换 → 稳定
swap(arr, j, j + 1);
swapped = true;
}
}
if (!swapped) break; // 本趟无交换 → 已有序，提前退出
}
}- 最好
O(n)：数组已有序时，第一趟无交换即结束（这是"最好情况 O(n)"的来源，没有这个swapped优化就永远是 O(n²)）； - 稳定：只有严格大于才交换，相等元素不会越过彼此。
"冒泡还有必要学吗？" 有必要——小规模、基本有序时它的常数极小、实现最简单、稳定、空间严格
O(1)。这也是很多语言内置排序在"小数组"时切换为插入/冒泡的原因。
3. 选择排序如何实现？为什么它不稳定？
答： 每趟从未排序区间选出最小值，与未排序区间的第一个位置交换。
public void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIdx]) minIdx = j; // 找最小值下标
}
if (minIdx != i) swap(arr, i, minIdx); // 交换到已排序区末尾
}
}为什么不稳定：交换是跨区间的远距离交换，会把相等元素的相对顺序打乱。
举例：[5a, 5b, 2] —— 第一趟把最小值 2 与 5a 交换，得到 [2, 5b, 5a]，两个 5 的相对次序被颠倒。
三个
O(n²)排序的交换特征对比：冒泡/插入都是相邻交换（故稳定），选择是远距离交换（故不稳定）。
4. 插入排序如何实现？为什么小规模时最快？
答： 把当前元素插入到左侧已排序区间的正确位置，类似"摸扑克牌理牌"。
public void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int cur = arr[i]; // 待插入元素
int j = i - 1;
while (j >= 0 && arr[j] > cur) { // 用 > 而非 >=，相等则停下 → 稳定
arr[j + 1] = arr[j]; // 比它大的元素整体后移
j--;
}
arr[j + 1] = cur; // 插入空位
}
}为什么小规模最快：
- 常数因子极小：只有一次赋值与比较，没有函数调用与复杂下标运算；
- 最好
O(n)：基本有序时几乎不移动元素； - 缓存友好：顺序访问内存，CPU 缓存命中率高；
- 近乎有序时接近
O(n)：数据局部有序程度越高越快。
这也是为什么
Arrays.sort()（DualPivotQuicksort）在子数组长度小于 47 时会切换为插入排序——大算法配小算法，是大厂工程实现的标准做法。
5. 希尔排序如何实现？
答： 希尔排序是插入排序的改进版：先用较大增量（gap）对间隔 gap 的元素做插入排序，让数组"大致有序"，再逐步缩小 gap 直到 1（最后一次就是标准插入排序，但此时数组已近乎有序，非常快）。
public void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) { // 增量序列：n/2, n/4, ..., 1
for (int i = gap; i < n; i++) {
int cur = arr[i], j = i - gap;
while (j >= 0 && arr[j] > cur) { // 对间隔 gap 的分组做插入排序
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = cur;
}
}
}- 复杂度依赖增量序列：
n/2递减序列最坏O(n²)；Hibbard 序列约O(n^1.5)；平均约O(n^1.3)； - 不稳定：跨增量交换会打乱相等元素的相对顺序；
- 空间
O(1)。
希尔排序是第一个突破
O(n²)的算法（平均意义上），它证明了"利用插入排序对近乎有序数据高效"这一特性可以层层放大。
三、O(n log n) 排序
6. 归并排序如何实现？为什么它稳定？
答： 典型分治：把数组一分为二，递归排好左右两半，再合并两个有序数组。
public void mergeSort(int[] arr) {
if (arr.length < 2) return;
mergeSort(arr, 0, arr.length - 1, new int[arr.length]); // 辅助数组只申请一次
}
private void mergeSort(int[] arr, int left, int right, int[] tmp) {
if (left >= right) return;
int mid = left + (right - left) / 2; // 防溢出
mergeSort(arr, left, mid, tmp);
mergeSort(arr, mid + 1, right, tmp);
merge(arr, left, mid, right, tmp);
}
private void merge(int[] arr, int left, int mid, int right, int[] tmp) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++]; // <= 优先取左边 → 稳定
}
while (i <= mid) tmp[k++] = arr[i++]; // 左半剩余
while (j <= right) tmp[k++] = arr[j++]; // 右半剩余
System.arraycopy(tmp, left, arr, left, right - left + 1); // 拷回原数组
}为什么稳定：合并时遇到相等元素优先取左半区的（arr[i] <= arr[j]），而左半区的元素原本就在右边之前，因此相等元素的相对次序得以保持。
特点：
- 时间稳定
O(n log n)（不受数据分布影响），空间O(n)； - 适合外部排序与链表排序（链表归并无需随机访问，且空间可优化为
O(1)）； - 缺点：需要额外数组，且内存拷贝带来常数开销。
Java 中
Arrays.sort(Object[])用的就是归并的变体 TimSort（对象数组需要稳定性），而Arrays.sort(int[])用的是双轴快排（基本类型不需要稳定性，追求速度）。
7. 快速排序如何实现？最坏为什么会退化成 O(n²)？如何优化？
答： 快排也是分治：选一个基准（pivot）→ 分区（partition）使左边都 ≤ 基准、右边都 ≥ 基准 → 递归两侧。
public void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int p = partition(arr, left, right); // 分区，返回基准最终位置
quickSort(arr, left, p - 1); // 注意：p 本身已就位，不参与递归
quickSort(arr, p + 1, right);
}
private int partition(int[] arr, int left, int right) {
// 优化 1：随机选基准，交换到 left，避免有序数组导致的最坏情况
int random = left + (int) (Math.random() * (right - left + 1));
swap(arr, left, random);
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--; // 从右往左找 < pivot 的
while (i < j && arr[i] <= pivot) i++; // 从左往右找 > pivot 的
if (i < j) swap(arr, i, j);
}
swap(arr, left, i); // 基准归位到 i
return i;
}最坏 O(n²) 的成因：若每次都选到最值作为基准（例如基准固定取第一个元素、而数组已经有序或近乎有序），分区后一侧为空、另一侧有 n-1 个元素，递归深度退化为 n，总代价 n + (n-1) + ... + 1 = O(n²)。
三大优化：
| 优化 | 做法 | 解决的问题 |
|---|---|---|
| 随机基准 | 随机选一个元素与首位交换后再当基准 | 避免有序/逆序输入退化 |
| 三数取中 | 取 left、mid、right 三者的中位数当基准 | 同样避免极端划分，且无随机开销 |
| 小区间切插入排序 | 子数组长度小于阈值（如 15~47）时改用插入排序 | 减少递归开销（小数组上插入排序常数更小） |
其他易错点：① 递归时不要再包含
p（已就位），否则死循环；② 双指针法要保证i < j的判断在内外层都不能少，否则下标越界；③ 快排不稳定（交换是跨区间的）。
四、线性时间排序
8. 计数排序如何实现？
答： 不比较元素，直接统计每个值出现的次数，再根据次数还原序列。适合数据范围 k 较小的整数。
import java.util.Arrays;
public void countingSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int[] count = new int[max - min + 1]; // 用偏移量 min 处理负数
for (int v : arr) count[v - min]++; // 1. 统计频次
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1]; // 2. 前缀和 → 得到每个值的"结束位置"
}
int[] res = new int[arr.length];
// 3. 从后往前填，保证稳定性
for (int i = arr.length - 1; i >= 0; i--) {
res[--count[arr[i] - min]] = arr[i];
}
System.arraycopy(res, 0, arr, 0, arr.length);
}- 时间
O(n + k)、空间O(k)（k为值域大小）； - 稳定性取决于第 3 步——必须从后往前遍历，才能让先出现的相等元素落在前面；
- 局限：只适合整数，且
k不能太大（若k = 10^9就无法开数组了）。
9. 桶排序与基数排序如何实现？
答： 两者都是"按位/按区间分桶，桶内再排序"的思想。
桶排序：把数据按值域划分到若干桶，桶内各自排序后按序拼接。适合数据均匀分布的场景。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public void bucketSort(double[] arr) {
int n = arr.length;
List<List<Double>> buckets = new ArrayList<>(n);
for (int i = 0; i < n; i++) buckets.add(new ArrayList<>());
for (double v : arr) {
int idx = (int) (v * n); // 假设元素均匀分布在 [0, 1)
buckets.get(idx).add(v);
}
int k = 0;
for (List<Double> bucket : buckets) {
Collections.sort(bucket); // 桶内排序（小数据可用插入排序）
for (double v : bucket) arr[k++] = v;
}
}基数排序（LSD，从低位到高位）：对每一位做一次计数排序，d 轮后即有序。
public void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10) { // 按个位、十位、百位……逐位排序
sortByDigit(arr, exp);
}
}
private void sortByDigit(int[] arr, int exp) {
int[] count = new int[10]; // 每一位只有 0~9
for (int v : arr) count[(v / exp) % 10]++;
for (int i = 1; i < 10; i++) count[i] += count[i - 1];
int[] res = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) { // 从后往前 → 稳定
int d = (arr[i] / exp) % 10;
res[--count[d]] = arr[i];
}
System.arraycopy(res, 0, arr, 0, arr.length);
}- 基数排序时间
O(n × d)（d为最大位数）、空间O(n + k)、稳定； - 上面的实现只处理非负整数，含负数需先分离符号或加偏移量；
- 适合位数少、数据量大的场景（如手机号、身份证排序）。
三种线性排序的共同前提：都不是比较排序，因此不受
O(n log n)下界约束（该下界只适用于基于比较的排序）。代价是对数据有额外假设（值域小 / 分布均匀 / 位数少）。
五、查找
10. 二分查找怎么写？四个坑是什么？
答： 二分查找要求数据有序，每次比较中间元素、排除一半区间。
public int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1; // 闭区间 [left, right]
while (left <= right) { // 闭区间用 <=
int mid = left + (right - left) / 2; // 防溢出写法
if (nums[mid] == target) return mid;
else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}四个经典坑：
| 坑 | 错误写法 | 正确做法 |
|---|---|---|
| 整数溢出 | mid = (left + right) / 2（两值都接近 Integer.MAX_VALUE 时溢出变负数） | mid = left + (right - left) / 2 |
| 区间语义不统一 | 闭区间 [l,r] 配 while(l<r)，或混用 right = mid 与 right = mid - 1 | 选定一种并全程一致：闭区间配 while(l<=r) + mid±1；左闭右开 [l,r) 配 while(l<r) + right=mid |
| 死循环 | 更新边界时忘记 +1/-1，区间不收缩 | 边界必须严格收缩，确保每轮区间变小 |
| 变体错误 | 找左右边界时 nums[mid] == target 就 return | 变体中不能提前返回，要继续收缩边界（见下题） |
统一记法（推荐左闭右开）：
left = 0, right = n; while (left < right) { mid = left + (right-left)/2; ... }，左侧收缩用left = mid + 1，右侧收缩用right = mid（不是 mid-1）。这套写法天然适配"找边界"类问题，不容易错。
11. 二分查找的变体：如何找左右边界？
答： 找"第一个 ≥ target"与"最后一个 ≤ target"的位置，关键是 nums[mid] == target 时不返回，继续收缩。
// lowerBound：第一个 >= target 的下标（不存在则返回 nums.length）
public int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length; // 左闭右开 [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) left = mid + 1; // 不满足条件 → 排除左半
else right = mid; // 满足条件 → 保留 mid，收缩右半
}
return left; // left == right，即答案位置
}
// upperBound：最后一个 <= target 的下标（不存在则返回 -1）
public int upperBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) left = mid + 1; // 满足条件 → 继续往右找
else right = mid;
}
return left - 1; // left 是第一个 > target 的位置，减一即答案
}基于这两个函数可以解决一批题：
| 需求 | 写法 |
|---|---|
| 第一个等于 target | lowerBound(nums, target)，再校验该位置是否恰好等于 |
| 最后一个等于 target | upperBound(nums, target)，再校验 |
| 第一个大于 target | upperBound(nums, target) + 1 |
| 有序数组中 target 出现次数 | upperBound - lowerBound + 1（需校验边界） |
面试话术：与其记一堆"左闭右开+1-1"的口诀，不如固定一套模板并解释"为什么这样不会死循环"——
right = mid保证区间每轮至少缩小 1（因为mid < right恒成立）。这比背模板更能体现理解。
12. 什么是快速选择（QuickSelect）？如何求第 K 大元素？
答： 快速选择是快排 partition 的"半递归"版本：分区后只递归包含目标下标的那一侧，因此平均复杂度从 O(n log n) 降到 O(n)。
// 求第 k 大元素（k 从 1 开始计）：换算成升序下标 target = n - k
public int findKthLargest(int[] nums, int k) {
int target = nums.length - k;
int left = 0, right = nums.length - 1;
while (true) {
int p = partition(nums, left, right); // 复用快排的 partition
if (p == target) return nums[p]; // 基准正好落在目标位置
else if (p < target) left = p + 1; // 只往右找
else right = p - 1; // 只往左找
}
}复杂度：T(n) = n + n/2 + n/4 + … ≈ 2n，即平均 O(n)；最坏（每次都选到最值）仍为 O(n²)，可用随机基准规避。空间 O(1)。
三种求 Top K 方案的选型：
| 方案 | 时间 | 空间 | 何时选 |
|---|---|---|---|
| 全排序 | O(n log n) | O(log n) | 数据量小、顺便要整体有序 |
| 大小为 K 的堆 | O(n log k) | O(k) | 数据量大 / 流式（n 极大、k 小） |
| 快速选择 | 平均 O(n) | O(1) | 数据可全量入内存、只求一次答案 |
注意：快速选择会修改原数组；且它只保证"第 K 大"正确，不保证前 K 个有序。
13. 数据量超过内存、无法一次性加载时如何排序？
答： 这就是外部排序（External Sort），核心是两阶段 + 多路归并：
阶段一：生成有序顺段（run）
- 把大文件按内存容量切成若干块，每块加载进内存，用快排/堆排排好；
- 排好的块写回磁盘，形成一个个局部有序的"顺段"；
- 进阶：用置换选择（Replacement Selection）算法生成顺段，平均长度可达内存大小的 2 倍，减少顺段数量。
阶段二：多路归并
- 从每个顺段读入一部分，用k 路归并不断选出全局最小者写入结果文件；
- 关键优化：用败者树（Loser Tree） 代替"每次线性扫描 k 个候选"——败者树能在
O(log k)内选出最小值，把这一阶段的比较开销从O(k)降到O(log k)，而归并的层数也直接决定磁盘 I/O 次数（这是外部排序的真正瓶颈）。
为什么 I/O 是关键：外部排序的耗时几乎全在磁盘读写上，所以优化的核心是减少归并趟数（增大归并路数
k、减少顺段数），而不是优化比较次数。k越大，趟数越少，但每次比较开销越大——败者树正是为了在这个权衡中取得最优。
一句话记忆："内存排序分批 → 生成顺段 → 败者树做 k 路归并"。这也是数据库
ORDER BY落盘排序、大数据 Shuffle 阶段 sort-spill 的底层原理。