算法章最后一讲做两件事:手写排序与二分这两个还没补的基本功,以及整套刷题方法论——题单怎么刷、考场怎么答、八周计划里算法占几格。素材来自排序手写精讲系列与必刷题单的四周计划,这一讲也替没有算法专项训练的 Java 工程师给出一条最短路径。
「手写快排」至今仍是手撕环节的常客,因为它一次考到递归、分区、边界与交换四处细节。二分则更隐蔽——「有序数组找目标」「找第一个大于等于 x 的位置」,考的是边界收紧与循环不变量。两者共同的答题结构:先说思路复杂度,再写代码,最后用两三个数组长度的例子走一遍验证。
分治(把大问题切成独立小问题分别解决再合并)像几个小组分头搬砖再汇总;快排是「先分区再递归」,归并是「先递归再合并」——一句话记住两者差异。二分查找像翻字典:每次折半,前提是有序;每次循环必须让区间严格变小,否则死循环。
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[hi], i = lo; // 取末位为基准
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { // 小于基准的换到左侧
int t = a[i]; a[i] = a[j]; a[j] = t; i++;
}
int t = a[i]; a[i] = a[hi]; a[hi] = t; // 基准归位
return i;
}
// 二分:找第一个 >= target 的位置(左边界)
int lowerBound(int[] a, int target) {
int l = 0, r = a.length; // 右界开区间
while (l < r) {
int mid = l + (r - l) / 2; // 防溢出写法
if (a[mid] < target) l = mid + 1;
else r = mid; // 收紧右界
}
return l;
}
防溢出的 l + (r - l) / 2、开闭区间约定先声明——这两句话能挡掉一半追问。
排序怎么选(精讲系列的结论):面试手写首选快排(平均 O(n log n)、原地),追问稳定性就说归并(稳定但 O(n) 辅助空间),追问「JDK 里是什么」答——基本类型双轴快排、对象数组 TimSort(归并+插入混合,保稳定性),Arrays.sort 源码追问在第 6 章有铺垫。堆排序作为「最坏也是 O(n log n) 且 O(1) 空间」的选项带一句即可。四周刷题计划(题单版):第一周数组+链表(32.1/32.2),第二周树+哈希(32.3/32.4),第三周 DP+回溯(32.5),第四周全部重做一遍错题加限时模拟——重做比刷新题重要,间隔重复同样适用于刷题。考场四步法(精讲系列的答题法):澄清输入特性 → 说思路与复杂度 → 写代码边写边念 → 两个例子走查边界。每题控制在十到十五分钟,走查环节是「不是背题」的最强证明。
快排写完,追问十有八九落到「写个稳定的」或「链表怎么排序」——答案都是归并。合并两个有序数组是它的全部灵魂:
void mergeSort(int[] a, int lo, int hi) { // [lo, hi)
if (hi - lo < 2) return;
int mid = (lo + hi) >>> 1;
mergeSort(a, lo, mid); mergeSort(a, mid, hi); // 先递归
int[] tmp = new int[hi - lo]; // 再合并
int i = lo, j = mid, 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);
}
<= 取左是稳定性的全部:相等时左半先落,相对次序得以保留。归并的两个延伸必须会接:链表排序用归并(快排对链表没有数组下标的分区便利,而归并找中点+合并正好是 32.2 的 876+21 两块积木);外部排序(内存装不下的大文件)先切块排序再多路归并——大数据 Shuffle 的思想源头(第 33.1 讲会再遇到)。
面试的排序追问最终都会落在「让你选,选哪个」:小数组(几十个元素)插入排序最快,没有递归开销;基本有序的数据也是插入的天下;内存紧张、要求最坏复杂度,堆排序 O(n log n) 且 O(1) 空间;要稳定且不在乎辅助空间,归并;通用场景,快排平均最快;JDK 的选择更讲究——基本类型双轴快排(比较便宜、不稳定无妨),对象数组 TimSort(比较贵、稳定必须保),「按数据类型换算法」这个设计本身就是答案的天花板(第 6.2 讲拆过 ConcurrentHashMap,同款思想)。答题话术:先问数据特性(规模、是否基本有序、是否要稳定、内存约束),再报选择——与系统设计的「先澄清再动笔」完全同构。
四周计划的执行规格落到数字上:每天固定时段两题(建议早晨,算法吃清醒度),每题限时二十五分钟——做不出就看题解,看懂后标记「重做」;错题本只记三行:题号、卡壳原因(思路/边界/实现)、一句话钥匙;重做节奏为第二天、第四天、第七天三连(间隔重复);周六模拟三题四十五分钟全真环境(白纸或纯文本编辑器,无补全无运行)。验收指标不是刷了多少题,而是两个比率:错题重做通过率(目标八成)与模拟限时完成率(目标两题以上)。这套规格来自题单四周计划与精讲系列的答题法,照抄即可执行——方法论的价值就在可执行,能落成数字的计划才叫计划。
手写快排背「分区-递归」,二分背「区间约定先声明」,刷题背「四周计划、重做为王」——算法章六讲到这里收口:二十道必刷题,每个套路一个丢弃论证,就是 Java 工程师的算法够用线。