写排序这件事我前后折腾过好几轮。第一次学的时候觉得冒泡最简单快排背下来就行堆排序看两眼就跳过结果真正在笔试里手写快排边界写错导致死循环堆排序把建堆的起点算成了 n/2数组直接乱序。后来带别人刷题发现大家卡的地方出奇一致不是不懂思想而是不知道每一行代码为什么这么写。这篇就把冒泡、快排、堆排序这三兄弟放在一起拆从比较次数、内存占用、稳定性一直讲到下标计算和边界处理代码用 Java 写思路对 C、C、Python 一样通用。刚接触数据结构、正在准备笔试面试或者想把排序这块地基重新夯实一遍的人都能照着往下走。1. 三个排序先摆在一起比较次数、移动次数和内存账1.1 为什么初阶阶段反而要同时学这三个很多人学排序是顺着教材一页一页翻冒泡、选择、插入、希尔、归并、快排、堆排、基数一个个背过去。背完一圈脑子里剩下的是八个名字和一张复杂度表真要动手写还是从零开始想。我的建议正好相反初阶阶段别贪多把冒泡、快排、堆排序这三个吃透剩下的几个理解思想就够用了。原因很实在这三个恰好覆盖了三种完全不同的设计思路。冒泡是相邻比较、逐步把极值推到端点属于最朴素的交换类快排是选一个基准、把数组分成两半再递归属于分治类堆排序是用数组模拟完全二叉树、靠下标关系维护堆性质属于树形结构类。三种思路都摸过一遍再看选择排序会发现它就是冒泡的变种看归并会发现它和快排是分治的两种切法看希尔会发现它只是插入排序加了步长。基础打在这个位置后面学什么都快。另一个原因是这三个排序在面试和笔试里出现的频率极高。手写快排几乎是标配手写堆排序在中高级岗位里也不少见冒泡则常被拿来问你能优化到什么程度。这三个写不利索其他算法写得再花哨也容易被一句你手写个快排我看看打回原形。1.2 时间复杂度的账面和实际差在哪教科书上冒泡是 O(n²)快排平均 O(n log n)堆排 O(n log n)。账面看快排和堆排一个档次冒泡差一个量级。但实际跑起来同样的十万个随机整数快排往往比堆排快将近一倍冒泡慢到根本跑不完。这个差距不是常数因子能解释的得从比较次数背后的内存访问模式去看。快排每次划分都是在连续的内存上做顺序扫描a[i]、a[j]挨着访问CPU 缓存命中率高堆排的下标是2*i1、2*i2跳着走数组一大缓存就不断失效理论复杂度一样实际耗时差一截。冒泡更极端每轮都要从头扫到尾交换次数在逆序数组上达到 n(n-1)/2 次每次交换都是两次写内存实际开销比理论值还难看。提示复杂度表只能用来判断量级选型时还得看数据规模、内存限制和缓存的脾气。小数组上插入排序常常吊打快排就是这个道理。所以看复杂度不能只看大 O还要问三个问题最坏情况是什么样、平均情况靠什么假设、常数项大不大。快排的平均 O(n log n) 建立在每次划分比较均匀这个假设上一旦基准选得烂它就退化成 O(n²)堆排的最坏和平均都是 O(n log n)稳定性好得多代价是常数大。这个取舍在后面选型那一节还会展开。1.3 稳定性和原地性落到工程里意味着什么稳定性指的是相等元素在排序后是否保持原来的相对顺序。冒泡稳定快排和堆排不稳定。这个性质平时刷题感受不到真到业务代码里就很要命。比如一个订单列表先按时间排好序再按金额排一次如果用的排序不稳定同金额的订单时间顺序就乱了用户看到的列表会莫名其妙地跳动。原地性指的是排序过程需不需要额外的数组空间。冒泡和堆排都是 O(1) 额外空间快排递归栈平均 O(log n)、最坏 O(n)。在嵌入式或者内存吃紧的场景里快排的递归栈可能直接把栈撑爆这时候堆排的 O(1) 就是硬优势。维度冒泡排序快速排序堆排序平均时间O(n²)O(n log n)O(n log n)最坏时间O(n²)O(n²)O(n log n)额外空间O(1)O(log n) 栈O(1)稳定性稳定不稳定不稳定是否原地是是是对缓存友好度好好差典型用途教学、小数据通用排序主力内存受限、要求最坏可控这张表建议自己手画一遍。画的时候不要抄而是回想每个格子为什么是这个值快排最坏为什么是 O(n²)堆排最坏为什么还是 O(n log n)冒泡的稳定性从哪来。能自己讲清楚才算真记住。2. 冒泡排序淘汰得早但它把提前收工的思路讲透了2.1 一趟冒泡到底把什么送到了终点冒泡的核心动作只有一句从左到右相邻两个元素比较大的往后换。走完一趟整个数组里最大的那个一定被推到了最右边。第二趟走前 n-1 个把第二大的推到倒数第二。如此往复第 k 趟结束最后 k 个位置已经就位。这个每一趟确定一个最终位置的性质是理解冒泡的钥匙。它意味着内层循环的右边界可以不断收缩不需要每趟都扫到 n-1。很多人写冒泡时内层固定写成for (int j 0; j n - 1; j)能跑出正确结果但白白多做了一倍的比较。public static void bubbleSort(int[] a) { int n a.length; for (int end n - 1; end 0; end--) { boolean swapped false; for (int i 0; i end; i) { if (a[i] a[i 1]) { int t a[i]; a[i] a[i 1]; a[i 1] t; swapped true; } } if (!swapped) { break; } } }内层条件是i end而不是i n - 1保证a[i1]最远只取到下标 end不会越界。这个细节写错就是ArrayIndexOutOfBoundsException初学者十个里有八个踩过。2.2 标志位优化和最后一次交换位置优化上面代码里的swapped是最基础的优化某一趟从头到尾没发生任何交换说明数组已经有序直接跳出。这个优化对近乎有序的数组效果非常明显一个已经排好序的长度一万的数组普通冒泡要跑一亿次比较加了标志位只跑一万次。还能再进一步。swapped只告诉你有没有交换没告诉你交换发生在哪。如果某一趟最后一次交换发生在下标 5说明 5 之后的所有元素都已经有序了下一趟的右边界可以直接收缩到 5中间那一大段白扫的全省了。public static void bubbleSortPro(int[] a) { int end a.length - 1; while (end 0) { int lastSwap 0; for (int i 0; i end; i) { if (a[i] a[i 1]) { int t a[i]; a[i] a[i 1]; a[i 1] t; lastSwap i; } } end lastSwap; } }这个版本用lastSwap同时承担了是否发生交换和新边界在哪两个职责如果一趟下来一次交换都没有lastSwap保持初始值 0end变成 0循环自然结束。写法比双标志位更利落也是我认为冒泡排序唯一值得记的版本。提示冒泡排序在工程里几乎不会被使用但这两个优化思路特别值得带走。一个算法的提前退出条件往往藏在它的执行过程里能不能发现取决于你有没有盯着每一步在干什么看。2.3 手写冒泡时三个高频错处第一个错处是内层边界写死成 n-1。这会让你每次都把已经就位的尾部元素重新比较一遍虽然结果没错但优化全废。更要命的是如果配合lastSwap优化边界写死会让优化失效因为lastSwap永远停在比较过的最大下标附近。第二个错处是交换写成a[i] a[i1]; a[i1] a[i];。这是新手最经典的失误两行赋值执行完两个位置变成了同一个值数组里的数据凭空丢失。解决办法是老老实实引入临时变量或者用异或交换但异或交换在i j时会把自己清零肉眼看不出问题调试起来能耗掉半天。我现在的习惯就是一律用临时变量清晰、不容易错、性能差异可以忽略。第三个错处是对空数组和单元素数组没做保护。n 0时end -1循环条件end 0不成立直接跳过没问题n 1时同理。看起来安全但如果把循环写成for (int end n - 1; end 0; end--)单元素数组进去走一趟空循环问题不大空数组进去就会先访问a[0]导致越界。边界条件不是靠运气过的写的时候就要把 n0、n1 在脑子里跑一遍。3. 快速排序骨架只有十行坑全在划分和边界3.1 partition 的挖坑法与前后指针法逐行拆解快排的整体结构简单到可以用三行说清选一个基准把数组分成小于等于基准和大于等于基准两段然后对两段递归。真正的手艺全在怎么分这一件事上。常见的划分方式有三种Hoare 原始版本、挖坑法、前后指针法。我推荐先掌握挖坑法因为它的变量含义最直观出错时容易定位。private static int partition(int[] a, int left, int right) { int pivot a[left]; int i left; int j right; while (i j) { while (i j a[j] pivot) { j--; } a[i] a[j]; while (i j a[i] pivot) { i; } a[j] a[i]; } a[i] pivot; return i; }逐行看。pivot把a[left]的值存起来此时a[left]这个位置就空了可以放心被覆盖这是挖坑这个名字的由来。第一个内层循环从右往左找第一个严格小于基准的元素找到后填进左边的坑于是右边留下一个新坑。第二个内层循环从左往右找第一个严格大于基准的元素填进右边的坑。循环结束时i j这个位置就是基准的最终归宿把pivot填回去返回下标。这里有两个必须盯住的细节。内层循环的条件必须是i j否则在极端情况下j--会一路减到 -1数组越界比较符号必须是和如果写成和遇到和基准相等的元素就会停下虽然也能把数组分完但划分点会变得不可预测极端情况下直接死循环。还有一种更常见的写法叫前后指针法也叫 Lomuto 划分private static int partitionLomuto(int[] a, int left, int right) { int pivot a[right]; int small left - 1; for (int i left; i right; i) { if (a[i] pivot) { small; int t a[small]; a[small] a[i]; a[i] t; } } small; int t a[small]; a[small] a[right]; a[right] t; return small; }small始终指向已处理区间里最后一个小于等于基准的位置i负责扫描。扫完把基准换到small 1左边全是小的右边全是大的。这种写法逻辑更线性、更好记缺点是交换次数比挖坑法多遇到大量重复元素时划分也不够均匀。两种都值得会面试时用哪种都行关键是要能解释清楚每个变量的含义。3.2 递归出口、小区间切换插入排序快排的递归函数最容易出错的地方反而不是划分而是出口。public static void quickSort(int[] a, int left, int right) { if (left right) { return; } int p partition(a, left, right); quickSort(a, left, p - 1); quickSort(a, p 1, right); }出口写left right而不是left right。前者同时覆盖了空区间left right和单元素区间left right两种情况后者只覆盖单元素。如果写成当p 0时递归调用quickSort(a, 0, -1)left right不满足函数继续往下走partition里a[left]直接越界。这个 bug 我第一次写快排时遇到过报错信息指向 partition排查了半天才发现是出口的问题。另一个实用的优化是小区间切换插入排序。快排递归到区间长度很小比如 15 以内时递归调用的开销已经超过了排序本身的收益。插入排序在近乎有序的小数组上极快而且常数小。private static final int THRESHOLD 15; public static void quickSortOpt(int[] a, int left, int right) { if (right - left 1 THRESHOLD) { insertionSort(a, left, right); return; } int p partition(a, left, right); quickSortOpt(a, left, p - 1); quickSortOpt(a, p 1, right); } private static void insertionSort(int[] a, int left, int right) { for (int i left 1; i right; i) { int cur a[i]; int j i - 1; while (j left a[j] cur) { a[j 1] a[j]; j--; } a[j 1] cur; } }阈值取多少没有标准答案8 到 20 都有人用我在 Java 环境里实测 15 左右比较稳定。这个优化的收益在数据量大时才明显但它是理解算法不是纯理论、常数因子也重要的好例子。3.3 有序数组与全重复元素两种退化场景的处理固定取a[left]或a[right]作为基准有两个经典退化场景。第一种是数组本身已经有序或逆序。此时每次划分都只能分出一个元素递归深度变成 n时间复杂度退化到 O(n²)而且 n 稍大一点比如十万就会栈溢出。修复方式是随机化基准或者三数取中。private static void randomPivot(int[] a, int left, int right) { int r left (int) (Math.random() * (right - left 1)); int t a[left]; a[left] a[r]; a[r] t; }在partition开头调用一下把随机选中的元素换到left后面逻辑不变。这样无论输入长什么样划分的期望都是均匀的最坏情况出现的概率被压到极低。另一种做法是三数取中取left、mid、right三个位置的中间值作为基准对有序数组特别有效而且不引入随机性结果可复现适合需要确定性输出的场景。第二种是数组里大量重复元素。用挖坑法配上、的比较全相同的数组每次划分都只能切掉一个元素同样退化到 O(n²)。处理它的标准方案是三路划分把数组分成小于基准等于基准大于基准三段中间那段直接跳过不参与递归。public static void quickSort3Way(int[] a, int left, int right) { if (left right) { return; } int pivot a[left (int) (Math.random() * (right - left 1))]; int lt left; int i left; int gt right; while (i gt) { if (a[i] pivot) { swap(a, lt, i); } else if (a[i] pivot) { swap(a, i, gt--); } else { i; } } quickSort3Way(a, left, lt - 1); quickSort3Way(a, gt 1, right); }循环里三个分支lt左边是小于区gt右边是大于区中间是等于区。循环结束时等于区已经就位只需要递归两边。这个版本在处理大量重复成绩大量重复标签这类真实数据时优势巨大而且不会退化成 O(n²)。提示判断一份快排实现靠不靠谱拿三个用例去测就够了——完全有序、完全逆序、全部元素相同。三个里有一个跑得慢就说明基准选择或划分策略有问题。4. 堆排序把数组当下标游戏玩的完全二叉树4.1 父子下标关系与大顶堆的定义边界堆排序是三个里面唯一需要一点想象力的。数组本身是线性的但你可以把它看成一棵完全二叉树下标 0 是根下标 i 的左孩子是2i1右孩子是2i2父节点是(i-1)/2。这个映射不需要额外存储纯粹靠算术关系建立所以堆排序能做到 O(1) 额外空间。大顶堆的定义是每个节点的值都不小于它的两个孩子。注意是不小于孩子不是整棵树有序。堆只保证堆顶是整个数组的最大值其余元素之间没有顺序关系。很多人第一次学的时候以为堆排序用了一个有序结构其实不是堆的弱序性质恰恰是它能做到 O(n log n) 的原因——维护弱序比维护全序便宜得多。小顶堆反过来每个节点不大于孩子堆顶是最小值。升序排序用大顶堆降序用小顶堆。这个对应关系初学容易搞混我的记法是大顶堆把最大值顶到堆顶然后把它换到数组末尾末尾就是升序的最后一位所以大顶堆配升序。父子下标关系里最容易出错的边界是最后一个非叶子节点怎么算。设数组长度 n最后一个元素下标是n-1它的父节点是((n-1)-1)/2 (n-2)/2。所以建堆的起点是(n-2)/2往左一直到 0。很多人在这里写成n/2或者n/2-1在 n 是偶数时结果碰巧一样n 是奇数时就差了 1表现为大部分用例能过、个别用例结果错最难调。4.2 建堆为什么从 (n-2)/2 开始且是 O(n)先说为什么从最后一个非叶子节点开始。叶子节点没有孩子天然满足堆性质不需要调整。所以建堆只需要处理非叶子节点从最后一个非叶子的位置往前逐个执行下沉。顺序必须是从后往前因为下沉操作依赖孩子子树已经是堆这个前提从后往前处理时每个节点的子树都已经调好了。再说为什么建堆的复杂度是 O(n) 而不是 O(n log n)。这是个常被问到的点。粗算一下高度为 h 的节点大约有 n/2^(h1) 个每个节点下沉最多走 h 层总代价是 h 乘以节点数再求和。这个求和的结果是 n/2 × (1 2/2 3/4 4/8 ...)后面的级数收敛到常数 4所以整体是 O(n) 级别。换个角度理解更直观树里绝大多数节点都在最底层它们的下沉代价是 0 或 1只有根节点需要走满 log n 层但根节点只有一个。把节点数量和每次代价乘起来低层的海量节点贡献很小高层的少量节点贡献也不大总和被压在 n 这个量级。这个结论和直觉相反——很多人以为建堆是 O(n log n)其实是 O(n)堆排序整体的 O(n log n) 全部来自后面 n 次换堆顶下沉。4.3 siftDown 里的 size 参数是最容易写错的一行下沉函数是堆排序的核心。它的任务是把某个位置 i 的元素往下推直到满足父不小于子。private static void siftDown(int[] a, int i, int size) { while (true) { int left 2 * i 1; if (left size) { break; } int larger left; if (left 1 size a[left 1] a[left]) { larger left 1; } if (a[i] a[larger]) { break; } int t a[i]; a[i] a[larger]; a[larger] t; i larger; } }这段代码里size这个参数是最关键的。它表示当前堆的边界数组下标从 0 到 size-1 属于堆size 及之后已经排好序、不参与堆调整。为什么一定要传这个参数而不是直接用a.length因为在排序阶段每换走一个最大值堆的有效长度就减一size必须跟着变。如果贪省事用a.length已经排好序的末尾元素会被重新纳入堆的范围排序结果直接错乱。我见过的最典型的错误是把排序阶段写成这样// 错误示范 for (int end a.length - 1; end 0; end--) { swap(a, 0, end); siftDown(a, 0, a.length); // 用的是 a.length不是 end }表面上能跑出结果实际在某些输入下会把已经排好的最大值又换回堆里最终数组不是有序的。这种错误不会报异常只会结果错调试时永远想不到是这里。正确的写法是把end作为新的堆大小传进去。还有一个细节是left 1 size这个判断。它保证在只有左孩子、没有右孩子的时候不会去比较a[left1]。完全二叉树里最后几个节点确实可能只有左孩子这个判断漏掉就是越界。4.4 排序阶段交换、缩堆、再下沉建堆完成后a[0]是整个数组的最大值。排序阶段就是反复做三件事把堆顶和当前堆的最后一个元素交换堆大小减一对新堆顶执行下沉。交换把最大值放到了它最终该在的位置缩堆把它排除在堆外下沉让剩下的元素重新满足堆性质。public static void heapSort(int[] a) { int n a.length; for (int i (n - 2) / 2; i 0; i--) { siftDown(a, i, n); } for (int end n - 1; end 0; end--) { int t a[0]; a[0] a[end]; a[end] t; siftDown(a, 0, end); } }第一段建堆从(n-2)/2到 0一共处理了大约 n/2 个节点每个节点最多下沉 log n 层但总代价是 O(n)。第二段循环 n-1 次每次交换是 O(1)下沉是 O(log n)合计 O(n log n)。end 0这个条件意味着最后一个元素不用处理因为只剩一个元素时它必然有序。如果写成end 0数组只剩一个元素时交换a[0]和a[0]虽然结果不变但多了一次无意义的操作还容易让人误以为逻辑有问题。另外n 等于 0 或 1 时第一段循环的起点(n-2)/2会得到负数循环条件i 0直接不成立安全跳过第二段同理。所以这段代码对空数组和单元素数组天然安全不需要额外判断——这是我最喜欢堆排序的一点边界处理特别省心。和快排比堆排序的常数明显大因为下沉过程中的下标计算是2*i1这种跳跃式访问缓存不友好。但它有一个别人比不了的优点最坏情况也是 O(n log n)而且不需要递归没有栈溢出的风险。在实时系统或者对延迟有硬性要求的地方这种可预测性比平均性能更重要。5. 用对数器把三个实现按在地上摩擦5.1 对数器的写法与常见无效验证代码写完就跑一组手写数据看到输出对了就收工这是最容易翻车的学习方式。手写的数据往往太善良长度是 5 或 10元素是 1 到 9 的小整数没有重复没有负数这种数据几乎不可能暴露边界问题。真正靠得住的验证方式是对数器随机生成大量数组用你自己的实现排一遍用语言内置的排序排一遍两两对比。public static void check() { for (int t 0; t 200000; t) { int n (int) (Math.random() * 60); int[] a new int[n]; for (int i 0; i n; i) { a[i] (int) (Math.random() * 100) - 50; } int[] expected a.clone(); int[] actual a.clone(); Arrays.sort(expected); quickSort(actual, 0, actual.length - 1); if (!Arrays.equals(expected, actual)) { System.out.println(失败 Arrays.toString(a)); return; } } System.out.println(全部通过); }这里面有几个设计要点。随机长度用Math.random() * 60而不是固定长度可以覆盖从空数组到较长数组的各种规模元素值用Math.random() * 100 - 50制造负数负数参与比较时符号容易出问题值得专门覆盖循环次数给到二十万次量足够大小概率的边界问题也能被撞出来。常见的无效验证有几种。一种是只跑一组固定数据意义有限。另一种是两个实现互相验证比如拿自己写的另一版快排去对拍两个都错的时候照样通过。最可靠的基准是语言内置排序那是无数人用过的成熟实现把它当作标准答案最省事。还有一种是只验证结果不验证异常如果中间抛了异常程序直接崩掉你以为通过了。所以在check外面套一层异常捕获、打印出问题的用例是必要的一步。5.2 小数组、全相同、逆序、含负数四类用例随机对拍能覆盖大部分情况但有几类数据出现的概率偏低需要单独构造。用例类型构造方式主要暴露的问题空数组与单元素长度 0、1递归出口、越界全相同元素全部填同一个值快排退化、划分点失衡严格逆序从 n 递减到 1冒泡交换次数、快排基准选择严格有序从 1 递增到 n快排退化成 O(n²)、递归深度含负数与重复正负混合、大量重复比较符方向、稳定性两元素长度 2交换逻辑、循环边界全相同元素这个用例尤其值得单独跑。前面说过挖坑法在所有元素相同时会退化成每次只切掉一个元素n 大一点就会明显变慢甚至在递归深的地方栈溢出。用长度一万的全相同数组测一下如果耗时明显超过预期就说明划分策略需要改成三路。严格有序和严格逆序这两类测的其实是基准选择。用a[left]当基准的快排在这两种输入上表现最差长度五万就可能栈溢出。测试时把数组长度拉到五万、十万观察是否抛StackOverflowError比在小数据上看耗时更灵敏。5.3 实测耗时对比与结论在同一台机器上用 Java 对三个实现跑一组对比数据规模分别取 10 万随机整数结果大致是这个量级数据规模冒泡快排随机基准小区间优化堆排1000 随机约 3 ms约 0.3 ms约 0.5 ms10000 随机约 180 ms约 1.5 ms约 3 ms100000 随机跑不完量级在秒以上约 18 ms约 35 ms100000 有序同上约 15 ms随机基准生效约 30 ms具体数字会随硬件和 JVM 状态浮动但量级关系稳定冒泡在千级就开始吃力万级以上基本没有实用价值快排和堆排都在毫秒级快排普遍快 1.5 到 2 倍。快排的优势主要来自缓存友好堆排的劣势也主要来自缓存不友好跟理论复杂度无关。还有一点值得注意如果快排不加随机化有序数组上的耗时会直接爆掉十万规模可能跑出几秒甚至栈溢出而堆排依然稳定在三十毫秒左右。这个对比特别能说明最坏情况保证的价值——不是所有场景都在乎平均性能有些场景只在乎不能突然变慢。提示做性能对比时一定要先预热 JVM让同一份代码先跑几轮再记录时间。不预热的话第一轮包含了类加载和 JIT 编译开销数据会非常难看容易得出错误结论。6. 选型建议业务代码里到底该写哪个6.1 三张表说清使用场景脱离场景谈哪个排序好没有意义我把常见场景和推荐方案整理成下面这张表场景推荐方案理由教学演示、理解交换思想冒泡带 lastSwap 优化逻辑最直观优化点清晰通用内存排序、数据量大快排随机基准三路小区间优化平均最快缓存友好内存紧张、不允许递归堆排O(1) 额外空间无栈溢出要求最坏情况可控堆排最坏也是 O(n log n)数据几乎有序、规模小插入排序近乎 O(n)常数极小要求稳定排序归并排序快排和堆排都不稳定只求前 K 大小顶堆不是完整堆排序只需维护 K 个元素的堆最后一行值得多说一句。求数组里最大的 K 个数这类问题很多人第一反应是排序后取前 K 个复杂度 O(n log n)用大小为 K 的小顶堆复杂度降到 O(n log K)K 远小于 n 时优势明显。这种情况下堆的价值不在于排序而在于维护一个局部有序结构思路比堆排序本身更值得掌握。6.2 语言内置排序为什么不用这三个有人会问既然快排这么好为什么 Java 的Arrays.sort对基本类型不用纯快排答案是双轴快排加多种策略的混合。它对小数组切插入排序对大数组用两个基准把数组切成三段遇到划分不均时还会切换成堆排序兜底。这个设计的目的很明确既要快排的平均性能又要避免它在最坏情况下的失控。C 的std::sort思路类似用的是内省排序深度超过阈值就切堆排序。这个事实说明一件事工业级排序从来不是单一算法而是多个算法的组合。每种算法都有自己的甜区组合起来才能在各种输入下都表现稳定。理解这一点比死记某个算法的最优复杂度有用得多。你在业务代码里直接调内置排序就行不需要自己造轮子但在需要理解为什么这么设计的场合冒泡、快排、堆排这三个足够撑起整个讨论。我自己在这些年写排序相关的代码踩得最狠的两个坑都在堆排序一个是建堆起点写成n/2另一个是siftDown里把size写成a.length。前者在奇数长度数组上错后者在排序后期错两个都不报异常只是结果不对。后来养成的习惯是写完任何排序实现先把长度 0、1、2 的数组各跑一遍再跑全相同和逆序最后上对数器。这套流程走下来边界问题基本无所遁形比盯着代码反复看有效得多。