← 课程目录 🚀 从零到一
📐 学习维度 阶段8 · 第32章 数据结构与算法专题(leetcode 分类刷题指南) 🚀 从零到一 📚 课程目录 🏠 首页 🛤️ 学习路径

32.6 排序、二分与刷题方法论:算法章收口

审校 2026-09-29 · 素材来源:Java排序算法面试手写精讲系列复盘、raw 50 四周刷题计划
📑 本篇章节导航 (共10节,点击直达)
场景:排序与二分的考察方式类比与定义:分治与对半最小可跑示例:快排与二分原理拆解:算法选择与刷题方法论归并排序:稳定性的担当排序全家速查:九选一怎么说刷题执行规格:可量化的纪律踩坑清单面试怎么问一句话总结

算法章最后一讲做两件事:手写排序与二分这两个还没补的基本功,以及整套刷题方法论——题单怎么刷、考场怎么答、八周计划里算法占几格。素材来自排序手写精讲系列与必刷题单的四周计划,这一讲也替没有算法专项训练的 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 工程师的算法够用线。