排序算法大概是每个写程序的人绕不开的第一道坎。不管是大学的数据结构课还是面试手撕代码的固定环节插入排序、归并排序、快速排序这三个几乎就是标配。我见过不少同学能把代码背得滚瓜烂熟可一被问到为什么归并排序一定稳定快排最坏情况是怎么触发的大数据量下到底选哪个就卡壳了。这篇东西我想把这三种排序从实现到原理掰开揉碎讲一遍包括我在实际工程里踩过的坑以及后来总结出来的一些优化手法和验证技巧希望能帮到正在啃排序、准备面试突击或者工作中真的需要手写排序的人。1. 排序算法选型先搞清楚三个问题再动手1.1 为什么还要手写排序算法很多人的第一反应是语言自带排序直接调不就完了确实不管是哪种编程语言内置排序在绝大多数场景下都比手写更可靠、经过的测试也更充分。但有几个场景你绕不开手写一是面试现场面试官要看的就是你对基础算法的理解深度背题和真正理解一眼就能看出来追问两句就露馅二是排序对象不是普通数字比如按某个字段排序、按自定义规则比较理解底层原理才能正确设计比较器三是某些特定场景需要对排序做定制优化比如近乎有序的数据、大量重复元素通用内置排序未必是最优解手写反而能针对数据特征做文章。1.2 三种算法的定位完全不同插入排序是增量式思维一个一个把元素插到已经排好序的部分里适合小规模数据代码量最小思路最直白。归并排序是分治思想的代表先把数组拆到最小单元再两两合并稳定性和最坏情况复杂度都是它的优势代价是需要额外空间。快速排序同样是分治但它的核心是先按基准值把数据划分成大小两堆再分别递归处理平均性能极佳但存在退化风险。三者的思路差异很大理解它们等于理解了排序领域的三个基本流派插入、合并、划分。把这三个搞透再去看堆排序、希尔排序、桶排序之类的变体会发现都是换汤不换药。1.3 学习排序的正确姿势我个人的经验是不要死记代码而是抓住两个关键点一是每一步在干什么二是为什么这样做是对的。前一个保证你能把代码写出来后一个保证你能应对变体题和面试追问。我会建议初学者配合手动画递归过程、拿小数组模拟执行来理解比如拿一个长度 4 的数组把归并排序的每一层调用画出来比盯着代码看十遍都管用。下面每一部分我都会给出完整可运行的代码、复杂度推导过程还有容易出错的边界细节这些内容是我的实操总结不是教科书式的罗列。2. 插入排序像整理扑克牌一样直观2.1 核心思路与代码实现插入排序的思路一句话就能讲清楚把数组分成已排序和未排序两部分每次从未排序部分取一个元素在已排序部分从后往前找它的位置插进去。就像打牌时摸一张新牌把它插到手里已经排好序的牌堆里摸完 n-1 张牌整个数组就有序了。public static void insertionSort(int[] arr) { for (int i 1; i arr.length; 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; } }这里有两个容易纠结的边界。为什么循环从 i1 开始因为只有一个元素的子数组天然有序不需要处理。为什么 while 里条件写 arr[j] key 而不是 这关系到稳定性写成严格大于相等元素的相对位置不会改变排序是稳定的如果写成大于等于相等元素会被交换位置稳定性就丢了。这是个面试经常追问的细节也是很多人背代码时忽略的地方。2.2 复杂度推导与适用场景最好情况是数组已经有序内层 while 一次都不执行每一轮只做一次比较就结束总复杂度 O(n)。最坏情况是数组逆序第 i 轮需要移动 i 次总移动次数等于 12...(n-1)n(n-1)/2也就是 O(n²)。平均情况同样是 O(n²)严格推导会用到逆序对的概念结论记住即可。空间复杂度 O(1)因为只用了一个 key 变量做暂存属于原地稳定排序。适用场景非常明确数据量小通常几十到几百个元素或者数据基本有序。我实际测试过50 个元素以内的排序插入排序往往比快排还快因为它的常数因子极小没有递归调用开销也不需要额外空间。这也是为什么很多高性能排序实现会在递归到小规模时自动切换到插入排序而不是一条路走到黑。2.3 两个实用优化第一个优化是提前终止机制。内层循环在找到插入位置后立即停止这意味着数据越接近有序耗时越低。对近乎有序的数据插入排序的实际表现接近 O(n)这是它最大的价值。比如日志系统按时间戳排序后再插入少量新数据插入排序几乎是线性时间完成。第二个优化是二分插入排序用二分查找找插入位置把比较次数从 O(n) 降到 O(logn)但元素移动次数不变整体复杂度仍是 O(n²)。它适合比较开销大的场景比如排序对象是复杂对象比较一次很贵减少比较次数比减少移动次数更划算。代码改动很小把内层 while 换成二分查找定位位置再整体搬移元素即可但要注意二分查找的边界条件写错会引入新的 bug建议配合单元测试验证。3. 归并排序稳定的分治典范3.1 核心思路归并排序的核心是分而治之再合并。先把数组从中间一分为二递归地把左右两半分别排好序然后合并两个有序子数组。合并的过程很像两个有序的队伍合并成一个队伍谁小谁先出列两边都走完了任务就完成。这么做的依据是一个很朴素的观察合并两个有序数组只需要线性时间所以拆分的开销可以被合并的高效率覆盖。3.2 代码实现与边界说明public static void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } public static void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left; int j mid 1; int k 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } System.arraycopy(temp, 0, arr, left, temp.length); }关键点有几个。递归终止条件是 left right也就是子数组为空或只有一个元素时不再拆分。mid 的写法是 left (right - left) / 2而不是 (left right) / 2后者在数组很大时 leftright 可能溢出这是个非常经典的坑。合并时一定要写完整三个 while 循环主循环负责两边都比较后面两个循环负责把没走完的那一侧剩余元素全部拷过去少了任何一个循环都会丢元素排序结果必然错误。3.3 复杂度分析时间复杂度递归式为 T(n)2T(n/2)O(n)递归树每一层加起来是 O(n)一共 logn 层总复杂度 O(nlogn)。而且无论输入数据是什么状态归并排序都要走完完整的拆分和合并过程所以最好、最坏、平均都是 O(nlogn)这是它最让人放心的特性不存在退化问题。空间复杂度方面每次合并都需要一个和当前子数组等长的临时数组但同一时刻递归栈上每一层的临时数组可以复用所以总空间是 O(n)不是 O(nlogn)。很多新手会在 merge 里 new 一个数组频繁创建销毁会有不小的性能开销工程上通常是复用同一个临时数组靠下标范围控制使用区间。如果排序的是链表归并排序还有一个独特优势无需额外空间只用指针就能完成合并这也是归并排序常被用来归并链表的原因。3.4 稳定性和两个工程优化归并排序为什么稳定因为合并时当左右两个元素相等我们总是先取左侧的元素代码里就是 if (arr[i] arr[j]) 这个判断保证的。这里只要写成严格小于稳定性就丢了。这个细节在面试里经常被拿来考察建议自己动手改一行验证一下效果。第一个工程优化叫小数组兜底当递归子数组长度小于某个阈值常见取 10 到 20 时改用插入排序。这不影响 O(nlogn) 的整体复杂度但能显著减少递归调用次数和函数开销实际性能提升肉眼可见。第二个优化是减少不必要的拷贝比如控制合并方向省去最后一层回拷但代码复杂度会明显上升初学者可以先使用最清晰的版本等性能测试发现瓶颈再优化也不迟。我的经验是先正确再快别为了优化把代码写到自己都看不懂。4. 快速排序工程上的性能担当4.1 核心思路快排同样是分治但顺序和归并正好反过来。归并是先拆再合合并阶段才是重头戏快排是先划分再递归划分阶段就把基准值放到了最终位置。具体流程是选出一个基准值把数组划分成左边都小于等于基准、右边都大于等于基准基准落到它该在的位置然后递归排序左右两部分。划分是核心划分完基准就位了这一点和归并有着本质区别。4.2 两种典型分区实现先给最常见的单指针扫描法思路清晰适合教学和面试手写。public static void quickSort(int[] arr, int low, int high) { if (low high) { return; } int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } public static int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, high); return i 1; }分区的逻辑不复杂i 记录最后一个小于基准的元素的位置遍历 j 从 low 到 high-1发现小于基准的元素就把它和 i1 位置交换。遍历结束后把基准换到 i1 位置返回这个下标。这个实现直观、好写、不容易出错缺点是交换次数偏多而且基准固定在最后一个元素对某些输入性能不理想。另一种是双指针相向扫描法左指针找大于基准的右指针找小于基准的都找到了就交换直到两指针相遇最后把基准归位。public static int partitionTwoPointer(int[] arr, int low, int high) { int pivot arr[low]; int i low; int j high; while (i j) { while (i j arr[j] pivot) { j--; } while (i j arr[i] pivot) { i; } if (i j) { swap(arr, i, j); } } swap(arr, low, i); return i; }这种方式的交换次数平均更少对缓存也更友好工程实现大多用这种思路。但要注意内层两个 while 的边界条件比如 arr[j] pivot 里的等号不能随便去掉否则相等元素会被左右反复交换极端情况下会死循环。这个坑我踩过写完后最好拿一个全部相等的数组跑一遍验证。4.3 基准值选择快排最大的坑如果每次选最后一个元素当基准而输入恰好是逆序或接近逆序划分结果会严重失衡每次划分只砍掉一个元素递归深度变成 n时间复杂度退化成 O(n²)。这不是理论推演我见过线上真实数据触发过服务直接卡死。解决办法有三个层面。第一随机选基准把最坏情况变成概率事件概率低到可以忽略。第二三数取中从首、中、尾三个位置取中间值当基准能避免大部分有序输入导致的退化。第三对含有大量重复元素的数组用三路划分把等于基准的元素集中到中间避免重复元素反复参与划分。我自己写工程版快排时三数取中加随机扰动再叠加三路划分是标配实测对各种脏数据都稳得住。4.4 复杂度分析与实际性能期望时间复杂度 O(nlogn)划分均匀时递归式同样是 T(n)2T(n/2)O(n)。最坏 O(n²)但通过随机化基准实际触发的概率几乎为零。空间复杂度是递归栈深度平均 O(logn)最坏 O(n)。不稳定原因在于交换操作可能把相等元素的相对顺序打乱这个特性决定了它不能替代归并排序在稳定性要求高的场景中的位置。那为什么快排是实际性能之王两个原因。一是数据移动次数少划分让每个元素平均只被比较和交换有限的几次常数因子小二是局部性好操作的是紧密相邻的内存区域缓存命中率高。归并排序虽然复杂度保证 O(nlogn)但合并时频繁读写临时数组常数因子明显更大。所以对普通数组排序工程上快排几乎总是赢家这也是大多数语言内置排序以快排为蓝本的原因。5. 三张表看懂三种排序的选型逻辑5.1 核心参数对照算法最好情况平均情况最坏情况额外空间稳定性插入排序O(n)O(n²)O(n²)O(1)稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(nlogn)O(n²)O(logn)不稳定这张表基本涵盖了面试里九成的时间复杂度问题。特别注意快排的空间复杂度是递归栈深度不是 O(1)很多人栽在这里。归并的最坏情况和平均情况一样这是它的最大卖点代价是空间占用翻倍。5.2 稳定性到底什么时候重要很多初学者不理解稳定性有什么用觉得反正排完序结果一样。举两个实际例子。按价格排序商品列表时价格相同的商品希望保持原来的上架顺序稳定排序能做到这一点。按姓氏排序后再按名字排序时如果姓氏排序是稳定的那两次排序叠加就能得到先按名再按姓的复合排序效果如果第一次排序不稳定第二次排序会把第一次的成果打乱需要额外处理才能达到同样的效果。在数据库、表格式数据的多次排序场景中稳定性是刚需。5.3 实战选型建议数据量小或者基本有序直接插入排序简单可靠。数据量中等且需要稳定排序归并排序或者使用语言内置的稳定排序实现。数据量大、追求性能、不要求稳定快排。内存受限、数据量又大快排最合适因为它是原地的归并的 O(n) 额外空间在超大数组上可能直接内存不足。对象排序建议优先用内置的稳定混合排序它内部已经做了大量优化会在递归到小规模时自动切换到插入排序之类的策略自己从头手写很难超越它的综合表现。6. 实操中的坑与排查技巧6.1 递归深度和栈溢出归并和快排都是递归实现最坏情况下递归深度能到 n典型场景就是快排遇到逆序数据且基准选得不好。对十万级以上的数据默认栈大小很容易爆掉。解决方案有两个层面一是保证基准选择随机化或三数取中把递归深度控制在 logn 级别这是根治二是必要时改写为非递归版本用手工栈模拟递归虽然代码长一些但彻底摆脱栈大小限制。我自己的项目里就遇到过快排递归深度过大直接把服务打崩的案例排查了半天才发现是数据分布恰好命中了最坏情况最后换了随机基准才解决。6.2 边界条件写错的典型症状排序代码里最常见的 bug 集中在几个地方。插入排序内层循环忘记 j--导致死循环归并排序 merge 时少了尾部拷贝循环导致部分元素丢失快排递归调用写成了 quickSort(arr, low, pivotIndex) 而不是 pivotIndex - 1导致无限递归而且栈溢出。这些我都真实踩过排查方法很简单找一个长度 5 以内的数组人肉模拟一遍执行过程比对每一轮数组状态问题基本一眼就能看出来。别一上来就调试大数组那等于大海捞针。6.3 用随机测试验证正确性手写排序最怕的是大部分情况正常个别情况出错。正确做法是写一个测试器生成大量随机数组和语言内置排序的结果逐元素比对。测试必须覆盖几类特殊输入空数组、单元素、两个元素、全部相等、升序、降序、大量重复元素、随机大数组。我一般会跑十万组随机数据全部通过才敢说这个排序实现是可信的。这个习惯救过我很多次强烈建议养成每次改完算法代码都跑一遍防止改一处坏一处。6.4 性能测试的几个细节第一先预热再计时特别是带即时编译特性的语言环境第一次调用和第一百次调用的耗时天差地别直接用首次调用计时会得出完全错误的结论。第二测试数据要覆盖不同规模1 万、10 万、100 万、1000 万各来一轮观察增长曲线是否符合预期复杂度。第三最好用多组随机数据取平均值避免单次测试的偶然性。第四别忽略常数因子小数据量反直觉地用插入排序是常态基准测试结果会告诉你阈值到底在哪这个阈值在不同机器上不一样确定阈值最好的方法是跑自己的机器而不是抄网上的参数。我个人在实际操作中的体会是排序算法的高频考点其实不是那几十行代码而是代码背后的推演能力。能把复杂度推导讲清楚能把稳定性、空间开销、工程取舍说明白面试基本就稳了。最后再分享一个小建议写完任何排序算法第一件事不是跑大数据量测试而是先跑一遍全相等的数组和全逆序的数组这两个输入能暴露大多数隐藏的边界问题效率比盲目测一百组随机数据高得多。