企业官网建设流程全解析

数组排序算法，几乎是每个程序员入门时都要过的一道坎。很多同学在面试前突击背代码，能一字不差默写冒泡排序，但要真问他为什么需要双重循环、为什么交换发生在里层、时间复杂度到底怎么推出来的，就支支吾吾说不清了。这篇笔记是我自己反复梳理、亲手实现、也踩过不少坑之后的总结，把冒泡、选择、插入三种基础排序和二分查找放在一起，因为她们之间有一条完整的学习链条：先搞懂排序，才能理解在有序数据上二分查找的价值。适合刚开始学数据结构、准备笔试面试，以及想彻底夯实算法基础、而不是满足于“背代码”的开发者。

1. 排序算法的学习价值与复杂度基础

1.1 为什么还要手写这些“过时”的算法

现在几乎每种主流编程语言都有现成的排序函数，随便一调就能完成排序，那为什么还要浪费时间去手写冒泡、选择和插入？这是初学者最容易产生的疑问，也是很多人直接跳过基础排序、直奔快速排序和归并排序的原因。我的看法恰恰相反：基础排序是理解整个排序体系的地基，地基不打牢，后面学快排、堆排、归并时只会更困惑。

面试和笔试场景是最表面的一层价值，更重要的在于这几种算法各自代表了一种解决问题的思路。冒泡体现的是“相邻交换、逐步收敛”，选择体现的是“每次确定一个最终位置”，插入体现的是“维护局部有序，扩大有序区间”。这些思想在后面会反复出现：插入排序的思路在希尔排序里被沿用，选择排序的思路冒出了堆排序，冒泡的交换思想在鸡尾酒排序、奇偶排序里都是核心。没有这些基本盘，直接去啃复杂算法，会很难消化。

另外，手写基础算法的过程，其实是在训练一种“精确表达”的能力。代码没有歧义，边界条件写不清楚就会出错，交换逻辑写反了结果就是错的。这种对逻辑严谨性的打磨，才是这类练习真正的价值所在。

1.2 时间复杂度与空间复杂度应该怎么看

学习任何排序算法，第一件事就是搞清楚它的时间复杂度和空间复杂度。时间复杂度不是算出来的精确执行时间，而是描述算法执行时间随数据规模增长的“增速”。

考虑数据规模为 n，常见的时间复杂度从好到差排列：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。基础排序算法中出现频率最高的是 O(n²)，也就是数据量翻一倍，执行时间会变成原来的四倍左右，因为嵌套双重循环导致操作次数接近 n × n。

看代码数循环层数是估算时间复杂度的最快方法。一段两层嵌套循环，每层都跟 n 有关，整体复杂度基本就是 O(n²)。这种推算能力不只是在做题时用，实际写代码时同样重要。我遇到过不少同学写完一个两层循环，完全没有想过它在数据量到十万级时会跑得有多慢，直到线上卡死才反应过来。

空间复杂度衡量的是算法在运行过程中额外占用的内存。冒泡、选择、插入这三种算法都只用了常数级别的额外空间，也就是 O(1)，因为它们都是在原数组上通过交换、移动来排序，不需要复制一份完整的数据。这是它们的一大优点，尤其是对内存敏感的环境。

1.3 稳定性的概念与意义

稳定性这个概念，很多教材一笔带过，但面试官特别喜欢追问。稳定性的定义其实很简单：排序前后，相等元素的相对顺序保持不变，则称这个排序算法是稳定的；如果相等元素的相对顺序可能被改变，则是不稳定的。

举个例子，有一个数组[{name: "A", score: 90}, {name: "B", score: 90}, {name: "C", score: 88}]，先按分数排序，如果算法是稳定的，那么分数相同的 A 和 B 会保持原来的先后顺序。这个性质在需要“多关键字排序”的场景中意义重大。比如先按成绩排序，再按学号排序，如果第二次排序算法不稳定，第一次排序的结果可能被破坏。

实际开发中，按时间排序后又按优先级排序、按部门分组后又按姓名排序，都是典型的稳定排序需求。所以判断一个算法的稳定性，是选型时绕不开的一环。我先给结论：冒泡排序和插入排序是稳定的，选择排序不稳定，至于为什么，后面对应章节里我会详细拆解。

2. 冒泡排序：最直观的交换排序

2.1 核心思想与直观理解

冒泡排序的思想一句话就能说清楚：通过相邻元素的两两比较，把大的元素像气泡一样逐步“冒”到数组末尾，每一轮冒泡都能确定一个最大值的位置。

假设数组是[5, 3, 8, 1, 9, 2]，第一轮从第一个元素开始，5 和 3 比较，5 大，交换，数组变成[3, 5, 8, 1, 9, 2]；接着 5 和 8 比较，8 大，不交换；8 和 1 比较，交换；8 和 9 比较，不交换；9 和 2 比较，交换。一轮结束后，最大值 9 已经“浮”到了最后一位。第二轮只需要比较前五个元素，第二大的元素会“浮”到倒数第二位。以此类推，n 个元素的数组最多需要 n-1 轮，每轮比较的次数递减。

这个算法的直观程度很高，特别适合用来建立“双重循环”的直觉。外循环控制轮数，内循环负责逐对比较和交换，两个循环一嵌套，问题就清楚了。这也是我建议初学者从冒泡开始的原因，它把排序中最核心的“比较—交换”动作，用最直白的方式呈现了出来。

2.2 基础实现与代码解析

最经典的冒泡排序实现如下：

def bubble_sort(arr): n = len(arr) for i in range(n - 1): for j in range(n - 1 - i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr

代码里有两个边界需要真正理解，而不是死记。第一个边界是外循环层的range(n - 1)，为什么不是range(n)？因为每轮冒泡确定一个最大值的位置，n 个元素里最后只剩下一个元素时，它自动就是最小的，不需要再单独比较，所以最多 n-1 轮。

第二个边界是内循环的n - 1 - i。这个-i是冒泡排序的精髓所在：第 i 轮结束时，数组末尾已经有 i 个元素是排好序的，这些元素不需要再参与下一轮比较。如果不减i，算法虽然也能排序，但会做大量无意义的重复比较。很多初学同学会在这一步犯错，内层循环写成range(n - 1)，结果还是能排序成功，但实际效率变差了。

在 Java、C、Go 等语言中，交换需要写一个临时变量：temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp。Python 的多元赋值简化了这个过程，但理解底层仍然有三个步骤，面试手写时如果用 Java 或 C，别把交换三段式写错。

2.3 优化：提前结束的标记法

基础版冒泡排序有一个很明显的浪费：如果某一轮从头到尾都没有发生任何交换，说明数组已经有序了，后面的轮数完全没必要继续执行。加一个标志位就可以避免：

def bubble_sort_optimized(arr): n = len(arr) for i in range(n - 1): swapped = False for j in range(n - 1 - i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True if not swapped: break return arr

这就是我在实际写代码时更常用的版本。注意swapped必须在外层循环内部、内层循环开始前重置为False，每轮都需要重新判断这一轮是否有交换发生。放在外层循环外面会导致一个经典 bug：只要某一轮没有交换，后面就全部跳过了。我见过不止一个同学犯过这个错，排查时一定要先检查标志位的位置。

优化之后，冒泡排序的最好情况（数组本身就是有序的）时间复杂度可以降到 O(n)，因为第一轮扫描完整数组发现没有交换，直接退出。平均和最坏情况仍然是 O(n²)。这个优化在笔试中经常被问到，答得出来说明你真的理解了算法，而不是只会默写。

2.4 冒泡排序的复杂度推导与常见坑

冒泡排序的时间复杂度推导过程，恰好可以顺带复习一下等差数列求和的思路。最坏情况下数组完全逆序，第一轮比较 n-1 次，第二轮比较 n-2 次，最后一轮比较 1 次，总比较次数为 (n-1) + (n-2) + ... + 1 = n(n-1)/2。所以时间复杂度是 O(n²)，而且比较次数在最坏情况下达到了理论上的最大值。

常见坑我列一下，都是我实际遇到过的问题。

第一，内层循环边界写成range(n)，导致arr[j + 1]在 j 取到 n-1 时下标越界，程序直接报错。第二，比较符号写反，>写成<，排序结果变成降序，检查时很难一眼看出来。第三，交换逻辑里把arr[j]和arr[j + 1]的位置互换写错，导致排序结果完全错误。第四，优化版里swapped标志的位置错误，导致有序数组提前退出后，数组后半部分根本没有排序。

冒泡排序在数据量大时确实效率不高，十万个随机数的排序，冒泡要跑好几秒甚至更久，而内置排序函数几乎瞬间完成。这恰恰说明选择合适算法的重要性，也解释了为什么工程中几乎不会直接使用冒泡排序。但这不妨碍它作为教学工具的价值，把它的每一步都弄明白了，后面学别的排序会顺畅很多。

3. 选择排序：每轮确定一个最终位置

3.1 核心思想与生活化理解

选择排序的思路和冒泡完全不同。它的核心是：每一轮从未排序区间中找出最小值（或最大值），放到未排序区间的起始位置，这个位置从此固定下来。

生活化的例子就是整理扑克牌。手里有一堆乱序的牌，每次都从剩余牌堆中挑出最小的一张，放到最左边，然后继续在剩下的牌中挑最小的，放到第二张的位置，直到全部挑完。这个过程没有相邻交换，而是“先找到位置，再一次性放过去”，所以每一轮只需要做一次真正的交换。

对数组[5, 3, 8, 1, 9, 2]来说，第一轮扫描整个数组，找到最小值 1，把 1 和第一个位置的 5 交换，得到[1, 3, 8, 5, 9, 2]；第二轮从第二个位置开始扫描，找到剩余区间的最小值 2，交换到第二个位置，得到[1, 2, 8, 5, 9, 3]。每一轮都确定一个位置的最终元素，n-1 轮之后数组完全有序。

3.2 实现细节与代码解析

选择排序的标准实现如下：

def selection_sort(arr): n = len(arr) for i in range(n - 1): min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j if min_idx != i: arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr

和冒泡排序对比，这里的核心差异在于：内层循环做的事情是“记录最小值的下标”，而不是“立刻交换”。整个内层循环结束后，只执行一次交换，把最小值放到正确位置。

为什么要记录下标而不是在发现更小元素时立刻交换？因为立刻交换会导致数据被频繁移动，而先找到最小值下标，最后一次性交换，交换次数从 O(n²) 直接降到了 O(n)。这一点在“写操作代价高”的场景下非常宝贵，比如数据元素很大、交换成本高于比较成本时，选择排序的优势就能体现出来。

实现中还有一个容易被忽略的细节：if min_idx != i这个判断不是必须的，但加上它能避免“原本位置就是对的，却还是交换了一次”的无效操作。虽然对结果没有影响，但养成这种写代码的习惯，能减少不必要的动作。

3.3 为什么选择排序是不稳定的

前面说了选择排序不稳定，现在来解释为什么。关键在于“交换”这个动作，可能把相等元素的相对顺序打乱。

看一个具体例子，数组[5a, 3, 5b, 1]，其中 5a 和 5b 是两个值相等但来自不同记录的元素。第一轮扫描找到最小值 1，把 1 和第一个位置的 5a 交换，数组变成[1, 3, 5b, 5a]。注意，原本 5a 在 5b 前面，现在 5a 跑到了 5b 后面，相等元素的相对顺序被改变了，所以选择排序不稳定。

实际工程中如果严格要求稳定性，就要要么改用稳定的排序算法（比如插入排序、归并排序），要么在比较时引入额外关键字。我在做某些数据合并任务时就踩过这个坑：先用选择排序按部门排序，再按姓名排序，结果同部门内的人员顺序在第二次排序后被打乱。后来换成稳定的排序算法才解决了问题。

3.4 选择排序与冒泡排序的横向对比

同为 O(n²) 的排序算法，冒泡和选择经常被放在一起比较。

比较次数方面，两者都是 O(n²)，选择排序固定比较 n(n-1)/2 次，不随数据有序程度变化。交换次数方面，选择排序最多进行 n-1 次交换，而冒泡排序最坏情况下的交换次数接近 n(n-1)/2，差距悬殊。

所以从“数据移动成本”的角度看，选择排序明显优于冒泡。但选择排序有一个致命短板：它对数据的有序程度完全无感。无论数组是基本有序还是完全逆序，它都要老老实实扫描完所有剩余区间，最好情况和最坏情况一样慢。这一特性决定了它在实际工程中也很少见，更多是作为一种教学算法和某些特殊场景下的选型。

学习时我的建议是，把冒泡和选择放在一起对比着学。冒泡强调相邻交换、每轮把大值沉底或把大值浮顶；选择强调寻找极值、每轮确定一个位置的最终归属。两种思路代表了排序问题的两个不同切入点，理解了它们的差别，后面学快排和堆排时会觉得更顺。

4. 插入排序：维护局部有序的朴素智慧

4.1 核心思想与扑克牌类比

插入排序的核心思想，是把一个元素插入到已经有序的子数组中合适的位置，使这个子数组继续保持有序，然后不断扩大有序区间的范围。

最贴切的生活类比就是整理扑克牌。大多数人打扑克时会习惯性地把摸到的新牌插入到手牌中合适的位置：左手握着的牌从左到右是按大小排好的，摸到一张新牌，就把它插到比它大的牌前面、比它小的牌后面。这个动作重复若干次，整手牌就完全有序了。插入排序就是把这种习惯动作形式化。

具体到数组操作，从第二个元素开始，把它前面的所有元素视为“已经排好序的区间”，取出这个元素作为待插入的 key，然后从后往前依次与前面的元素比较，找到第一个比 key 小的位置，把它插到这个位置后面。

这里有一个关键动作需要注意：插入排序在比较过程中不是用“交换”实现的，而是“整体后移”。每比较一次，就把比 key 大的元素往右挪一位，给 key 腾出插入位置。这种数据移动方式比冒泡的交换效率更高，也是插入排序在特定场景下表现优秀的内在原因。

4.2 实现细节与代码解析

def insertion_sort(arr): n = len(arr) for i in range(1, n): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr

这段代码里有一个非常容易出错的地方：内层 while 循环中arr[j + 1] = arr[j]是向右移动元素，而不是交换。整个循环结束时，key 被放到arr[j + 1]的位置。

还有一个隐藏的坑是j >= 0这个条件。如果 key 是当前未排序区间中最小的元素，while 循环会一直执行到 j 变成 -1，此时插入位置是数组的最前面 arr[0]。如果没有j >= 0这个保护，代码会尝试访问arr[-1]，在 Python 中不会报错但会错误地访问到最后一个元素，在其他语言中则会直接越界崩溃。这个问题我印象很深，因为报错方式在各语言中完全不同，排查起来很迷惑。

再一个常见错误是提前保存 key 这一步被省略。有人直接写成arr[i]在循环里作为基准值，然后arr[j + 1] = arr[j]把原来的arr[i]覆盖掉了，导致待插入的值丢失。正确做法必须是先把arr[i]保存在 key 中，因为它可能在移动过程中被覆盖。

4.3 为什么插入排序对“近乎有序”的数据特别快

插入排序最值得称道的一点，就是它在数据近乎有序的情况下效率极高。最好情况是数组已经完全有序，此时每个元素只要比较一次就找到位置，不用移动任何数据，总比较次数是 n-1，时间复杂度是 O(n)。

这个特性让插入排序在很多现实场景中非常有价值。实际业务数据往往不是完全随机的，很多情况下只是个别元素的位置不对，整体已经接近有序。比如一个按时间排序的列表，只有几条新数据插进来打乱了顺序；比如数据库里的索引页在做局部调整。这些场景下，插入排序的性能远超平均情况下的 O(n²) 表现。

更实际的应用是混合排序。现代很多编程语言的内置排序算法（比如某些语言标准库中的混合排序策略），在处理大规模数据时用快速排序或归并排序的思路，但当递归切分到很小的子数组时，会改用插入排序来完成收尾。原因很简单：对于小规模数据，递归和分治的固定开销反而超过了 O(n²) 算法的实际耗时，而插入排序实现简单、常数项极小，在小数据量下往往是最快的选择。所以千万别小看这个“基础算法”，它在现代排序库内部的地位远比表面看起来重要。

4.4 插入排序的稳定性与边界条件

插入排序是稳定的，这一点可以从它的移动方式看出来。当遇到相等元素时，while 循环的退出条件是arr[j] > key，也就是说只有当arr[j]严格大于 key 时才会执行移动；如果arr[j] == key，循环立刻停止，key 被插入到这个相等元素的前面。相等元素的相对顺序因此保持不变，所以不稳定问题不存在。

插入排序的时间复杂度总结为：最好 O(n)、平均 O(n²)、最坏 O(n²)、空间 O(1)、稳定。其中最坏情况是数组完全逆序，每个 key 都要移动到最前面，总移动次数达到最坏值。

学习插入排序时，我强烈建议配合图来理解“有序区间逐步扩展”的过程。初始时数组左边第一个元素天然有序，然后不断把后续元素插入到有序区间的合适位置。这个描述听起来抽象，但画两轮步骤图就非常直观了。理解了插入排序，后面学希尔排序时会觉得很轻松，因为希尔排序就是在插入排序的基础上增加了“间隔分组”的优化。

5. 二分查找：有序数组上的跳跃式搜索

5.1 前提条件与核心价值

二分查找和前面三种排序算法不同，它不是排序算法，而是建立在“有序数组”前提之上的查找算法。它的核心逻辑是：每次把搜索区间对半切开，根据中间元素与目标值的大小关系，直接排除掉一半不可能是答案的区间，从而大幅缩小搜索范围。

这个算法之所以经典，是因为它把线性查找的 O(n) 复杂度直接降到了 O(log n)。n 越大，优势越明显。一亿条有序数据用线性查找最坏要比较一亿次，用二分查找只需要大约 27 次，因为每次比较都把问题规模减半，2 的 27 次方已经超过一亿。

二分查找的前提条件是有序数组。这一点再怎么强调都不为过，因为这是我见过的最常见的误用场景：拿到一个无序数组就直接跑二分查找，结果时对时错，非常诡异。无序数组上二分查找的结果没有意义，正确做法是先排序，再二分。这也正是我把排序和二分查找放在一篇文章里的原因：排序是二分查找的前置条件，两者是配套使用的技能组合。

5.2 基础实现与循环不变式

最标准的二分查找实现如下：

def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1

这段代码里有一个非常重要的概念叫“循环不变式”，通俗说就是：每次循环开始前，目标值只可能存在于[left, right]这个闭区间内。只要维护好这个不变量，循环结束时left > right就意味着整个区间被排除干净，目标值确实不存在。

left和right的更新规则要重点理解。当arr[mid] < target时，mid 及其左边的所有元素都小于目标值，不可能包含答案，所以直接把搜索下界提高到mid + 1。同理，当arr[mid] > target时，直接把上界降到mid - 1。加一和减一这两个操作是二分查找不出死循环的关键，很多人写成left = mid或right = mid，结果区间永远不缩小，程序陷入死循环。

为什么退出条件用left <= right而不是left < right？因为搜索区间是闭区间，当left == right时，区间内仍然有一个元素需要检查。如果写成left < right，会漏掉这个单元素的情况，此时如果目标值恰好等于这个元素，就永远找不到。纠结这两个条件的人，我建议代入一个单元素数组实际跑一遍，立刻就会明白区别。

5.3 防溢出写法与 mid 计算

代码里mid = left + (right - left) // 2这种写法，初中生都能看明白等价于(left + right) // 2，为什么要多此一举？因为在某些语言和环境下，当left和right都很大时，两者之和可能超出整数类型的上限，产生溢出。而left + (right - left) // 2是先算差值再除以二，最大也不会超过right，从根本上避免了溢出问题。

这个写法在实际面试里是个加分项，见过不少候选人用(left + right) // 2写对了逻辑，但没考虑到极端大数组下的溢出风险。虽然很多现代语言会自动处理大整数，但这个意识仍然值得养成。

另外要注意整除符号的含义。Python 中// 2是向下取整的整除，得到的结果偏向 left 一侧。这本身没有问题，关键是整个算法的逻辑要与这个取整方向保持一致。如果换用向上取整的写法，那left和right的收缩逻辑也需要重新推敲，不要混用。

5.4 变体：查找第一个等于目标值的位置

实际业务中更常见的是二分查找的变体，不是找任意一个等于目标值的位置，而是找“第一个等于目标值的下标”或者“最后一个等于目标值的下标”。比如在一个有序考试成绩列表中，需要找出所有成绩等于 90 分的记录，那就必须定位到第一处和最后一处。

先找第一个等于 target 的位置：

def binary_search_left(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = left + (right - left) // 2 if arr[mid] >= target: right = mid - 1 else: left = mid + 1 if left < len(arr) and arr[left] == target: return left return -1

这个变体和基础版的核心差异在于：当arr[mid] == target时，不立即返回，而是继续把 right 往左收缩，依然在左侧查找是否还有相等元素。循环结束后，left 指向的位置就是第一个不小于 target 的元素，再验证它是否真的等于 target。

找最后一个等于 target 的位置的写法对称：

def binary_search_right(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = left + (right - left) // 2 if arr[mid] <= target: left = mid + 1 else: right = mid - 1 if right >= 0 and arr[right] == target: return right return -1

这两个变体我建议背下来，因为笔试中考的频率极高。背代码本身不可怕，可怕的是不理解为什么这样收缩边界。只要抓住循环不变式——“区间内始终包含所有可能的答案”，两个变体就不会写错。

6. 四种算法的横向对比与选型思路

6.1 复杂度特性速查表

把四种算法放到一张表里对比，复习时一眼就能抓住关键：

注意冒泡排序和插入排序的最好情况都是 O(n)，前提是带优化标志或数据本身有序。选择排序最特殊的一点是，效率完全不依赖数据初始状态，永远稳定在 O(n²)。二分查找单独看，空间复杂度 O(1)，但它要求预先排好序，而排序本身的成本要另外算进去。

这张表不只是用来背的。做题或者选型时，先看数据量级：n 很小（比如几百以内），O(n²) 算法完全够用；n 到十万以上，必须考虑 O(n log n) 甚至更优的算法；n 特别大但又有大量查询需求，先排序再二分查找往往是性价比最高的组合。

6.2 不同场景下的算法选型建议

按照实际经验，我给几个具体的选型方向。

第一，数据量很小（几百个元素以内）且不知道数据分布特征时，优先考虑插入排序。它实现简单，常数项小，对有序数据特别快，而且稳定。很多 O(n²) 算法在这种规模下反而可能跑赢常数项偏大的 O(n log n) 算法，因为数据规模还不足以让复杂度差距体现出来。

第二，数据本身近乎有序时，插入排序是绝对的首选。最好情况下的 O(n) 表现对“只有几个位置错了”的数据非常友好。

第三，数据元素很大、但比较代价较低时，选择排序值得考虑。因为它最多只做 n-1 次交换，数据移动总量最小，在写操作昂贵的场景下有实际价值。不过要注意它不稳定，需要稳定排序时直接排除。

第四，冒泡排序在工程选型中基本没有位置，它唯一的价值是教学。真正手写排序时，我不会在任何项目里使用冒泡排序，但我会要求自己能在 30 秒内无错写出它来，因为这对应聘者来说是最基本的底线。

第五，需要查找的场景，数据量小且查询不频繁时用线性查找就够了；数据量大或查询频繁时，一定先排序再二分查找。排序是一次性成本，重复查询可以无限次享受 O(log n) 的收益。

6.3 推荐的学习顺序与练习方法

站在一个过来人的角度，我推荐的学习顺序是：冒泡 → 选择 → 插入 → 二分查找，中间不要跳步。

冒泡帮助你建立双重循环和相邻比较的直觉，这是后面所有算法的基础。选择帮助你理解“记录下标、最后交换”这种间接操作的思维，也让你第一次意识到稳定性问题的存在。插入则让你体会到“数据移动”和“数据交换”的区别，并了解 O(n²) 算法在某些场景下并不慢。二分查找收尾时，你会把“有序”这个关键词和“高效查找”关联起来，四块拼图刚好合成一个完整的能力闭环。

练习方法上我的经验是：绝不背代码，而是先画图。用纸画一个 6 元素的数组，一步一步手动执行每种排序，把每轮交换、移动后的数组状态写下来。自己亲手画过两三轮之后，代码自然就能写出来了。写完后用随机数组、有序数组、逆序数组、含重复元素的数组分别测试。验证方式可以写一个断言：排序结果必须满足 arr[i] <= arr[i+1] 对每个 i 成立。这个习惯帮我抓出过大量边界问题。

7. 常见问题与排错实录

7.1 死循环问题：二分查找的边界失控

二分查找最常见的故障就是死循环。症状很典型：程序卡住不退出，或者 CPU 占用率飙升。原因几乎都出在left和right的更新上。

一种情况是把left = mid + 1写成left = mid。假设left和right相邻，比如 left=3、right=4，mid 计算出来是 3，arr[mid] < target时如果 left 更新为mid=3，区间从 [3,4] 变成 [3,4]，根本没有缩小，死循环立刻出现。另一种情况是退出的循环条件写错，写成while left < right，又恰好在单元素区间时需要查找，每次都能匹配到逻辑分支但永远不触发退出。排查时先打印每一次的 left、right、mid 三个值，立刻就能看出区间有没有在收缩。

7.2 下标越界问题：冒泡与插入的边界隐患

冒泡排序的越界多发生在内层循环。for j in range(n)时，最后一轮 j 取到 n-1，arr[j + 1]访问 arr[n] 直接越界。Python 会报 list index out of range，Java 和 C 会报数组越界异常。解法是内层循环的上限必须是n - 1 - i。

插入排序的越界则往往发生在另一种形式。while 循环里如果漏写了j >= 0，条件退化为arr[j] > key，当 j 变成 -1 时，Python 会访问到数组最后一个元素，不报错但逻辑彻底错误，Java 和 C 中则直接崩溃。这类问题的诡异之处在于：同样的逻辑在不同语言里表现完全不同，最容易让人摸不着头脑。排查方法是打印 j 的取值，看到负数就要立刻意识到边界缺失。

7.3 排序结果部分正确：交换与保存逻辑错误

排序结果“部分正确”比完全错误更隐蔽。可能出现的情况是数组前半段排好了，后半段还是乱序。常见原因有三个。

第一个是外层循环轮数不足。n 个元素需要 n-1 轮，写成 range(n-2) 就会少排最后一轮。第二个是内层循环范围不对。比如选择排序中range(i+1, n)写成range(i, n)，每轮可能选到已经排好的元素，导致排序不完整。第三个是插入排序中没有保存 key，移动过程中把原来的值覆盖掉了，插入的数据不是原来那个元素。

排查这类问题时，我用的最有效的方法是构造小数组逐步打印。5 个元素的数组，每轮循环结束后打印数组当前状态，对比自己在纸上推演的结果，很快就能定位是哪一步出了问题。

7.4 二分查找的经典 bug 速查表

把二分查找最容易出错的点整理成一张速查表，排查时对照着看：

这张表我建议收藏。每次写二分查找变体前先过一遍，能帮你躲开大部分雷区。

7.5 笔试与面试的常见追问

面试官在基础排序上喜欢追问的几个问题，我提前帮大家梳理一下。

第一个是“冒泡排序第 k 轮之后的状态”，考察是否真的理解每轮做什么。第二个是“这几种排序里哪些稳定，为什么”，回答时要用具体例子说明不稳定算法是如何破坏相对顺序的。第三个是“数据已经基本有序时哪个最快”，答案是插入排序，因为它能提前发现有序并减少移动。第四个是“你能把二分查找的循环不变式说清楚吗”，这是区分背代码和理解算法的试金石。第五个是“如何在一个有序数组中找到目标值出现的次数”，做法是先二分找到左边界，再二分找到右边界，两者相减加一即可。

这些问题都不难，但都是建立在深度理解上的。平时自己书写一遍、画一遍图、调试一遍，面试就能自然应答。

写在最后的一点个人经验

最后再分享一个我实际刷算法时养成的方法：每次学完一个算法，不要急着做下一道题，先用“输入—状态—输出”三步复盘。输入是哪个数组，每一步的中间状态是什么，最终输出是什么。把这个过程写在纸上，或者写成带打印的代码跑一遍，比单纯背诵代码记忆深刻得多。

还有一个屡试不爽的验证技巧：写一个专门用于测试的小脚本，生成随机数组、有序数组、逆序数组、含重复元素的数组这四类测试数据，每次写完排序算法都跑一遍断言。这个习惯我会一直保持下去，因为测试数据足够随机的时候，很多边界问题根本藏不住。基础算法值得认真对待，它们是整个计算机科学的地基，花在这上面的时间永远不会白费。