我最近在帮团队做Java技术面试复盘发现一个挺有意思的现象问起候选人“你熟悉的排序算法有哪些”十个人里有九个会提到冒泡排序但真要他在白板上手写一遍能一次写对边界条件的不到三成。更典型的是二分查找很多干了三五年的Java开发能在五分钟内无Bug写出标准版的人说实话不算多。所以我想把“Java优选算法”这个系列认真写下去。不追KMP、不卷红黑树就从最扎实的地基开始每天两个算法讲清楚原理、代码、坑点和面试问法。今天是第一天的内容我选的是两个看起来“简单到不好意思写”的算法冒泡排序和二分查找。如果你以为这两题太基础不值得看那我建议你往下翻翻——我见过太多在它们身上翻车的人了包括曾经的我。1. Day1的选题逻辑为什么优先选这两个算法算法学习的误区我踩得太多了。早些年我也干过“收藏即学会”的事把KMP、红黑树、B树的解析存了一堆张口闭口就是高级词汇结果真到写代码时连一个数组逆序都要想半天。后来我才想明白一个朴素道理算法这玩意是金字塔结构不是积木拼盘。底层不稳上层全是空中楼阁。1.1 排序算法体系里最通用的“母题”排序为什么值得作为整个系列的开篇因为几乎每一种经典排序算法都对应着一类重要的算法思想冒泡排序本质是暴力枚举 相邻比较交换是最朴素的问题求解直觉选择排序对应线性扫描 极值选取是很多贪心策略的雏形插入排序对应增量构建 局部有序是希尔排序的基石归并排序是分治思想最标准的教科书实现快速排序是分区递归 随机化思维的典型代表。也就是说你把排序全部吃透等于同时掌握了暴力、贪心、分治、递归这几套核心方法论。以后无论是刷LeetCode还是写业务代码这些思维都会反复出现。DAY1选冒泡不是因为它实用是因为它能把“排序算法长什么样”这个最基本的感觉带出来后面学快排、归并时对比着看理解会快得多。1.2 查找业务代码里出现频率最高的操作二分查找则完全是另一维度的价值。我工作这些年在真实业务里写过的二分查找一只手数得过来但二分背后暴露出的问题——边界条件、循环不变量、整数溢出——几乎是每天都会遇到的编码细节。更关键的是二分查找是面试算法题的“前置技能”。你去看那些中高难度的题目搜索旋转排序数组、寻找峰值、在排序数组中查找元素的第一个和最后一个位置……它们的解法本质上都是二分查找的变体。Day1就把它拿下后续刷题会顺畅很多。一句话总结选题思路冒泡负责建立“算法感”二分负责训练“边界脑”。一个练框架思维一个抠边界细节这俩凑齐了DAY2再进入选择排序和插入排序节奏正好。2. 冒泡排序的完整推导从“交换直觉”到代码落地2.1 一句话理解冒泡冒泡排序的思想用一句大白话讲每一轮让相邻的两个元素两两比较如果顺序不对就交换经过一轮之后当前未排序区间里最大的数就会像气泡一样“浮”到最右侧。被交换到右侧的大数看着就像水底冒到水面的气泡冒泡排序因此得名。理解这个名字很重要因为很多人在写代码时会忘记“每一轮结束后最右侧已经排好了一位”导致做了大量无效比较。2.2 手写走一遍冒泡过程我们用一个具体数组来推演。假设有这样一个待排序数组[5, 1, 4, 2, 8]目标是升序排列。第一轮从头开始比较相邻元素比较 5 和 15 1交换数组变为[1, 5, 4, 2, 8]比较 5 和 45 4交换数组变为[1, 4, 5, 2, 8]比较 5 和 25 2交换数组变为[1, 4, 2, 5, 8]比较 5 和 85 8不交换数组保持[1, 4, 2, 5, 8]第一轮结束8被“冒泡”到了最后一个位置这是本轮确定的最大值下一轮就不需要再管它了。第二轮只需要比较前4个元素比较 1 和 4不交换保持[1, 4, 2, 5, 8]比较 4 和 24 2交换变为[1, 2, 4, 5, 8]比较 4 和 5不交换保持[1, 2, 4, 5, 8]第二轮结束5到了倒数第二个位置。可以看到此时数组已经整体有序了但因为算法没有“感知”能力它还会继续执行第三轮和第四轮比较。这里就埋下了第一个优化点后面我会具体讲。第三轮比较 1 和 2不交换比较 2 和 4不交换。结束。 第四轮比较 1 和 2不交换。结束。最终得到有序数组[1, 2, 4, 5, 8]。2.3 从推演中总结规律看完整过程你会发现三个关键规律总共需要 n-1 轮外层循环。n个元素每轮确定一个最大值前 n-1 个确定后最后一个自然就位所以外层循环次数是 n-1。第 i 轮只需要比较前 n-i 对相邻元素。因为每完成一轮右侧就多一个已经排好序的元素不需要再参与比较。内层比较的索引范围是 [0, n-1-i]对应代码里的j n - 1 - i。2.4 标准版冒泡排序的Java实现基于以上规律标准版代码长这样public class BubbleSort { public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; // 外层循环控制轮数共 n-1 轮 for (int i 0; i n - 1; i) { // 内层循环第 i 轮只需比较到 n-1-i for (int j 0; j n - 1 - i; j) { // 相邻元素比较升序排列左边 右边就交换 if (arr[j] arr[j 1]) { swap(arr, j, j 1); } } } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }注意j n - 1 - i这个边界是冒泡代码最容易写错的地方。写成j n - i会数组越界写成j n - 1则每一轮都在做重复比较。写完后心里默念一遍“第 i 轮最后 i 个已归位所以比较上限是 n-1-i”基本就不会错了。3. 冒泡排序的两次关键优化与性能实测标准版代码能跑但面试官大概率会追问一句“还能优化吗”这时候你的回答质量直接决定了他对你基础扎不扎实的判断。3.1 第一次优化有序标记提前退出回到刚才推演的例子第二轮结束时数组已经整体有序了但标准版代码依然傻乎乎地跑完了第三轮、第四轮。如果数组原本就接近有序这种无脑比较非常浪费。优化思路很直接加一个布尔标记记录本轮是否发生过交换。如果某一轮全程没有发生任何交换说明数组已经整体有序直接终止外层循环。public static void bubbleSortOptimized1(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; // 每轮开始时重置 for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); swapped true; // 发生了交换 } } // 如果本轮没有发生交换说明已全部有序 if (!swapped) { break; } } }这版优化的意义在于最好情况的时间复杂度从 O(n²) 降到了 O(n)。比如对一个已经排好序的数组第一轮扫描完发现一次交换都没发生立刻退出只做了 n-1 次比较。3.2 第二次优化记录最后交换位置缩小比较区间第一次优化解决的是“完全有序提前退出”的问题。但还有一种情况数组的后半段已经有序而前半段还是乱的。比如[3, 1, 4, 6, 7, 8, 9, 10]第一轮结束时最后一次交换发生在索引 0 和 1 之间也就是数字 4 浮到索引2之后后面的 6、7、8、9、10 本身就是升序没有再发生交换。但下一轮标准版依然会把比较范围扩展到 n-1-1也就是一直比较到倒数第二对而这些比较完全是浪费。优化思路是维护一个变量记录本轮最后一次交换发生的索引位置这个位置之后的所有元素都已经有序下一轮只需要比较到这个位置即可。public static void bubbleSortOptimized2(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; // 当前轮的比较边界初始为数组末尾 int sortBound n - 1; while (sortBound 0) { int lastSwapIndex 0; // 记录本轮最后一次交换的位置 for (int j 0; j sortBound; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); lastSwapIndex j; // 更新为当前交换位置 } } sortBound lastSwapIndex; // 下一轮只需要比较到 lastSwapIndex } }这版优化把“比较边界”变成了动态的。每次循环结束sortBound会收缩到上一轮最后一次发生交换的位置。这样既自然地包含了“提前退出”的效果如果某轮没发生交换lastSwapIndex保持为 0sortBound变为 0循环结束又避免了稳定区段的无效比较。3.3 时间与空间复杂度对照指标标准版优化版有序标记优化版记录交换边界最坏时间复杂度O(n²)O(n²)O(n²)最好时间复杂度O(n²)O(n)O(n)平均时间复杂度O(n²)O(n²)O(n²)空间复杂度O(1)O(1)O(1)稳定性稳定稳定稳定稳定性这一点容易被忽略冒泡排序只在arr[j] arr[j1]时交换相等的元素不会交换位置所以相同值的相对顺序不会改变它是稳定排序。这个特性在面试中可能会被单独拎出来问记住它。3.4 面试中关于冒泡的追问面试官考冒泡排序一般不会只让你写代码。我总结几个常见的追问方向最好情况时间复杂度是多少答 O(n)但前提是加了有序标记优化否则是 O(n²)。冒泡排序是稳定的吗答稳定因为相等元素不交换。和插入排序比有什么区别这个问题很阴险。两者最坏复杂度都是 O(n²)但插入排序在“接近有序”的数据上表现极好且交换次数往往少于冒泡所以工程实现里插入排序更常见。冒泡更多是教学用途。一万个随机整数排序要多少次比较最坏约 5000 万次n(n-1)/2平均也接近这个量级。所以它只适合小规模数据。4. 二分查找二十行代码里的边界陷阱如果说冒泡排序是“大白话算法”那二分查找就是“高段位陷阱王”。它代码量极少逻辑看似简单但写对的概率和代码行数成反比——越短越容易错。我自己面试别人时统计过这个题的错误率超过一半的候选人都不能一次性通过边界测试。4.1 使用前提有序数组 随机访问二分查找的前提有两个数据必须是有序的通常是升序。无序数组需要先排序或者改用哈希表等方式。支持随机访问。也就是说底层数据结构得是数组ArrayList也行不能是链表。链表的“二分”代价极高因为每次取中间元素都要遍历。这也解释了为什么业务代码里直接二分用得少大部分业务数据不会专门维护有序数组而且频繁增删场景下维护有序数组的成本太高。但算法题和面试场景里它出现的频率极高。4.2 核心思想每次排除一半二分查找的思路一句话讲完每次看中间位置的元素如果等于目标值直接返回如果目标值小于中间值说明目标在左半区把右边界移到中间位置左边一位如果目标值大于中间值说明目标在右半区把左边界移到中间位置右边一位。重复这个过程直到区间为空。这里的关键在于每一轮都把搜索区间缩小一半所以查找 n 个元素最多需要 log₂(n) 次比较。100万个元素最多20次比较就能定位这就是它强大的地方。4.3 标准版实现循环不变量是核心写二分查找之前先想清楚你的循环不变量target只能在[left, right]这个左闭右闭区间内。只要这个区间还在收缩就一直循环一旦区间为空说明找不到。public class BinarySearch { /** 在升序数组 arr 中查找 target返回下标找不到返回 -1 */ public static int binarySearch(int[] arr, int target) { if (arr null || arr.length 0) { return -1; } int left 0; int right arr.length - 1; // 右边界取最后一个下标闭区间 while (left right) { // 区间合法条件left right // 防止 left right 整数溢出 int mid left (right - left) / 2; if (arr[mid] target) { return mid; // 找到了直接返回 } else if (arr[mid] target) { left mid 1; // target 在右半区 } else { right mid - 1; // target 在左半区 } } return -1; // 区间为空没找到 } }4.4 为什么 mid 要用left (right - left) / 2计算这是二分查找里最经典的坑。很多人初学时习惯写(left right) / 2看起来没问题但如果left和right都很大两者相加可能超出int的最大值 2147483647造成整数溢出mid 变成负数程序直接崩了。left (right - left) / 2的写法先计算区间长度的一半再加上左边界数学上和(leftright)/2完全等价但不会溢出。这是一道经典面试题很多人以为考的是二分其实考的是溢出意识。4.5 三个常见边界错误对照表错误写法后果正确写法while (left right)配闭区间区间内只剩一个元素时循环退出漏判while (left right)right mid配闭区间可能死循环因为 mid 可能等于 leftright mid - 1left mid配闭区间同样可能死循环left mid 1记忆口诀闭区间写法右边界动过之后是 mid-1左边界动过之后是 mid1循环条件是 left right。这个组合是配套的改一个就得全改。4.6 二分查找的变体面试高频追问题标准版仅仅是个开始面试官真正想考你的是变体。这里列三个最常见的变体一查找第一个等于 target 的位置数组中可能有重复元素需要找到最左边的那个。public static int findFirst(int[] arr, int target) { int left 0, right arr.length - 1; int result -1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { // 即使相等也继续向左找 if (arr[mid] target) { result mid; } right mid - 1; } else { left mid 1; } } return result; }变体二查找最后一个等于 target 的位置对称操作等于或小于时向右半区继续找。public static int findLast(int[] arr, int target) { int left 0, right arr.length - 1; int result -1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { if (arr[mid] target) { result mid; } left mid 1; // 即使相等也继续向右找 } else { right mid - 1; } } return result; }变体三查找第一个大于等于 target 的位置左边界这个变体是很多高级算法的基础比如求最长递增子序列的贪心优化还有TreeMap 的 ceilingEntry 操作。public static int findFirstGreaterOrEqual(int[] arr, int target) { int left 0, right arr.length - 1; int result arr.length; // 默认没有找到返回数组长度表示“都不满足” while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { result mid; right mid - 1; // 向左收缩找更小的满足索引 } else { left mid 1; } } return result; }这三种变体值得你在本地跑一遍测试用例尤其是全等于、全小于、全大于、空数组这些边界跑通了之后你对二分的理解会上一个台阶。5. 刷题落地的实战心得调试方法与避坑清单最后这部分不写原理全是实操中积累的经验。算法光看不练等于白看但练的方式方法决定了效率。5.1 用断点调试代替“人脑debug”我曾经见过很多人刷题代码跑不过就盯着屏幕看试图“人脑模拟”出问题。这种方式对复杂算法来说效率极低我建议直接用IDE的断点调试。IntelliJ IDEA 里按以下步骤操作在while循环第一行打上断点以 Debug 模式运行观察left、right、mid三个变量的实时变化单步执行每走一步对照当前区间判断程序行为是否符合预期。这比任何口头讲解都直观。二分写错的人通常调试一两次就能找到规律比如发现left和right始终无法收敛、mid 重复计算同一个位置导致死循环等。5.2 冒泡排序的典型错误排查冒泡最容易出的Bug是数组越界报错信息一般是ArrayIndexOutOfBoundsException。我之前帮同事排查过一版代码他写的内层循环是j n当j n-1时arr[j1]直接越界。排查方法很简单用边界输入跑一遍。比如n 1的数组[5]和n 2的数组[2, 1]。这两个最小用例能暴露九成以上的边界问题。另外还有一个隐蔽错误内层循环写成j n - i - 1还是j n - i - 2两者在数学上等价但前者更容易理解也更好记。写代码时优先选语义清晰的写法。5.3 二分查找的测试用例设计二分查找想验证正确性至少准备这六类测试数据测试类别示例数组目标值期望结果空数组[]任意-1单元素数组命中[5]50单元素数组未命中[5]3-1目标在数组开头[1, 3, 5, 7]10目标在数组结尾[1, 3, 5, 7]73目标不存在但介于中间[1, 3, 5, 7]4-1每一类都过了标准版二分才算合格。变体版还需要额外测试重复元素的场景比如[1, 2, 2, 2, 3]查第一个2返回1、最后一个2返回3。5.4 Day1的收尾节奏与作业DAY1不建议贪多两个算法彻底吃透比囫囵吞枣看十个有效得多。我给自己定的节奏是上午通读本文跟着推演过程手写一遍冒泡和二分不要复制代码合上文章自己写下午跑通6类二分测试用例再自己设计3个冒泡测试用例验证两次优化逻辑晚上把两个变体二分的代码默写一遍不看参考答案。明天DAY2会进入选择排序和插入排序以及“为什么插入排序比冒泡更适合工程场景”这个很多人想不明白的问题。到时候我会给出一组同样的数组在这几种排序下的实测算例对比相信看完你会对“复杂度相同但表现不同”有更直观的体会。算法学习的路上今天是第一步。没有花哨的技巧但地基就这么一块一块打的。