排序算法大概是每个写程序的人绕不开的第一道坎。不管是大学的数据结构课，还是面试手撕代码的固定环节，插入排序、归并排序、快速排序这三个几乎就是标配。我见过不少同学能把代码背得滚瓜烂熟，可一被问到"为什么归并排序一定稳定""快排最坏情况是怎么触发的""大数据量下到底选哪个"就卡壳了。这篇东西我想把这三种排序从实现到原理掰开揉碎讲一遍，包括我在实际工程里踩过的坑，以及后来总结出来的一些优化手法和验证技巧，希望能帮到正在啃排序、准备面试突击，或者工作中真的需要手写排序的人。
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; } }这里有两个容易纠结的边界。为什么循环从 i=1 开始？因为只有一个元素的子数组天然有序，不需要处理。为什么 while 里条件写 arr[j] > key 而不是 >=？这关系到稳定性，写成严格大于，相等元素的相对位置不会改变，排序是稳定的；如果写成大于等于，相等元素会被交换位置，稳定性就丢了。这是个面试经常追问的细节，也是很多人背代码时忽略的地方。
2.2 复杂度推导与适用场景
最好情况是数组已经有序，内层 while 一次都不执行，每一轮只做一次比较就结束，总复杂度 O(n)。最坏情况是数组逆序，第 i 轮需要移动 i 次，总移动次数等于 1+2+...+(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，后者在数组很大时 left+right 可能溢出，这是个非常经典的坑。合并时一定要写完整三个 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，发现小于基准的元素就把它和 i+1 位置交换。遍历结束后，把基准换到 i+1 位置，返回这个下标。这个实现直观、好写、不容易出错，缺点是交换次数偏多，而且基准固定在最后一个元素，对某些输入性能不理想。
另一种是双指针相向扫描法，左指针找大于基准的，右指针找小于基准的，都找到了就交换，直到两指针相遇，最后把基准归位。
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 万各来一轮，观察增长曲线是否符合预期复杂度。第三，最好用多组随机数据取平均值，避免单次测试的偶然性。第四，别忽略常数因子，小数据量反直觉地用插入排序是常态，基准测试结果会告诉你阈值到底在哪，这个阈值在不同机器上不一样，确定阈值最好的方法是跑自己的机器而不是抄网上的参数。
我个人在实际操作中的体会是，排序算法的高频考点其实不是那几十行代码，而是代码背后的推演能力。能把复杂度推导讲清楚，能把稳定性、空间开销、工程取舍说明白，面试基本就稳了。最后再分享一个小建议：写完任何排序算法，第一件事不是跑大数据量测试，而是先跑一遍全相等的数组和全逆序的数组，这两个输入能暴露大多数隐藏的边界问题，效率比盲目测一百组随机数据高得多。
