排序算法这个东西说它是Java程序员的老朋友一点不夸张。你翻任何一本数据结构教材前几章一定有它你面任何一家像样的公司手撕排序几乎是保留节目你在真实项目里用Arrays.sort或者Collections.sort的时候底层跑的其实也是这些老朋友的各种杂交版本。我这几年带过几个新人也做过不少技术复盘发现一个很有意思的现象大多数人对十种排序算法的记忆停留在背结论——快排平均O(nlogn)、冒泡O(n²)、归并稳定——但你真让他写一个不带bug的三路快排或者解释清楚为什么JDK对基本类型和对象类型用了两套排序策略能说明白的不超过三成。这篇内容我打算把Java里常用的十种排序算法从头到尾捋一遍冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数。不只是贴代码还要讲清楚每个算法为什么这么设计、边界在哪、生产环境里到底该选谁。另外标题里提到了演示动画这块我也会单独拎出来讲因为排序算法的动画可视化其实是理解算法最直观的方式我会给你一个能跑起来的思路把每一次交换都变成一帧画面。适合谁看如果你是刚开始学数据结构的在校生这篇可以当你的入门加进阶材料如果你是在准备面试的Java后端这篇能帮你把八股文里的排序部分从背变成懂如果你已经工作几年但很少自己手写排序了当成一次系统性复习也不错。代码全部是可直接复制运行的Java版本我会标清楚每个算法的注意事项和常见坑。1. 先给这十种算法按脾气分个类上来就写代码是最容易劝退的做法因为十种算法混在一起讲你根本记不住谁是谁。我的习惯是先按一个大分界线把它们分成两拨比较类排序和非比较类排序。这条线一划开你会发现后面的所有特性——时间复杂度下限、能不能突破O(nlogn)、稳定性怎么来的——全都有了解释的锚点。1.1 比较类和非比较类中间隔着一道墙比较类排序顾名思义算法执行过程中判断两个元素大小关系靠的是比较这个动作。冒泡、选择、插入、希尔、归并、快速、堆这七种都属于比较类。它们有一个共同的理论天花板在只依赖比较的前提下任何排序算法的最好情况都不可能低于O(nlogn)。这个结论不是我随口说的是有决策树模型证明的——n个元素一共有n!种排列每次比较最多把可能性劈成两半所以至少需要log₂(n!)次比较用斯特林公式展开大约就是n·logn级别。所以你在任何地方看到某某比较排序平均复杂度O(n)基本可以直接判定是错的。非比较类排序就是另外一拨计数、桶、基数。它们不靠元素之间的比较而是利用元素本身的数值信息——比如值域范围、位数结构——来直接决定元素该放哪个位置。正因为绕开了比较这道坎它们才能做到线性时间O(nk)甚至O(n)。代价也很明显它们对数据有强假设计数排序要求值域不能太大基数排序要求元素是整数或者能拆成位桶排序则要求数据分布相对均匀。数据一旦不满足假设性能会断崖式下跌甚至比冒泡还难看。理解这条分界线的现实意义在于面试官问你能不能实现一个O(n)的通用排序正确答案是不能除非你放弃通用性对数据做额外假设。这句话说出来比背十个结论都显得专业。1.2 稳定性不是玄学它决定你的业务数据会不会错乱再说稳定性。所谓稳定是指排序前后值相等的元素相对顺序保持不变。很多人觉得这没啥用反正值都一样顺序变了能怎样我举个真实场景你就懂了。假设你有一批订单先按金额排好序了现在业务要求再按状态排一次希望同一状态内的订单仍然保持金额升序。如果你的排序算法不稳定那么第二次排序后同状态订单的金额顺序就被打乱了你还得再排一次白白多干一遍活。十种算法里稳定的有冒泡、插入、归并、计数、桶、基数。不稳定的有选择、希尔、快速、堆。这里特别要提醒一个常被忽略的点稳定性描述的是算法本身不是某一次运行结果。有人写了个快排跑一组特定数据发现没乱就说我这个快排是稳定的这属于典型的以偏概全。快排只要发生跨位置交换稳定性就没了。还有一个特别容易踩的坑Java里的Arrays.sort对基本类型数组用的是双轴快速排序不稳定对对象数组用的是TimSort稳定。同样是Java的排序API换个参数类型稳定性就变了。所以如果你业务上依赖稳定性一定要看清楚自己传进去的是int[]还是Integer[]或者干脆自己用归并。2. 动手之前把测试骨架搭起来我发现很多人学算法的方式是抄一段代码跑一下main方法输出看着对就完事。这种验证方式其实很不靠谱因为排序的边界情况太多了空数组、单元素、全相等、完全逆序、大量重复。不搭一个像样的测试骨架你根本不知道自己写的算法是不是只在标准输入下才正确。2.1 公共交换方法和数组打印先准备两个工具方法后面十个算法都要反复用到。第一个是交换第二个是校验和打印。这里有个小细节值得单独说很多人喜欢写arr[i] arr[i] arr[j] - (arr[j] arr[i])这种炫技式交换或者用异或交换看起来省了一个临时变量但实际上可读性极差而且在i j的时候异或交换会把自己清零是个隐藏炸弹。老老实实用临时变量编译器优化之后性能没差别。public final class SortUtil { // 交换两个下标的值老老实实用临时变量 public static void swap(int[] arr, int i, int j) { if (i j) return; // 防御式写法避免无意义操作 int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } // 顺序校验只要发现一处逆序就返回false public static boolean isSorted(int[] arr) { for (int i 1; i arr.length; i) { if (arr[i - 1] arr[i]) return false; } return true; } public static void print(int[] arr) { StringBuilder sb new StringBuilder([); for (int i 0; i arr.length; i) { sb.append(arr[i]); if (i ! arr.length - 1) sb.append(, ); } sb.append(]); System.out.println(sb); } }测试数据生成这块我建议至少准备四组随机数组、完全逆序数组、全相等数组、以及大量重复值的数组。前两组测正确性和常规性能后两组专治快排和堆排的极端退化。尤其是全相等数组朴素的两路快排遇到它会退化成O(n²)这个坑我在面试里见候选人踩过不止一次。2.2 计时基准怎么写才不算白跑写性能测试的时候有几个细节决定了你的数据有没有参考价值。第一必须做预热JVM有即时编译前几次运行走的是解释执行慢得离谱你得先跑个几百轮让热点代码编译完毕。第二每轮排序要用原始数据的副本否则第二轮开始你排的就是已经有序的数组测出来的是有序数组排序耗时不是你想测的东西。第三多轮取平均或者取中位数单次测波动太大。下面这个骨架可以直接用public static long bench(java.util.function.Consumerint[] sorter, int[] source, int warmup, int rounds) { int[] copy source.clone(); for (int i 0; i warmup; i) { sorter.accept(source.clone()); } long total 0; for (int i 0; i rounds; i) { copy source.clone(); long start System.nanoTime(); sorter.accept(copy); total System.nanoTime() - start; } return total / rounds; // 返回平均纳秒 }注意用System.nanoTime()而不是System.currentTimeMillis()后者精度只有毫秒级排几万个元素的耗时可能只显示个位数毫秒误差大到没有意义。这个骨架搭好之后后面每写一个算法都过一遍测试和基准你就能拿到一组自己实测出来的数据。我实测下来十万随机整数冒泡要好几秒快排基本在十毫秒上下差距是三个数量级。自己跑出来的数字比看表格印象深得多。3. 三种基础排序冒泡、选择、插入这三种算法经常被人瞧不起觉得太简单了学它干嘛。我的看法相反它们恰恰是理解排序思想的最佳入口而且插入排序在真实工程里被大量使用——JDK的TimSort在数据量小的时候就是切回插入排序的。所以别跳过把每个算法的退化条件和优化空间都摸清楚。3.1 冒泡排序加不加标志位是两个东西冒泡的核心思路是相邻两两比较大的往后挪每轮结束最大的元素就冒到了末尾。朴素版本的代码很直白但有个明显的浪费如果某一轮从头到尾一次交换都没发生说明整个数组已经有序了后面的轮次纯属白跑。加上一个布尔标志位最好情况复杂度就能从O(n²)降到O(n)。public static void bubbleSort(int[] arr) { for (int end arr.length - 1; end 0; end--) { boolean swapped false; for (int i 0; i end; i) { if (arr[i] arr[i 1]) { SortUtil.swap(arr, i, i 1); swapped true; } } if (!swapped) break; // 本轮无交换提前收工 } }还有个进阶优化叫记录最后一次交换位置因为如果某一轮里最后一次交换发生在下标k那k之后的元素其实已经有序了下一轮只需要扫到k就行。这个优化在近乎有序的数据上效果明显但代码复杂度也上去了实战里意义不大知道有这个思路即可。冒泡的稳定性是天然保证的因为只有arr[i] arr[i1]才交换相等时不动作相对顺序自然不变。这也是为什么初学者理解稳定性从冒泡入手最合适。3.2 选择排序交换最少但别指望它稳定选择排序每一轮从未排序区间里挑一个最小值和未排序区间的第一个位置交换。它的特点是交换次数最少最多n-1次所以如果元素交换的成本很高比如元素是大对象交换涉及大量内存拷贝选择排序反而有它的价值。public static void selectionSort(int[] arr) { for (int i 0; i arr.length - 1; i) { int minIdx i; for (int j i 1; j arr.length; j) { if (arr[j] arr[minIdx]) minIdx j; } if (minIdx ! i) SortUtil.swap(arr, i, minIdx); } }但它有个致命细节不稳定。我举个极简的例子数组[5, 5, 2]第一轮找到最小值2下标2和下标0的5交换数组变成[2, 5, 5]。原本在前的那个5跑到后面去了两个5的相对顺序被打乱。这就是不稳定性的来源——跨位置的交换把元素甩过了同值的兄弟。面试里如果被问选择排序为什么不稳定把[5, 5, 2]这个例子说出来比任何抽象解释都有效。3.3 插入排序小数组上的隐形冠军插入排序的思路是维护一个已排序区每次从右边取一个元素在已排序区里从后往前找位置插入找的同时把比它大的元素统统右移一格。这个边比较边搬移的写法比先找位置再搬移要紧凑是标准写法。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]; // 比key大的统统右移 j--; } arr[j 1] key; // 空出来的位置放key } }插入排序特别值得说的有两点。第一它在近乎有序的数据上效率极高。如果每个元素离它最终位置最多k步总复杂度就是O(nk)k很小时基本等价于线性。第二正因为这个特性它在工业级排序实现里频繁出现——JDK的TimSort对长度小于某个阈值的分段直接用插入排序双轴快排对小数组也做类似处理。提醒写插入排序时while条件里判断j 0一定要放在arr[j] key前面。如果写反了当j减到-1时先访问arr[-1]直接数组越界异常。这是新手最常翻的车。稳定性方面插入排序是稳定的因为条件是严格大于才移动相等的元素不会被搬走自然保持原顺序。4. 进阶四件套希尔、归并、快排、堆排这四种是真正在生产环境和面试里唱主角的。希尔是插入排序的升级版归并和快排是两种截然不同的分治思路堆排则把堆这种数据结构的价值发挥到极致。把它们的实现细节和适用场景搞透你的算法功底基本就稳了。4.1 希尔排序增量序列选错就白写希尔排序的想法很朴素既然插入排序在近乎有序的数组上快那我就先做一轮大跨度的插入排序让数组变得大致有序再逐步缩小跨度最后用一次普通的插入排序收尾。这个跨度就是增量。代码结构上它就是把插入排序里的j - 1换成了j - gap。public static void shellSort(int[] arr) { int n arr.length; int gap 1; while (gap n / 3) gap gap * 3 1; // Knuth序列1,4,13,40... while (gap 1) { for (int i gap; i n; i) { int key arr[i]; int j i - gap; while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } gap / 3; } }增量序列的选择直接决定性能。常见的几种n/2递减的最简单但效率一般Hibbard序列1, 3, 7, 15...最坏O(n^1.5)Knuth序列1, 4, 13, 40...实测表现不错也是我平时用的。用3h1递推的好处是能保证最后的gap一定是1而且增量之间互质性较好能减少同一元素被反复搬运的情况。希尔排序的时间复杂度分析比较麻烦取决于增量序列最坏大约在O(n^1.3)到O(n²)之间。它不稳定因为跨间隔的交换会打乱同值元素顺序。但它的优势是不需要额外空间这点比归并强。数据量在几万以内、内存又比较紧张的场景希尔是很好的折中选择。4.2 归并排序稳定、可预测代价是一份额外空间归并的核心是分治把数组对半切分别排好再合并两个有序数组。合并的过程需要一个临时数组来暂存结果。它的复杂度非常稳定任何输入都是O(nlogn)不存在最坏退化这是它相对快排最大的优势。public static void mergeSort(int[] arr) { if (arr.length 2) return; int[] tmp new int[arr.length]; // 只分配一次避免递归里反复new msort(arr, tmp, 0, arr.length - 1); } private static void msort(int[] arr, int[] tmp, int lo, int hi) { if (lo hi) return; int mid lo (hi - lo) / 2; // 防溢出写法 msort(arr, tmp, lo, mid); msort(arr, tmp, mid 1, hi); if (arr[mid] arr[mid 1]) return; // 已经有序就不用合并了 merge(arr, tmp, lo, mid, hi); } private static void merge(int[] arr, int[] tmp, int lo, int mid, int hi) { System.arraycopy(arr, lo, tmp, lo, hi - lo 1); int i lo, j mid 1; for (int k lo; k hi; k) { if (i mid) arr[k] tmp[j]; else if (j hi) arr[k] tmp[i]; else if (tmp[j] tmp[i]) arr[k] tmp[j]; else arr[k] tmp[i]; } }这里有两个细节特别值得记。第一int mid lo (hi - lo) / 2而不是(lo hi) / 2后者在lo和hi都很大时会整型溢出虽然Java数组长度限制让它不太可能触发但这是通用写法养成习惯没坏处。第二if (arr[mid] arr[mid 1]) return;这句优化在部分有序的情况下能省掉大量合并操作TimSort里也有类似逻辑。注意合并判断里我写的是tmp[j] tmp[i]严格小于才取右边这样左边相等元素会优先输出稳定性就保住了。如果把等号方向写反归并也会变得不稳定。另外归并的额外空间是O(n)递归深度是O(logn)如果数据规模特别大可以考虑自底向上的迭代版本避免递归栈压力。4.3 快速排序三路划分解决重复元素灾难快排是面试出现频率最高的排序算法没有之一。核心是选一个基准值把数组分成小于基准和大于基准两部分然后递归处理两边。但朴素的实现有几个坑有序数组上退化成O(n²)、大量重复元素时同样退化。所以真正能拿去面试的快排基本上都要加随机化和三路划分。三路划分把数组分成小于、等于、大于三段等于基准的元素直接用一趟扫描集中到中间后续递归只处理小于和大于两段。这个改动对重复元素多的数组效果立竿见影。public static void quickSort(int[] arr) { qsort(arr, 0, arr.length - 1); } private static void qsort(int[] arr, int lo, int hi) { if (lo hi) return; int pivot arr[lo (int) (Math.random() * (hi - lo 1))]; // 随机选基准 int lt lo, i lo, gt hi; while (i gt) { if (arr[i] pivot) SortUtil.swap(arr, lt, i); else if (arr[i] pivot) SortUtil.swap(arr, i, gt--); else i; } qsort(arr, lo, lt - 1); qsort(arr, gt 1, hi); }三路划分的循环逻辑需要理解清楚lt指向小于区的下一个空位gt指向大于区的下一个空位i是当前扫描指针。遇到小于基准的换到lt位置并两个指针都前进遇到大于基准的换到gt位置gt后退但i不动因为换过来的元素还没检查遇到等于基准的i直接前进。循环结束时[lo, lt-1]是小于区[lt, gt]是等于区[gt1, hi]是大于区等于区不用再处理。随机选基准这一步不能省。如果固定取第一个或最后一个元素面对完全有序数组每次划分都会极不平衡递归深度变成n时间复杂度退化到O(n²)还会导致栈溢出。随机化之后期望复杂度才是O(nlogn)。提示JDK里Arrays.sort(int[])用的是双轴快速排序DualPivotQuicksort比单轴三路快排再做了一层优化选两个基准把数组分成三段。这是工程上的极致优化手写面试版掌握三路划分就够了。4.4 堆排序原地且最坏情况也不塌堆排序利用的是完全二叉树的数组表示下标i的左孩子是2i1右孩子是2i2父节点是(i-1)/2。排序分两步先建大顶堆再反复把堆顶最大值换到数组末尾然后对剩余部分重新下调整堆。public static void heapSort(int[] arr) { int n arr.length; for (int i n / 2 - 1; i 0; i--) siftDown(arr, i, n); // 建堆 for (int end n - 1; end 0; end--) { SortUtil.swap(arr, 0, end); siftDown(arr, 0, end); } } private static void siftDown(int[] arr, int i, int size) { while (true) { int left 2 * i 1, right left 1, largest i; if (left size arr[left] arr[largest]) largest left; if (right size arr[right] arr[largest]) largest right; if (largest i) break; SortUtil.swap(arr, i, largest); i largest; } }建堆为什么从n/2 - 1开始因为下标大于等于n/2的节点都是叶子节点叶子本身就是一个合法的堆不需要调整。建堆的整体复杂度是O(n)而不是O(nlogn)这个结论很多人会算错可以这样理解越靠近底层的节点越多但它们的下沉深度越浅把节点数×下沉深度求和最终收敛到线性级别。堆排序最大的优势是原地排序、空间O(1)、最坏情况也是O(nlogn)不像快排有退化风险。它的劣势是缓存不友好访问模式跳跃实际跑起来通常比快排慢一截。另一个实际用途是求Top K问题——只维护一个大小为K的堆不用全排序这个场景堆排思路比快排更合适。堆排不稳定因为堆顶和末尾的交换是跨位置的。5. 三种线性时间排序计数、桶、基数接下来这三种跳出比较的框架用数值本身的信息换时间。它们的共同前提是数据得讲道理范围可控、分布均匀、或者能拆成位。用对了是降维打击用错了就是灾难。5.1 计数排序把值当数组下标计数排序的做法是先找出数组的最小值和最大值开一个长度为max - min 1的计数数组统计每个值出现的次数再按顺序把值填回去。它本质上是用值做下标直接定位。基础版本很简单但如果要求稳定还需要用前缀和把计数数组改造成每个值最后一个位置的下标。public static void countingSort(int[] arr) { if (arr.length 0) return; int min arr[0], max arr[0]; for (int v : arr) { if (v min) min v; if (v max) max v; } int[] count new int[max - min 1]; for (int v : arr) count[v - min]; int idx 0; for (int v 0; v count.length; v) { while (count[v]-- 0) arr[idx] v min; } }它的复杂度是O(n k)k是值域大小。这里的关键就在于k。如果数组是[1, 2, 100000000]这种k飙到一亿开这么大一个计数数组直接内存爆炸性能还不如快排。所以计数排序的适用场景非常明确值域范围不大或者值是年龄、分数、状态码这类有限枚举。注意带负数的时候用v - min做偏移别直接用值当下标否则负数下标会抛异常。这个偏移操作是计数排序处理有符号整数的标准手法。5.2 桶排序计数排序的推广版桶排序是把值域划分成若干个区间每个区间是一个桶把元素丢进对应的桶桶内各自排序通常用插入排序因为桶内元素少最后按桶的顺序拼接。它相当于把计数排序的一个值一个桶放宽成一段值一个桶适合值域大但分布均匀的数据。public static void bucketSort(int[] arr, int bucketCount) { if (arr.length 2) return; int min arr[0], max arr[0]; for (int v : arr) { if (v min) min v; if (v max) max v; } if (min max) return; java.util.Listjava.util.ListInteger buckets new java.util.ArrayList(); for (int i 0; i bucketCount; i) buckets.add(new java.util.ArrayList()); double step (double) (max - min 1) / bucketCount; for (int v : arr) { int idx (int) ((v - min) / step); if (idx bucketCount) idx bucketCount - 1; // 边界保护 buckets.get(idx).add(v); } int k 0; for (java.util.ListInteger bucket : buckets) { java.util.Collections.sort(bucket); // 桶内排序稳定 for (int v : bucket) arr[k] v; } }桶数量怎么选常见做法是sqrt(n)或者直接取n。桶太多每个桶就一两个元素管理开销反而大桶太少桶内元素多退化成普通排序。经验做法是让桶数量和元素数量同量级保证每个桶平均元素数是个小常数。桶排序的性能高度依赖数据分布。数据均匀分布时接近O(n)但如果有严重倾斜比如99%的元素挤在一个桶里那这个桶内部排序的复杂度就变成了主导整体性能崩塌。所以用桶排序之前一定要先看看数据的分布特征别拍脑袋上。5.3 基数排序一位一位地分拣基数排序是把整数按位拆开从最低位开始每一位做一次稳定的分配和收集重复到最高位做完整个数组就有序了。它依赖的核心前提是每一位的排序必须是稳定的通常用计数排序来实现每一位的分配。public static void radixSort(int[] arr) { if (arr.length 2) return; int max arr[0]; for (int v : arr) if (v max) max v; int[] tmp new int[arr.length]; for (int exp 1; max / exp 0; exp * 10) { int[] count new int[10]; for (int v : arr) count[(v / exp) % 10]; for (int i 1; i 10; i) count[i] count[i - 1]; for (int i arr.length - 1; i 0; i--) { int digit (arr[i] / exp) % 10; tmp[--count[digit]] arr[i]; } System.arraycopy(tmp, 0, arr, 0, arr.length); } }为什么要从后往前遍历放元素因为我们要保持稳定性。count数组在前缀和之后count[d]表示当前位小于等于d的元素总个数也就是数字d应该放置的最后一个位置。从后往前遍历原数组把元素放到--count[digit]的位置能保证在原数组中靠后的同位数元素放到更靠后的位置稳定性就保住了。基数排序的复杂度是O(d·(n k))d是最大数的位数k是进制十进制就是10。对32位整数来说d最多10用十进制所以实际复杂度非常接近线性。它也不擅长负数处理负数需要额外做偏移或者分正负两批处理这点用的时候要留意。6. 演示动画让每一次交换都被看见终于说到标题里的动画部分了。排序算法看得再多次代码不如看一次动态过程来得直观——你能亲眼看到快排的划分是怎么一步步把区间缩小的堆排是怎么反复把堆顶甩到末尾的。这里我讲两个层面的方案一个是有图形界面的Swing版本一个是纯控制台的降级版本。6.1 先把过程录下来帧模型的思路直接边排序边刷新界面是行不通的因为排序执行得太快一眨眼就跑完了你什么都看不见。所以正确的思路是先录制再回放。具体做法是在排序过程中每发生一次有意义的操作交换、赋值、比较就把当前数组的状态快照存进一个列表同时记录当前高亮的下标位置。排序执行完后我们拿到一个帧序列再用定时器一帧一帧地播放。import java.util.ArrayList; import java.util.List; public class FrameRecorder { public final Listint[] frames new ArrayList(); public final Listint[] highlights new ArrayList(); // 记录一帧数组快照 需要高亮的下标 public void record(int[] arr, int... highlightIdx) { frames.add(arr.clone()); // 必须clone否则引用会被后续修改 highlights.add(highlightIdx); } }这里最容易犯的错误是frames.add(arr)直接把引用存进去。数组是可变对象你后面每一次交换都会把之前存的快照一起改掉最后回放时你会看到所有帧长得一模一样。必须用clone()复制一份。这个坑我自己踩过调试了半天才发现是引用问题。6.2 用 Swing 把数组画成柱子有了帧数据画图就简单了。用一个JPanel重写paintComponent把数组的每个值画成一根竖直柱子高度按比例映射当前帧里被高亮的下标用另一种颜色画。然后用javax.swing.Timer每隔几十毫秒推进一帧调用repaint()触发重绘。import javax.swing.*; import java.awt.*; public class SortPanel extends JPanel { private final FrameRecorder rec; private int cursor 0; public SortPanel(FrameRecorder rec) { this.rec rec; Timer timer new Timer(30, e - { // 30ms一帧约33帧每秒 if (cursor rec.frames.size() - 1) { cursor; repaint(); } else { ((Timer) e.getSource()).stop(); } }); timer.start(); } Override protected void paintComponent(Graphics g) { super.paintComponent(g); int[] frame rec.frames.get(cursor); int[] hi rec.highlights.get(cursor); int w getWidth() / Math.max(1, frame.length); for (int i 0; i frame.length; i) { boolean active false; for (int h : hi) if (h i) active true; g.setColor(active ? Color.RED : new Color(70, 130, 180)); int h frame[i]; g.fillRect(i * w, getHeight() - h, Math.max(1, w - 2), h); } } }把面板塞进JFrame就能跑。想让它更好看可以把数组的值缩放到面板高度范围内加上坐标轴甚至同时显示当前是第几轮、比较了多少次。这些都属于锦上添花核心还是帧序列 定时重绘这个模型。提示帧别录太多。如果数组有几千个元素一次排序能产生几十万帧内存直接撑爆。做演示的时候数组控制在20到60个元素之间就够了视觉效果最好也不会爆内存。6.3 没有图形界面时的降级方案如果你在没有图形环境的机器上跑比如服务器、容器Swing是起不来的。这时候可以用控制台做字符画动画原理一样每记录一帧就用字符把数组的值映射成一行星号配合\r覆盖输出加上一点Thread.sleep也能做出滚动效果。public static void printFrame(int[] frame, int[] hi) { for (int i 0; i frame.length; i) { boolean active false; for (int h : hi) if (h i) active true; System.out.println((active ? : ) #.repeat(Math.max(1, frame[i]))); } System.out.println(------); }这种输出的好处是顺手坏处是刷屏所以配合清屏操作或者在IDE里往上翻着看。我个人觉得做算法讲解的视频或者博客配图时这种字符画其实比彩色柱子更有硬核的感觉。当然如果只是自己理解算法直接用带回放的控制台版本最快。7. 踩坑记录与选型速查前面代码贴得差不多了最后这部分讲讲真刀真枪用的时候会遇到什么。排序算法的坑很多不是算法本身的数学问题而是实现细节、边界条件、调用姿势的问题。我把这些年攒下来的问题整理成两张表方便你直接查。7.1 十个最容易翻车的细节问题现象根因解决方式快排在有序数组上极慢固定基准导致划分极端不平衡随机选基准或三数取中快排在大量重复值上退化两路划分无法剥离等值元素改用三路划分归并排序结果不稳定合并时等值判断取了右边条件改为严格小于才取右计数排序内存溢出值域跨度太大先判断值域超过阈值改用比较排序堆排序结果顺序错乱建堆起点写成了n-1建堆从n/2-1开始向0遍历插入排序数组越界while条件里j0写在了后面边界判断必须放第一个条件动画帧内容全一样存的是数组引用而非副本记录时装帧用clone快排递归栈溢出递归深度过大或死循环检查lo/hi更新必要时改小数据量基数排序出现负数异常下标算法不适用负数拆分正负或统一加偏移量性能测试结果不可信没有预热、没复制原始数据预热副本多轮取均值这张表里的每一条基本都是我或者同事真实踩过的。尤其是快排递归栈溢出这条网上一堆快排代码在小数据下看着没问题一上大规模数据直接StackOverflowError本质是递归深度失控。7.2 一张表搞定选型选型这件事没有标准答案得看数据规模、数据特征、内存约束、稳定性要求。我把常见的场景和推荐方案整理在这张表里可以直接对照使用。场景推荐算法理由数据量小于50插入排序常数小无递归开销通用整数数组追求速度三路快排平均最快原地排序需要稳定数据量中等归并排序稳定且最坏O(nlogn)内存紧张要求原地堆排序或快排空间O(1)或O(logn)值域很小的整数计数排序线性时间数据均匀分布桶排序线性时间分布均匀时极快固定位数的整数基数排序线性时间稳定近乎有序的数据插入排序或TimSort接近线性要求最坏情况有保证归并或堆排无退化风险再多说一句工程实践。绝大多数时候你不需要自己写排序直接用Arrays.sort或Collections.sort就行JDK的实现经过千锤百炼比你手写快得多也稳得多。但理解底层用了什么算法、为什么这么选在性能调优、排查诡异bug、面试沟通上都有实打实的价值。比如你突然发现某个接口在特定数据下特别慢知道Arrays.sort对基本类型用的是快排、有序数据下可能不退化因为双轴快排有三数取值保护这些知识就能帮你快速定位方向。最后分享我自己的一个练习方法。别只看着代码敲一遍就完事找个在线可视化工具或者自己写个简单回放把自己写的排序过程一帧帧看一遍。你会发现自己代码里很多想当然的地方——比如某个循环边界写成还是某次交换到底有没有必要。看着动画里柱子一点点归位比盯着控制台输出的一串数字强太多了。这套十种算法的代码和测试骨架我从三年前开始攒中间改过好几版每次重读都能发现新的细节这大概就是基础知识的魅力——它不会过时但可以一直挖得更深。 Java十种排序算法全解析：原理、代码、动画演示与工程选型
排序算法这个东西说它是Java程序员的老朋友一点不夸张。你翻任何一本数据结构教材前几章一定有它你面任何一家像样的公司手撕排序几乎是保留节目你在真实项目里用Arrays.sort或者Collections.sort的时候底层跑的其实也是这些老朋友的各种杂交版本。我这几年带过几个新人也做过不少技术复盘发现一个很有意思的现象大多数人对十种排序算法的记忆停留在背结论——快排平均O(nlogn)、冒泡O(n²)、归并稳定——但你真让他写一个不带bug的三路快排或者解释清楚为什么JDK对基本类型和对象类型用了两套排序策略能说明白的不超过三成。这篇内容我打算把Java里常用的十种排序算法从头到尾捋一遍冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数。不只是贴代码还要讲清楚每个算法为什么这么设计、边界在哪、生产环境里到底该选谁。另外标题里提到了演示动画这块我也会单独拎出来讲因为排序算法的动画可视化其实是理解算法最直观的方式我会给你一个能跑起来的思路把每一次交换都变成一帧画面。适合谁看如果你是刚开始学数据结构的在校生这篇可以当你的入门加进阶材料如果你是在准备面试的Java后端这篇能帮你把八股文里的排序部分从背变成懂如果你已经工作几年但很少自己手写排序了当成一次系统性复习也不错。代码全部是可直接复制运行的Java版本我会标清楚每个算法的注意事项和常见坑。1. 先给这十种算法按脾气分个类上来就写代码是最容易劝退的做法因为十种算法混在一起讲你根本记不住谁是谁。我的习惯是先按一个大分界线把它们分成两拨比较类排序和非比较类排序。这条线一划开你会发现后面的所有特性——时间复杂度下限、能不能突破O(nlogn)、稳定性怎么来的——全都有了解释的锚点。1.1 比较类和非比较类中间隔着一道墙比较类排序顾名思义算法执行过程中判断两个元素大小关系靠的是比较这个动作。冒泡、选择、插入、希尔、归并、快速、堆这七种都属于比较类。它们有一个共同的理论天花板在只依赖比较的前提下任何排序算法的最好情况都不可能低于O(nlogn)。这个结论不是我随口说的是有决策树模型证明的——n个元素一共有n!种排列每次比较最多把可能性劈成两半所以至少需要log₂(n!)次比较用斯特林公式展开大约就是n·logn级别。所以你在任何地方看到某某比较排序平均复杂度O(n)基本可以直接判定是错的。非比较类排序就是另外一拨计数、桶、基数。它们不靠元素之间的比较而是利用元素本身的数值信息——比如值域范围、位数结构——来直接决定元素该放哪个位置。正因为绕开了比较这道坎它们才能做到线性时间O(nk)甚至O(n)。代价也很明显它们对数据有强假设计数排序要求值域不能太大基数排序要求元素是整数或者能拆成位桶排序则要求数据分布相对均匀。数据一旦不满足假设性能会断崖式下跌甚至比冒泡还难看。理解这条分界线的现实意义在于面试官问你能不能实现一个O(n)的通用排序正确答案是不能除非你放弃通用性对数据做额外假设。这句话说出来比背十个结论都显得专业。1.2 稳定性不是玄学它决定你的业务数据会不会错乱再说稳定性。所谓稳定是指排序前后值相等的元素相对顺序保持不变。很多人觉得这没啥用反正值都一样顺序变了能怎样我举个真实场景你就懂了。假设你有一批订单先按金额排好序了现在业务要求再按状态排一次希望同一状态内的订单仍然保持金额升序。如果你的排序算法不稳定那么第二次排序后同状态订单的金额顺序就被打乱了你还得再排一次白白多干一遍活。十种算法里稳定的有冒泡、插入、归并、计数、桶、基数。不稳定的有选择、希尔、快速、堆。这里特别要提醒一个常被忽略的点稳定性描述的是算法本身不是某一次运行结果。有人写了个快排跑一组特定数据发现没乱就说我这个快排是稳定的这属于典型的以偏概全。快排只要发生跨位置交换稳定性就没了。还有一个特别容易踩的坑Java里的Arrays.sort对基本类型数组用的是双轴快速排序不稳定对对象数组用的是TimSort稳定。同样是Java的排序API换个参数类型稳定性就变了。所以如果你业务上依赖稳定性一定要看清楚自己传进去的是int[]还是Integer[]或者干脆自己用归并。2. 动手之前把测试骨架搭起来我发现很多人学算法的方式是抄一段代码跑一下main方法输出看着对就完事。这种验证方式其实很不靠谱因为排序的边界情况太多了空数组、单元素、全相等、完全逆序、大量重复。不搭一个像样的测试骨架你根本不知道自己写的算法是不是只在标准输入下才正确。2.1 公共交换方法和数组打印先准备两个工具方法后面十个算法都要反复用到。第一个是交换第二个是校验和打印。这里有个小细节值得单独说很多人喜欢写arr[i] arr[i] arr[j] - (arr[j] arr[i])这种炫技式交换或者用异或交换看起来省了一个临时变量但实际上可读性极差而且在i j的时候异或交换会把自己清零是个隐藏炸弹。老老实实用临时变量编译器优化之后性能没差别。public final class SortUtil { // 交换两个下标的值老老实实用临时变量 public static void swap(int[] arr, int i, int j) { if (i j) return; // 防御式写法避免无意义操作 int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } // 顺序校验只要发现一处逆序就返回false public static boolean isSorted(int[] arr) { for (int i 1; i arr.length; i) { if (arr[i - 1] arr[i]) return false; } return true; } public static void print(int[] arr) { StringBuilder sb new StringBuilder([); for (int i 0; i arr.length; i) { sb.append(arr[i]); if (i ! arr.length - 1) sb.append(, ); } sb.append(]); System.out.println(sb); } }测试数据生成这块我建议至少准备四组随机数组、完全逆序数组、全相等数组、以及大量重复值的数组。前两组测正确性和常规性能后两组专治快排和堆排的极端退化。尤其是全相等数组朴素的两路快排遇到它会退化成O(n²)这个坑我在面试里见候选人踩过不止一次。2.2 计时基准怎么写才不算白跑写性能测试的时候有几个细节决定了你的数据有没有参考价值。第一必须做预热JVM有即时编译前几次运行走的是解释执行慢得离谱你得先跑个几百轮让热点代码编译完毕。第二每轮排序要用原始数据的副本否则第二轮开始你排的就是已经有序的数组测出来的是有序数组排序耗时不是你想测的东西。第三多轮取平均或者取中位数单次测波动太大。下面这个骨架可以直接用public static long bench(java.util.function.Consumerint[] sorter, int[] source, int warmup, int rounds) { int[] copy source.clone(); for (int i 0; i warmup; i) { sorter.accept(source.clone()); } long total 0; for (int i 0; i rounds; i) { copy source.clone(); long start System.nanoTime(); sorter.accept(copy); total System.nanoTime() - start; } return total / rounds; // 返回平均纳秒 }注意用System.nanoTime()而不是System.currentTimeMillis()后者精度只有毫秒级排几万个元素的耗时可能只显示个位数毫秒误差大到没有意义。这个骨架搭好之后后面每写一个算法都过一遍测试和基准你就能拿到一组自己实测出来的数据。我实测下来十万随机整数冒泡要好几秒快排基本在十毫秒上下差距是三个数量级。自己跑出来的数字比看表格印象深得多。3. 三种基础排序冒泡、选择、插入这三种算法经常被人瞧不起觉得太简单了学它干嘛。我的看法相反它们恰恰是理解排序思想的最佳入口而且插入排序在真实工程里被大量使用——JDK的TimSort在数据量小的时候就是切回插入排序的。所以别跳过把每个算法的退化条件和优化空间都摸清楚。3.1 冒泡排序加不加标志位是两个东西冒泡的核心思路是相邻两两比较大的往后挪每轮结束最大的元素就冒到了末尾。朴素版本的代码很直白但有个明显的浪费如果某一轮从头到尾一次交换都没发生说明整个数组已经有序了后面的轮次纯属白跑。加上一个布尔标志位最好情况复杂度就能从O(n²)降到O(n)。public static void bubbleSort(int[] arr) { for (int end arr.length - 1; end 0; end--) { boolean swapped false; for (int i 0; i end; i) { if (arr[i] arr[i 1]) { SortUtil.swap(arr, i, i 1); swapped true; } } if (!swapped) break; // 本轮无交换提前收工 } }还有个进阶优化叫记录最后一次交换位置因为如果某一轮里最后一次交换发生在下标k那k之后的元素其实已经有序了下一轮只需要扫到k就行。这个优化在近乎有序的数据上效果明显但代码复杂度也上去了实战里意义不大知道有这个思路即可。冒泡的稳定性是天然保证的因为只有arr[i] arr[i1]才交换相等时不动作相对顺序自然不变。这也是为什么初学者理解稳定性从冒泡入手最合适。3.2 选择排序交换最少但别指望它稳定选择排序每一轮从未排序区间里挑一个最小值和未排序区间的第一个位置交换。它的特点是交换次数最少最多n-1次所以如果元素交换的成本很高比如元素是大对象交换涉及大量内存拷贝选择排序反而有它的价值。public static void selectionSort(int[] arr) { for (int i 0; i arr.length - 1; i) { int minIdx i; for (int j i 1; j arr.length; j) { if (arr[j] arr[minIdx]) minIdx j; } if (minIdx ! i) SortUtil.swap(arr, i, minIdx); } }但它有个致命细节不稳定。我举个极简的例子数组[5, 5, 2]第一轮找到最小值2下标2和下标0的5交换数组变成[2, 5, 5]。原本在前的那个5跑到后面去了两个5的相对顺序被打乱。这就是不稳定性的来源——跨位置的交换把元素甩过了同值的兄弟。面试里如果被问选择排序为什么不稳定把[5, 5, 2]这个例子说出来比任何抽象解释都有效。3.3 插入排序小数组上的隐形冠军插入排序的思路是维护一个已排序区每次从右边取一个元素在已排序区里从后往前找位置插入找的同时把比它大的元素统统右移一格。这个边比较边搬移的写法比先找位置再搬移要紧凑是标准写法。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]; // 比key大的统统右移 j--; } arr[j 1] key; // 空出来的位置放key } }插入排序特别值得说的有两点。第一它在近乎有序的数据上效率极高。如果每个元素离它最终位置最多k步总复杂度就是O(nk)k很小时基本等价于线性。第二正因为这个特性它在工业级排序实现里频繁出现——JDK的TimSort对长度小于某个阈值的分段直接用插入排序双轴快排对小数组也做类似处理。提醒写插入排序时while条件里判断j 0一定要放在arr[j] key前面。如果写反了当j减到-1时先访问arr[-1]直接数组越界异常。这是新手最常翻的车。稳定性方面插入排序是稳定的因为条件是严格大于才移动相等的元素不会被搬走自然保持原顺序。4. 进阶四件套希尔、归并、快排、堆排这四种是真正在生产环境和面试里唱主角的。希尔是插入排序的升级版归并和快排是两种截然不同的分治思路堆排则把堆这种数据结构的价值发挥到极致。把它们的实现细节和适用场景搞透你的算法功底基本就稳了。4.1 希尔排序增量序列选错就白写希尔排序的想法很朴素既然插入排序在近乎有序的数组上快那我就先做一轮大跨度的插入排序让数组变得大致有序再逐步缩小跨度最后用一次普通的插入排序收尾。这个跨度就是增量。代码结构上它就是把插入排序里的j - 1换成了j - gap。public static void shellSort(int[] arr) { int n arr.length; int gap 1; while (gap n / 3) gap gap * 3 1; // Knuth序列1,4,13,40... while (gap 1) { for (int i gap; i n; i) { int key arr[i]; int j i - gap; while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } gap / 3; } }增量序列的选择直接决定性能。常见的几种n/2递减的最简单但效率一般Hibbard序列1, 3, 7, 15...最坏O(n^1.5)Knuth序列1, 4, 13, 40...实测表现不错也是我平时用的。用3h1递推的好处是能保证最后的gap一定是1而且增量之间互质性较好能减少同一元素被反复搬运的情况。希尔排序的时间复杂度分析比较麻烦取决于增量序列最坏大约在O(n^1.3)到O(n²)之间。它不稳定因为跨间隔的交换会打乱同值元素顺序。但它的优势是不需要额外空间这点比归并强。数据量在几万以内、内存又比较紧张的场景希尔是很好的折中选择。4.2 归并排序稳定、可预测代价是一份额外空间归并的核心是分治把数组对半切分别排好再合并两个有序数组。合并的过程需要一个临时数组来暂存结果。它的复杂度非常稳定任何输入都是O(nlogn)不存在最坏退化这是它相对快排最大的优势。public static void mergeSort(int[] arr) { if (arr.length 2) return; int[] tmp new int[arr.length]; // 只分配一次避免递归里反复new msort(arr, tmp, 0, arr.length - 1); } private static void msort(int[] arr, int[] tmp, int lo, int hi) { if (lo hi) return; int mid lo (hi - lo) / 2; // 防溢出写法 msort(arr, tmp, lo, mid); msort(arr, tmp, mid 1, hi); if (arr[mid] arr[mid 1]) return; // 已经有序就不用合并了 merge(arr, tmp, lo, mid, hi); } private static void merge(int[] arr, int[] tmp, int lo, int mid, int hi) { System.arraycopy(arr, lo, tmp, lo, hi - lo 1); int i lo, j mid 1; for (int k lo; k hi; k) { if (i mid) arr[k] tmp[j]; else if (j hi) arr[k] tmp[i]; else if (tmp[j] tmp[i]) arr[k] tmp[j]; else arr[k] tmp[i]; } }这里有两个细节特别值得记。第一int mid lo (hi - lo) / 2而不是(lo hi) / 2后者在lo和hi都很大时会整型溢出虽然Java数组长度限制让它不太可能触发但这是通用写法养成习惯没坏处。第二if (arr[mid] arr[mid 1]) return;这句优化在部分有序的情况下能省掉大量合并操作TimSort里也有类似逻辑。注意合并判断里我写的是tmp[j] tmp[i]严格小于才取右边这样左边相等元素会优先输出稳定性就保住了。如果把等号方向写反归并也会变得不稳定。另外归并的额外空间是O(n)递归深度是O(logn)如果数据规模特别大可以考虑自底向上的迭代版本避免递归栈压力。4.3 快速排序三路划分解决重复元素灾难快排是面试出现频率最高的排序算法没有之一。核心是选一个基准值把数组分成小于基准和大于基准两部分然后递归处理两边。但朴素的实现有几个坑有序数组上退化成O(n²)、大量重复元素时同样退化。所以真正能拿去面试的快排基本上都要加随机化和三路划分。三路划分把数组分成小于、等于、大于三段等于基准的元素直接用一趟扫描集中到中间后续递归只处理小于和大于两段。这个改动对重复元素多的数组效果立竿见影。public static void quickSort(int[] arr) { qsort(arr, 0, arr.length - 1); } private static void qsort(int[] arr, int lo, int hi) { if (lo hi) return; int pivot arr[lo (int) (Math.random() * (hi - lo 1))]; // 随机选基准 int lt lo, i lo, gt hi; while (i gt) { if (arr[i] pivot) SortUtil.swap(arr, lt, i); else if (arr[i] pivot) SortUtil.swap(arr, i, gt--); else i; } qsort(arr, lo, lt - 1); qsort(arr, gt 1, hi); }三路划分的循环逻辑需要理解清楚lt指向小于区的下一个空位gt指向大于区的下一个空位i是当前扫描指针。遇到小于基准的换到lt位置并两个指针都前进遇到大于基准的换到gt位置gt后退但i不动因为换过来的元素还没检查遇到等于基准的i直接前进。循环结束时[lo, lt-1]是小于区[lt, gt]是等于区[gt1, hi]是大于区等于区不用再处理。随机选基准这一步不能省。如果固定取第一个或最后一个元素面对完全有序数组每次划分都会极不平衡递归深度变成n时间复杂度退化到O(n²)还会导致栈溢出。随机化之后期望复杂度才是O(nlogn)。提示JDK里Arrays.sort(int[])用的是双轴快速排序DualPivotQuicksort比单轴三路快排再做了一层优化选两个基准把数组分成三段。这是工程上的极致优化手写面试版掌握三路划分就够了。4.4 堆排序原地且最坏情况也不塌堆排序利用的是完全二叉树的数组表示下标i的左孩子是2i1右孩子是2i2父节点是(i-1)/2。排序分两步先建大顶堆再反复把堆顶最大值换到数组末尾然后对剩余部分重新下调整堆。public static void heapSort(int[] arr) { int n arr.length; for (int i n / 2 - 1; i 0; i--) siftDown(arr, i, n); // 建堆 for (int end n - 1; end 0; end--) { SortUtil.swap(arr, 0, end); siftDown(arr, 0, end); } } private static void siftDown(int[] arr, int i, int size) { while (true) { int left 2 * i 1, right left 1, largest i; if (left size arr[left] arr[largest]) largest left; if (right size arr[right] arr[largest]) largest right; if (largest i) break; SortUtil.swap(arr, i, largest); i largest; } }建堆为什么从n/2 - 1开始因为下标大于等于n/2的节点都是叶子节点叶子本身就是一个合法的堆不需要调整。建堆的整体复杂度是O(n)而不是O(nlogn)这个结论很多人会算错可以这样理解越靠近底层的节点越多但它们的下沉深度越浅把节点数×下沉深度求和最终收敛到线性级别。堆排序最大的优势是原地排序、空间O(1)、最坏情况也是O(nlogn)不像快排有退化风险。它的劣势是缓存不友好访问模式跳跃实际跑起来通常比快排慢一截。另一个实际用途是求Top K问题——只维护一个大小为K的堆不用全排序这个场景堆排思路比快排更合适。堆排不稳定因为堆顶和末尾的交换是跨位置的。5. 三种线性时间排序计数、桶、基数接下来这三种跳出比较的框架用数值本身的信息换时间。它们的共同前提是数据得讲道理范围可控、分布均匀、或者能拆成位。用对了是降维打击用错了就是灾难。5.1 计数排序把值当数组下标计数排序的做法是先找出数组的最小值和最大值开一个长度为max - min 1的计数数组统计每个值出现的次数再按顺序把值填回去。它本质上是用值做下标直接定位。基础版本很简单但如果要求稳定还需要用前缀和把计数数组改造成每个值最后一个位置的下标。public static void countingSort(int[] arr) { if (arr.length 0) return; int min arr[0], max arr[0]; for (int v : arr) { if (v min) min v; if (v max) max v; } int[] count new int[max - min 1]; for (int v : arr) count[v - min]; int idx 0; for (int v 0; v count.length; v) { while (count[v]-- 0) arr[idx] v min; } }它的复杂度是O(n k)k是值域大小。这里的关键就在于k。如果数组是[1, 2, 100000000]这种k飙到一亿开这么大一个计数数组直接内存爆炸性能还不如快排。所以计数排序的适用场景非常明确值域范围不大或者值是年龄、分数、状态码这类有限枚举。注意带负数的时候用v - min做偏移别直接用值当下标否则负数下标会抛异常。这个偏移操作是计数排序处理有符号整数的标准手法。5.2 桶排序计数排序的推广版桶排序是把值域划分成若干个区间每个区间是一个桶把元素丢进对应的桶桶内各自排序通常用插入排序因为桶内元素少最后按桶的顺序拼接。它相当于把计数排序的一个值一个桶放宽成一段值一个桶适合值域大但分布均匀的数据。public static void bucketSort(int[] arr, int bucketCount) { if (arr.length 2) return; int min arr[0], max arr[0]; for (int v : arr) { if (v min) min v; if (v max) max v; } if (min max) return; java.util.Listjava.util.ListInteger buckets new java.util.ArrayList(); for (int i 0; i bucketCount; i) buckets.add(new java.util.ArrayList()); double step (double) (max - min 1) / bucketCount; for (int v : arr) { int idx (int) ((v - min) / step); if (idx bucketCount) idx bucketCount - 1; // 边界保护 buckets.get(idx).add(v); } int k 0; for (java.util.ListInteger bucket : buckets) { java.util.Collections.sort(bucket); // 桶内排序稳定 for (int v : bucket) arr[k] v; } }桶数量怎么选常见做法是sqrt(n)或者直接取n。桶太多每个桶就一两个元素管理开销反而大桶太少桶内元素多退化成普通排序。经验做法是让桶数量和元素数量同量级保证每个桶平均元素数是个小常数。桶排序的性能高度依赖数据分布。数据均匀分布时接近O(n)但如果有严重倾斜比如99%的元素挤在一个桶里那这个桶内部排序的复杂度就变成了主导整体性能崩塌。所以用桶排序之前一定要先看看数据的分布特征别拍脑袋上。5.3 基数排序一位一位地分拣基数排序是把整数按位拆开从最低位开始每一位做一次稳定的分配和收集重复到最高位做完整个数组就有序了。它依赖的核心前提是每一位的排序必须是稳定的通常用计数排序来实现每一位的分配。public static void radixSort(int[] arr) { if (arr.length 2) return; int max arr[0]; for (int v : arr) if (v max) max v; int[] tmp new int[arr.length]; for (int exp 1; max / exp 0; exp * 10) { int[] count new int[10]; for (int v : arr) count[(v / exp) % 10]; for (int i 1; i 10; i) count[i] count[i - 1]; for (int i arr.length - 1; i 0; i--) { int digit (arr[i] / exp) % 10; tmp[--count[digit]] arr[i]; } System.arraycopy(tmp, 0, arr, 0, arr.length); } }为什么要从后往前遍历放元素因为我们要保持稳定性。count数组在前缀和之后count[d]表示当前位小于等于d的元素总个数也就是数字d应该放置的最后一个位置。从后往前遍历原数组把元素放到--count[digit]的位置能保证在原数组中靠后的同位数元素放到更靠后的位置稳定性就保住了。基数排序的复杂度是O(d·(n k))d是最大数的位数k是进制十进制就是10。对32位整数来说d最多10用十进制所以实际复杂度非常接近线性。它也不擅长负数处理负数需要额外做偏移或者分正负两批处理这点用的时候要留意。6. 演示动画让每一次交换都被看见终于说到标题里的动画部分了。排序算法看得再多次代码不如看一次动态过程来得直观——你能亲眼看到快排的划分是怎么一步步把区间缩小的堆排是怎么反复把堆顶甩到末尾的。这里我讲两个层面的方案一个是有图形界面的Swing版本一个是纯控制台的降级版本。6.1 先把过程录下来帧模型的思路直接边排序边刷新界面是行不通的因为排序执行得太快一眨眼就跑完了你什么都看不见。所以正确的思路是先录制再回放。具体做法是在排序过程中每发生一次有意义的操作交换、赋值、比较就把当前数组的状态快照存进一个列表同时记录当前高亮的下标位置。排序执行完后我们拿到一个帧序列再用定时器一帧一帧地播放。import java.util.ArrayList; import java.util.List; public class FrameRecorder { public final Listint[] frames new ArrayList(); public final Listint[] highlights new ArrayList(); // 记录一帧数组快照 需要高亮的下标 public void record(int[] arr, int... highlightIdx) { frames.add(arr.clone()); // 必须clone否则引用会被后续修改 highlights.add(highlightIdx); } }这里最容易犯的错误是frames.add(arr)直接把引用存进去。数组是可变对象你后面每一次交换都会把之前存的快照一起改掉最后回放时你会看到所有帧长得一模一样。必须用clone()复制一份。这个坑我自己踩过调试了半天才发现是引用问题。6.2 用 Swing 把数组画成柱子有了帧数据画图就简单了。用一个JPanel重写paintComponent把数组的每个值画成一根竖直柱子高度按比例映射当前帧里被高亮的下标用另一种颜色画。然后用javax.swing.Timer每隔几十毫秒推进一帧调用repaint()触发重绘。import javax.swing.*; import java.awt.*; public class SortPanel extends JPanel { private final FrameRecorder rec; private int cursor 0; public SortPanel(FrameRecorder rec) { this.rec rec; Timer timer new Timer(30, e - { // 30ms一帧约33帧每秒 if (cursor rec.frames.size() - 1) { cursor; repaint(); } else { ((Timer) e.getSource()).stop(); } }); timer.start(); } Override protected void paintComponent(Graphics g) { super.paintComponent(g); int[] frame rec.frames.get(cursor); int[] hi rec.highlights.get(cursor); int w getWidth() / Math.max(1, frame.length); for (int i 0; i frame.length; i) { boolean active false; for (int h : hi) if (h i) active true; g.setColor(active ? Color.RED : new Color(70, 130, 180)); int h frame[i]; g.fillRect(i * w, getHeight() - h, Math.max(1, w - 2), h); } } }把面板塞进JFrame就能跑。想让它更好看可以把数组的值缩放到面板高度范围内加上坐标轴甚至同时显示当前是第几轮、比较了多少次。这些都属于锦上添花核心还是帧序列 定时重绘这个模型。提示帧别录太多。如果数组有几千个元素一次排序能产生几十万帧内存直接撑爆。做演示的时候数组控制在20到60个元素之间就够了视觉效果最好也不会爆内存。6.3 没有图形界面时的降级方案如果你在没有图形环境的机器上跑比如服务器、容器Swing是起不来的。这时候可以用控制台做字符画动画原理一样每记录一帧就用字符把数组的值映射成一行星号配合\r覆盖输出加上一点Thread.sleep也能做出滚动效果。public static void printFrame(int[] frame, int[] hi) { for (int i 0; i frame.length; i) { boolean active false; for (int h : hi) if (h i) active true; System.out.println((active ? : ) #.repeat(Math.max(1, frame[i]))); } System.out.println(------); }这种输出的好处是顺手坏处是刷屏所以配合清屏操作或者在IDE里往上翻着看。我个人觉得做算法讲解的视频或者博客配图时这种字符画其实比彩色柱子更有硬核的感觉。当然如果只是自己理解算法直接用带回放的控制台版本最快。7. 踩坑记录与选型速查前面代码贴得差不多了最后这部分讲讲真刀真枪用的时候会遇到什么。排序算法的坑很多不是算法本身的数学问题而是实现细节、边界条件、调用姿势的问题。我把这些年攒下来的问题整理成两张表方便你直接查。7.1 十个最容易翻车的细节问题现象根因解决方式快排在有序数组上极慢固定基准导致划分极端不平衡随机选基准或三数取中快排在大量重复值上退化两路划分无法剥离等值元素改用三路划分归并排序结果不稳定合并时等值判断取了右边条件改为严格小于才取右计数排序内存溢出值域跨度太大先判断值域超过阈值改用比较排序堆排序结果顺序错乱建堆起点写成了n-1建堆从n/2-1开始向0遍历插入排序数组越界while条件里j0写在了后面边界判断必须放第一个条件动画帧内容全一样存的是数组引用而非副本记录时装帧用clone快排递归栈溢出递归深度过大或死循环检查lo/hi更新必要时改小数据量基数排序出现负数异常下标算法不适用负数拆分正负或统一加偏移量性能测试结果不可信没有预热、没复制原始数据预热副本多轮取均值这张表里的每一条基本都是我或者同事真实踩过的。尤其是快排递归栈溢出这条网上一堆快排代码在小数据下看着没问题一上大规模数据直接StackOverflowError本质是递归深度失控。7.2 一张表搞定选型选型这件事没有标准答案得看数据规模、数据特征、内存约束、稳定性要求。我把常见的场景和推荐方案整理在这张表里可以直接对照使用。场景推荐算法理由数据量小于50插入排序常数小无递归开销通用整数数组追求速度三路快排平均最快原地排序需要稳定数据量中等归并排序稳定且最坏O(nlogn)内存紧张要求原地堆排序或快排空间O(1)或O(logn)值域很小的整数计数排序线性时间数据均匀分布桶排序线性时间分布均匀时极快固定位数的整数基数排序线性时间稳定近乎有序的数据插入排序或TimSort接近线性要求最坏情况有保证归并或堆排无退化风险再多说一句工程实践。绝大多数时候你不需要自己写排序直接用Arrays.sort或Collections.sort就行JDK的实现经过千锤百炼比你手写快得多也稳得多。但理解底层用了什么算法、为什么这么选在性能调优、排查诡异bug、面试沟通上都有实打实的价值。比如你突然发现某个接口在特定数据下特别慢知道Arrays.sort对基本类型用的是快排、有序数据下可能不退化因为双轴快排有三数取值保护这些知识就能帮你快速定位方向。最后分享我自己的一个练习方法。别只看着代码敲一遍就完事找个在线可视化工具或者自己写个简单回放把自己写的排序过程一帧帧看一遍。你会发现自己代码里很多想当然的地方——比如某个循环边界写成还是某次交换到底有没有必要。看着动画里柱子一点点归位比盯着控制台输出的一串数字强太多了。这套十种算法的代码和测试骨架我从三年前开始攒中间改过好几版每次重读都能发现新的细节这大概就是基础知识的魅力——它不会过时但可以一直挖得更深。