冒泡、选择、插入、快速排序全解析：原理、复杂度与工程实践

开始正文排序算法是数据结构与算法里绕不开的基础功冒泡、选择、插入、快速这四种更是面试笔试里出场率最高的四个面孔。很多人背了代码、过了面试真到项目里要用时却犯了难到底该用哪个为什么快速排序平均很快最坏情况却可能跑出 O(n²)插入排序明明复杂度更高为什么很多工程框架里还是离不开它这篇文章就围绕这四个经典排序从原理到代码、从复杂度到工程实践完整拆一遍。不管你是刚学算法的学生还是准备面试的求职者又或是入职多年想回头夯实基础的开发者这篇都能让你看完直接上手写代码也明白每行代码背后的取舍逻辑。1. 排序四兄弟先搞清楚每家“性格”再上手1.1 四种排序的直观印象先把这四种排序在脑海里过一遍画面。冒泡排序就像碳酸饮料里的气泡从底部往上冒每一轮结束最大的元素就“浮”到了它该待的位置选择排序像是一个挑剔的买手每一轮从剩余待排序区里挑出最小/最大的那个放到最终位置插入排序像打扑克时整理手牌每摸一张新牌就插到手里已排好序的序列中正确的位置上快速排序则像拆一堆文件先从中间挑一个“主元”pivot把小于它的扔到左边、大于它的扔到右边然后左右两堆各自递归接着拆。这四种排序虽然目标相同但思想路线完全不同。冒泡和选择是典型的“暴力轮询”时间复杂度稳定在 O(n²)插入排序即使同样是 O(n²) 最坏复杂度但对近乎有序的数据有惊人的适应力实际跑起来经常比理论预期快得多快速排序则是分治思想的代表作平均时间复杂度 O(n log n)在多数场景下是通用排序里的首选。1.2 为什么这四个排序值得反复琢磨很多同学会问真实项目里我直接用语言内置的排序不就行了比如 Java 的Arrays.sort()、Python 的sorted()、C 的std::sort()谁会手写排序这话没错但理解这四个排序的意义根本不在于重复造轮子而在于搞清楚三个层面的问题。第一是复杂度意识。如果你手里负责的是一个数据量很大的接口排序逻辑由底层函数库代劳你至少得知道内置排序什么时候会退化、什么时候表现优异才能写出符合预期的代码。第二是稳定性与内存的权衡。有些排序是原地排序比如快速排序、选择排序有些是稳定的比如冒泡、插入稳定性在按多字段排序时会直接影响结果正确性这是内置排序封装好的黑盒里你未必注意到的细节。第三是学习分治、递归、双指针、循环不变量这些基础编程思想的载体。这四个排序刚好覆盖了从“姥姥式逐个对比”到“分而治之”的完整思维梯度吃透它们后面学归并、堆排序、计数排序、桶排序都会顺很多。我个人的看法是这四个排序就像是算法世界里的“四则运算”虽然简单但任何复杂算法都离不开这种底层逻辑。基础打不牢后面学红黑树、跳表、B树这种高级数据结构时很容易栽跟头。2. 冒泡与选择把最简单直观的两兄弟讲透2.1 冒泡排序的原理与 Java 实现冒泡排序的思路一句话就能说清从头开始依次比较相邻两个元素如果前一个比后一个大就交换它们。一趟下来最大元素就会像气泡一样移动到数组末尾下一趟再从头部开始把次大的移动到倒数第二个位置依次类推。n 个元素的数组外层要跑 n-1 趟内层每趟比较的次数逐渐减少因为尾部已经排好的元素不需要再参与比较。写成 Java 代码是这样的public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; // 外层循环控制趟数最后一趟只剩一个元素不需要比较 for (int i 0; i n - 1; i) { // 内层循环每趟从头比较到 n-1-i因为末尾 i 个元素已经就位 for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { // 交换相邻元素 int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } }这里有几个值得注意的细节。内层循环的边界n-1-i是冒泡排序代码里最容易写错的地方。如果写成n-1虽然结果不会错但每一趟都会把已经排好的尾部元素再比较一遍白白浪费不少时间。另外交换操作里用临时变量是最稳妥的做法有些人会写异或交换的“炫技”版本但那在数组元素相同或涉及自身交换时容易出潜在问题不如老老实实用临时变量。冒泡排序还可以加一个经典优化如果某一趟完整走下来没有发生任何交换说明整个序列已经有序就可以提前终止。这个优化在数据本身就接近有序的场景下效果极其显著能把最好情况的时间复杂度降到 O(n)。代码如下public static void bubbleSortOptimized(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]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; swapped true; } } if (!swapped) { break; } } }2.2 选择排序少做无谓交换的“省事派”选择排序的思想和冒泡同样直接每一轮从剩余未排序区域里找到最小值把它放到该放的位置。比如第一轮从整个数组里挑出最小元素放在下标 0 的位置第二轮从 1 到 n-1 里挑出最小元素放在下标 1 的位置以此类推。它和冒泡最核心的区别是冒泡每发现一次逆序就交换一次而选择排序每一轮只交换一次——记录下最小值的下标等这一轮扫描全部结束后再交换一次。Java 实现如下public static void selectionSort(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; for (int i 0; i n - 1; i) { int minIndex i; for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } if (minIndex ! i) { int temp arr[i]; arr[i] arr[minIndex]; arr[minIndex] temp; } } }选择排序最大的优点是对写操作交换特别友好。它的交换次数固定是 n-1 次而冒泡的交换次数在最坏情况下是 n(n-1)/2 次。在对写入成本很敏感的场景比如写 flash 存储、机械硬盘等有寿命限制的设备选择排序比冒泡有压倒性优势。这也是在面试里被问到“哪种排序交换次数最少”时标准答案就是选择排序的原因。但选择排序有一个明显的短板它不稳定。举个例子现在有数组[5a, 3, 5b, 1]第一轮找到最小值 1和下标 0 的 5a 交换数组变成[1, 3, 5b, 5a]原来 5a 在前、5b 在后现在 5b 反而跑到前面去了。如果排序的是对象数组按某个字段排序时其他字段的先后顺序被打乱这在某些业务场景下是不可接受的。所以选择排序在工程里一般用得不多更多是作为算法入门的教学案例。2.3 冒泡与选择的复杂度对比和实践建议两种排序的时间复杂度都是 O(n²)空间复杂度都是 O(1)原地排序这点很多新手容易混淆。区别在于最好情况优化过的冒泡在数据有序时是 O(n)选择排序即使数据完全有序依然要每一个位置都扫描一轮找到最小值所以最好情况也是 O(n²)没有提前终止的能力。在现代 CPU 上冒泡排序通常跑得比选择排序还要慢一点原因在于冒泡做了大量无谓的交换操作而交换涉及读写内存是比比较更昂贵的操作。而选择排序虽然也慢但它的比较次数是固定的交换次数少实际耗时往往优于冒泡。如果你只是练手、写教学代码两个都可以如果在超大数据量下真的被要求手写一个不依赖库的 O(n²) 排序二选一我建议用选择排序它写起来更短也不容易在边界上出错。3. 插入排序被严重低估的实战强者3.1 插入排序的“打牌式”原理插入排序的思路借鉴的是大多数人整理手牌的直觉你左手已经拿了一手排好序的牌右手摸一张新牌把它从左往右或从右往左找到合适位置插进去后面的牌顺势往后挪。在数组里就是把数组从逻辑上分成两部分左边是已排序区初始只有第一个元素右边是待排序区。每次从待排序区取第一个元素与左边已排序区从右往左逐个比较找到它该插入的位置同时把大于它的元素统一向右挪一位。Java 代码如下public static void insertionSort(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; for (int i 1; i n; i) { int key arr[i]; // 记住当前要插入的元素 int j i - 1; // 从已排序区从右往左找位置并同时后移元素 while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; // 插入到正确位置 } }这段代码的核心逻辑在于while循环里同时完成两件事比较和移动。key被提前保存是为了在向后移动元素时不会丢失当前待插入元素的值。很多新手写成arr[j1] arr[j]后找不到key是从哪来的就是没理解这一步为什么要提前备份。3.2 插入排序的“逆袭”场景插入排序理论最坏复杂度是 O(n²)但它有两个堪称“逆袭”的特质。第一是对近乎有序的数据极度敏感。如果数据大致已经排好只是个别元素错位插入排序每轮移动次数会大幅减少最好的情况完全有序只需要 O(n) 时间——每一轮只需比较一次发现arr[j] key就立即停下整个过程就是一层 for 循环的扫描。第二是它是稳定排序相同元素的相对顺序不会改变。基于这两个特质插入排序在工程界有一个非常经典的应用场景作为高级排序算法的“收尾工具”。比如 Java 的Arrays.sort()在排序对象数组时底层采用 ComparableTimSort 排序当递归拆分后的子数组长度小于某个阈值约 32 或 64时就会改用插入排序来完成最后的小区间排序。再比如 Android 的Collections.sort()底层实现里也能看到插入排序的影子。为什么因为对于很小的数组比如 10 个元素以内递归带来的方法调用开销、分治带来的逻辑复杂度反而比直接把 10 个元素用插入排序理清楚更耗时。这就是典型的“复杂度高不一定慢常数小能救命”的例子也解释了为什么 O(n²) 的排序算法在真实工程里依然有一席之地。3.3 插入排序的一个小优化折半插入插入排序在已排序区找插入位置时用的是线性扫描。既然已排序区是严格递增的那完全可以用二分查找快速定位插入位置再把元素批量后移这种优化叫“折半插入排序”。它能减少比较的次数但注意移动元素的次数依然不变所以最坏时间复杂度仍然是 O(n²)。好处是常熟变小效率有一定提升代价是代码复杂度略高。如果你面试时被问到“如何优化插入排序”能说出这一点会加分不少。C 里的实现和 Java 大同小异区别主要是“数组”可以是std::vector或者原生指针数组核心循环逻辑完全一致void insertionSort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }我建议初学者把这份代码多默写几遍因为插入排序是写归并排序和快速排序时底层常用的小数组处理手段对它足够熟练能让你后面写工程代码顺畅很多。4. 快速排序分治思想的巅峰之作4.1 快速排序的核心机制快速排序是现代计算机科学里最有影响力的排序算法之一。它的核心思想就四个字分而治之。具体步骤是从待排序序列中选一个元素作为“主元”pivot通过一趟扫描把数组分成两个部分左边所有元素都小于 pivot右边所有元素都大于 pivot等于 pivot 的可以放任意一边然后对左右两部分递归地重复这个过程。每一轮 partition 都让 pivot 落到了最终位置反复递归直到区间长度只剩 1 或 0。这里的关键是 partition 过程到底怎么实现。教科书里最经典的是“Lomuto partition”和“Hoare partition”两种。Lomuto 实现起来更简单适合初学者理解Hoare 效率更高交换次数更少但边界条件更容易写错。我先展示 Lomuto 版本的 Java 实现public static void quickSort(int[] arr, int left, int right) { if (left right) { return; } int pivotIndex partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } private static int partition(int[] arr, int left, int right) { int pivot arr[right]; // 选最右元素作为 pivot int i left - 1; // i 指向小于 pivot 的区域的最后一个位置 for (int j left; j right; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } // 把 pivot 放到正确位置 swap(arr, i 1, right); return i 1; } private static void swap(int[] arr, int a, int b) { int temp arr[a]; arr[a] arr[b]; arr[b] temp; }Lomuto 的核心是维护两个区域[left, i]是已经确认小于 pivot 的区域[i1, j-1]是已经扫描过但大于或等于 pivot 的区域。每次发现arr[j] pivot就把i向右推进一格把该元素换到小于区域末尾。扫描结束后pivot和i1位置交换返回i1就是 pivot 的最终下标。4.2 快速排序的坑点pivot 的选择与最坏复杂度很多人背了快速排序代码却忽略了快速排序真正的核心在于 pivot 的选择。如果每次都选到当前区间的最小或最大元素比如数据本身已经有序每次都选最右端元素partition 之后一侧是空的另一侧是 n-1 个元素递归深度就会变成 n时间复杂度退化到 O(n²)。这就是快速排序“平均 O(n log n)、最坏 O(n²)”的由来。为了解决这个问题最常见的工程做法是“三数取中”median-of-three取当前区间的左端、右端、中点三个元素把它们的中间值作为 pivot。这样即便数据本身有序pivot 也不会总是极端值退化概率大幅降低。另一种做法是随机选 pivot每次 partition 前随机交换一个位置到最右端从统计学上让最坏情况发生概率低到可忽略。三种策略里我推荐工程代码里用“三数取中”它不需要额外导入随机数库性能也更稳定。C 的std::sort底层并不仅仅用快速排序而是结合了快速排序、堆排序和插入排序的“混合排序”当递归深度超出阈值时改用堆排序保证 O(n log n) 复杂度小区间用插入排序保证常数小。Java 的Arrays.sort()对基本类型数组用 DualPivotQuicksort双轴快速排序对对象数组用 TimSort。这些细节说明真实世界的排序算法从来不是单一结构而是多种算法的取长补短。4.3 三路快排与手写快速排序时的边界问题当数组里有大量重复元素时传统的二路 partition 可能会让相等的元素集中在某一边导致分区严重不平衡。这时可以用“三路快速排序”three-way quicksort来解决。三路的意思是 partition 后得到三个区小于 pivot、等于 pivot、大于 pivot。递归时只处理小于区和大于区等于区直接跳过这样重复元素越多、性能越好。经典的荷兰国旗问题Dutch national flag problem就是三路划分思想的代表。写快速排序时最让人头疼的永远是边界条件。我总结了自己写过无数遍后摸索出的几个要点递归终止条件left right必须判断否则可能出现无限递归或栈溢出。Lomuto partition 里i从left - 1开始交换前别忘了判断i ! j可以省掉一次不必要的 swap但这不是必须的。返回的 pivotIndex 必须在下一轮递归里从区间里剔除否则 pivot 会被反复处理导致死循环。对大数组递归时Java 默认栈空间可能不够数据量超过几万甚至几十万时手写递归快排可能溢栈。可以改成迭代版本用显式栈模拟递归来避免深递归也可以调大 JVM 的栈大小但更好的做法是混合排序——小数组用插入排序、深度过深用堆排序、正常用快排。下面给一个加了“三数取中”和插入排序优化、工程味十足的快速排序 Java 实现private static final int INSERTION_SORT_THRESHOLD 10; public static void quickSortOptimized(int[] arr, int left, int right) { if (right - left INSERTION_SORT_THRESHOLD) { // 小区间用插入排序减少递归开销 insertionSortRange(arr, left, right); return; } int pivotIndex medianOfThree(arr, left, right); int pivot arr[pivotIndex]; // 把 pivot 换到最右端方便用 Lomuto partition swap(arr, pivotIndex, right); int i left - 1; for (int j left; j right; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } int finalPivotIndex i 1; swap(arr, finalPivotIndex, right); quickSortOptimized(arr, left, finalPivotIndex - 1); quickSortOptimized(arr, finalPivotIndex 1, right); } private static int medianOfThree(int[] arr, int left, int right) { int mid left (right - left) / 2; if (arr[left] arr[mid]) swap(arr, left, mid); if (arr[left] arr[right]) swap(arr, left, right); if (arr[mid] arr[right]) swap(arr, mid, right); return mid; }这个版本综合了三种优化策略小数组走插入排序、三数取中规避最坏情况、Lomuto partition 简洁可靠。面试时你如果能写出这个层次面试官一般会认为你对排序有足够的工程理解而不是只会背书。5. 四兄弟横向对照复杂度、稳定性和场景选型5.1 一张表看清四兄弟的全貌排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性核心思想冒泡排序O(n²)O(n)优化后O(n²)O(1)稳定相邻交换大元素上浮选择排序O(n²)O(n²)O(n²)O(1)不稳定每轮选最小/最大放到位插入排序O(n²)O(n)O(n²)O(1)稳定已排序区逐个插入新元素快速排序O(n log n)O(n log n)O(n²)O(log n)递归栈不稳定分治 基于 pivot 划分这张表里最容易被忽略的是空间复杂度。很多人以为快速排序是原地排序空间就是 O(1)其实不然——快速排序递归调用时要消耗函数调用栈的空间。平均情况下递归深度是 O(log n)最坏情况下会达到 O(n)。所以如果你要处理海量数据且对内存极其敏感快速排序并不是最佳选择归并排序虽然空间 O(n)但稳定性更好。5.2 实战场景下的选型建议不同场景下到底用哪一家我给几条在项目里摸爬滚打得出的经验数据量很小几十个元素以内时插入排序往往吊打快速排序因为快排的递归调用开销远大于那几十次比较的开销。这就是为什么 Java 和很多语言的内置排序都会设置一个阈值小区间改用插入排序。如果你的业务里经常出现小数组排序可以手动调用一个手写的插入排序。数据量很大且分布随机时快速排序是通用首选。平均性能最优原地排序节省内存。但要注意生产环境的代码建议采用三数取中 混合策略不要直接用我上面那版最朴素的 Lomuto 递归实现。数据近乎有序时插入排序的实际表现最亮眼接近 O(n)。冒泡排序优化后也能达到 O(n)但它的常数比插入排序要大所以同样是有序数据实测插入排序更快。如果数据只是少量错位而不是完全有序插入排序依然有明显优势。对稳定性有要求且要保证最坏情况复杂度时用归并排序或 TimSort。比如按“时间”字段排序后还想保持同时间的元素按“ID”排列就必须用稳定排序。注意快速排序和选择排序在这里直接出局。5.3 关于“哪个排序最好”的追问说实话“哪个排序最好”在理论上没有标准答案因为要结合数据规模、数据分布、内存大小、稳定性需求、CPU 缓存特性来看。但如果你只是想掌握一个最通用的排序供面试时手写快速排序是首选如果面试官要求一个写起来最简单不容易错的冒泡或选择可以应急如果面试官考察“如何在近乎有序的数据里排序”插入排序是标准答案。这四种排序的考察频率背后其实是对编程基本功、复杂度分析和实际工程考量三个维度的综合测试。6. 实测手记常见问题与调试心得6.1 手写排序最易翻车的几个细节我见过太多人在手写排序时翻车排错位置高度集中在这几个点第一是边界下标。比如冒泡的内层循环写成j n - i而不是j n - 1 - i会导致访问arr[j1]时越界。第二是快速排序的 partition 里循环结束后忘了把 pivot 换到正确位置。第三是插入排序里忘了用临时变量保存待插入元素导致后移过程中覆盖了key的值。这几个问题几乎每个人都会犯一两次排查花的时间比写代码还多。给新手一个方法论写完代码后一定要用空数组、单元素数组、双元素数组、全部相等的数组、完全逆序的数组这五个测试用例各跑一遍。空数组和单元素数组能排查基础边界双元素数组能排查交换逻辑全部相等的数组能测试排序是否稳定和是否会越界完全逆序的数组能暴露最坏情况下的性能问题和递归深度。我用这套组合排查出过至少十几个肉眼看不出的隐性 bug。6.2 排查“排序结果不对”的标准流程如果排序结果不对先别急着打印整个数组用以下三个步骤定位检查数组长度是否为 0 或 1如果是任何排序都应该直接返回你的代码是否处理了这个分支检查交换函数。自己写 swap 时如果传入的是同一个下标会不会出问题如果数组元素是两个相同值交换会不会导致值丢失检查递归的区间划分。快速排序的递归区间是否把 pivot 正确排除quickSort(arr, left, pivotIndex - 1)和quickSort(arr, pivotIndex 1, right)中间没有包含 pivotIndex这一点非常关键。如果还排查不出来就在关键循环前打印区间边界和当前数组状态。我曾经调试一个快速排序的 bug最后发现是 Lomuto partition 里i的初始值应该是left - 1而不是left原因就是i本身代表“小于区域末尾下标”初始时小于区域为空下标应该比 left 小 1。这类问题不画几下流程很难看出端倪。6.3 从学习和面试角度的额外建议面试手写排序时不要直接闷头写先口头说清楚思路。比如写快速排序可以先说“我打算用 Lomuto partition选最右端元素做 pivot维护一个小于区域指针扫描并交换”。面试官通常更看重你能否把思路讲清楚其次才是代码能否一次性通过。写完代码后主动提出用测试用例验证而不是等面试官追问。学习排序的过程也别贪多一次吃透一个比囫囵吞枣四个要好。先从冒泡建立“交换”直觉再从选择建立“挑选最优”的思维再从插入理解“局部有序”的力量最后上升到快速排序的“分治”高度。这个梯度本身就是算法思维从低级到高级的缩影。我个人在项目中写排序相关代码最深的体会是不要迷信某一个算法工程里最终用的往往是混合方案。理解这几个基础排序不是为了替代系统库函数而是为了在系统库函数不满足需求时知道应该往哪个方向去改、去写、去优化。排序只是起点但把起点学扎实了后面很多问题的解决思路都会顺理成章。