🔀 排序与查找
十大排序对比 · 快排/归并/堆排手写 · 二分查找及其变体
1. 常见排序算法对比（必背表）？
| 算法 | 平均 | 最坏 | 空间 | 稳定 |
|---|---|---|---|---|
| 冒泡 | O(n²) | O(n²) | O(1) | ✅ |
| 选择 | O(n²) | O(n²) | O(1) | ❌ |
| 插入 | O(n²) | O(n²) | O(1) | ✅ |
| 希尔 | O(n^1.3) | O(n²) | O(1) | ❌ |
| 快排 | O(n log n) | O(n²) | O(log n) | ❌ |
| 归并 | O(n log n) | O(n log n) | O(n) | ✅ |
| 堆排 | O(n log n) | O(n log n) | O(1) | ❌ |
| 计数 | O(n+k) | O(n+k) | O(n+k) | ✅ |
| 桶 | O(n+k) | O(n²)（数据全落一个桶） | O(n+k) | 取决于桶内排序 |
| 基数 | O(d(n+k)) | O(d(n+k)) | O(n+k) | ✅ |
🎯 面试要点
- 稳定性含义：相等元素的相对顺序不变。归并稳定、快排/堆排不稳定
- 快排最坏 O(n²) 的原因：每次基准都是最值（如已有序数组选第一个）→ 随机基准/三数取中缓解
- JDK 的 Arrays.sort：基本类型用双轴快排，对象用 TimSort（归并优化版）——稳定且利用有序性
2. 手写快速排序（含 partition）？
思路：选基准 → partition 把小于基准的放左边、大于的放右边 → 递归左右。partition 是核心（荷兰国旗/挖坑法）。
快排 + 挖坑法 partition
void quickSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
}
int partition(int[] a, int lo, int hi) {
int pivot = a[lo]; // 基准挖坑
while (lo < hi) {
while (lo < hi && a[hi] >= pivot) hi--; // 右边找小的
a[lo] = a[hi]; // 填左边的坑
while (lo < hi && a[lo] <= pivot) lo++; // 左边找大的
a[hi] = a[lo]; // 填右边的坑
}
a[lo] = pivot; // 基准归位
return lo;
}🎯 面试要点
- 快排的延伸：TopK 问题用 partition 剪枝——partition 后基准下标 == k 即答案，平均 O(n)（比排序 O(n log n) 快）
- 双指针（左右扫描）和挖坑是 partition 两种主流写法，会一种+理解即可
- 随机基准：swap(a, lo, lo + random) 再 partition，防有序数组退化
3. 归并排序和堆排序的实现要点？
归并：分治——拆到单元素，再两两合并有序数组。合并两个有序数组是高频子题（面试常单考）。外部排序（大数据文件排序）也是归并思想。
堆排：建堆（从最后一个非叶子节点下沉）→ 反复把堆顶（最值）与末尾交换并收缩堆。关键：下沉（siftDown）操作。
归并排序（合并步骤）
void mergeSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) >>> 1;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
merge(a, lo, mid, hi); // 合并两个有序段
}
void merge(int[] a, int lo, int mid, int hi) {
int[] tmp = new int[hi - lo + 1];
int i = lo, j = mid + 1, k = 0;
while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
System.arraycopy(tmp, 0, a, lo, tmp.length); // 拷贝回原数组
}🎯 面试要点
- 归并的额外空间 O(n)：临时数组；注意
(lo+hi)>>>1防溢出 - 堆排不稳定、原地 O(1)；实现长易错，考手写概率低于快排，但"用堆做 TopK/中位数"必考思路
- 海量数据 TopK：堆方案 O(n log k)，内存只存 k 个——必答场景
4. 二分查找的模板与变体？
二分前提：有序（或具备二段性）。易错点：边界（left < right vs <=）、mid 取整方向、收缩边界——背一个模板并理解。
三种查找模板
// 1. 标准查找（闭区间）
int binarySearch(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) { // 闭区间：<=
int mid = lo + ((hi - lo) >>> 1); // 防溢出写法
if (a[mid] < target) lo = mid + 1;
else if (a[mid] > target) hi = mid - 1;
else return mid;
}
return -1;
}
// 2. 找左边界：第一个 ≥ target 的位置（可能等于 n，表示全都小于 target）
int lo = 0, hi = a.length; // 注意 hi 取 n（左闭右开）
while (lo < hi) {
int mid = lo + ((hi - lo) >>> 1);
if (a[mid] >= target) hi = mid; // 收缩右边界
else lo = mid + 1;
}
// 3. 找右边界：最后一个 ≤ target 的位置
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int mid = lo + ((hi - lo + 1) >>> 1); // 上取整防死循环！
if (a[mid] <= target) lo = mid;
else hi = mid - 1;
}🎯 面试要点
- 左边界 mid 下取整、右边界 mid 上取整——上取整那行最容易写错（死循环）
- 二分的进阶应用：旋转数组找最小值（比较 a[mid] 与 a[hi]）、搜索旋转数组、二维矩阵查找
- 二分答案：值域二分（如"最小化最大值"的分配问题）——难题常考思想