很多人第一次听到“秩排序”Rank Sort这个名字都会下意识把它归到“冷门排序”那一类。实际上它的核心思想简单到可以用一句话讲完给每个元素数一数数组里有多少个元素比它小这个数字就是它在最终有序序列里的位置然后把它直接放到对应下标上。没错排序这件事在这里被简化成了“数数”加“放位置”。我最初认真琢磨这个算法是因为A同学在讨论排序稳定性时顺手写了个按“比它小的元素个数”来排的玩具代码结果被重复元素折磨到怀疑人生。这篇文章就从这个朴素问题出发我用 Java 把秩排序从零实现一遍拆解重复元素如何处理、稳定性如何保证再把它和计数排序、快速排序等经典算法放在一起对比最后给你一份可以直接复现的测试清单。无论你是刚学数据结构的学生还是在准备算法面试这篇都适合你。1. 排序的底层逻辑给每个元素算一个“该待的位置”1.1 秩是什么从“排第几位”说起“秩”这个字在线性代数里通常和矩阵相关表示极大线性无关组的向量个数但在数据结构里我们可以理解得更朴素——“某个元素在一堆元素中从小到大排第几位”。比如 [50, 10, 20, 40, 30] 中10 是最小的它的秩是 020 前面只有一个 10秩是 130 的秩是 240 的秩是 350 的秩是 4。如果我把每个元素按自己的秩放到新数组的下标上就得到 [10, 20, 30, 40, 50]排序完成。这里的关键认识是排序的本质是给每个元素确定目标位置。插入排序、冒泡排序、快速排序都是通过不停地比较和交换让元素一步一步逼近目标位置而秩排序的思路完全不同——一次算准一次到位。它不做交换不搞递归只需要回答一个简单的问题在我之外还有多少个元素应该排在我前面正因为这个“先算位置、再放元素”的思路足够干净秩排序才经常被用来和“通过交换逼近位置”的传统排序作对比。很多讲排序原理的课程喜欢把它放在计数排序之前讲也是因为这个位置思想是理解计数排序、基数排序的天然跳板。1.2 把“数一数前面有几个人”写成代码计算一个元素 arr[i] 的秩最直接的办法就是遍历整个数组统计满足 arr[j] arr[i] 的 j 的个数int rank 0; for (int j 0; j arr.length; j) { if (arr[j] arr[i]) { rank; } }外层循环负责遍历每个元素内层循环负责给当前元素数“前面有多少个更小的”。每次数完arr[i] 的目标位置就是 rank。这样一个双重循环写下来你已经完成了能处理“所有元素互不相同”情况的秩排序的核心骨架。用生活场景类比就是一排同学按身高从低到高拍照每个人只需要知道自己前面站了几个比自己矮的人。站第 0 位的最矮站最后位的最高每个人的“前面人数”就是他的秩而照片站位就是按秩排出来的。2. 第一版 Java 实现直接数、直接放然后翻车2.1 最直观的写法往往问题最多顺着上面的思路我一开始写出来的版本长这样public static void rankSortNaive(int[] arr) { int n arr.length; int[] sorted new int[n]; for (int i 0; i n; i) { int rank 0; for (int j 0; j n; j) { if (arr[j] arr[i]) { rank; } } sorted[rank] arr[i]; } System.arraycopy(sorted, 0, arr, 0, n); }代码很简短先开一个和原数组等长的 sorted 数组对每个元素统计比它小的元素个数然后直接把元素放到 sorted 的对应下标。最后用 System.arraycopy 把结果拷回原数组保证调用之后原数组被真正排序。注意内层循环里 j 从 0 到 n-1包含 j i 的情况因为一个元素不可能小于自己所以这个比较是空操作不影响结果但比较次数会略微超过理论值这个我们在后面复杂度部分再说。如果数组元素全部不同这个版本是正确的。比如 [5, 2, 8, 1, 9]5 的秩是 22 的秩是 18 的秩是 31 的秩是 09 的秩是 4放到新数组后得到 [1, 2, 5, 8, 9]。问题在于一旦出现重复元素这个版本的逻辑就立刻崩溃。2.2 翻车现场两个相同元素抢同一个位置以 [2, 1, 1, 3] 为例我用上面的代码跑一遍第一个 1下标 1的秩是 0因为没有任何元素比它小第二个 1下标 2的秩仍然是 0因为两个 1 是相等关系用 arr[j] arr[i] 判定时相等元素之间不会互相计数2 的秩是 1因为它前面有两个 13 的秩是 3因为前面有三个元素比它小。两个 1 都想去 0 号位后写的那一个会把先写的覆盖掉。我实际运行的结果是sorted 数组最终变成了一个包含 0 默认值的乱序状态比如 [1, 0, 0, 3]完全不可用。到这里A同学的第一反应是那我在放置之前判断一下如果 rank 位置被占了就往后找第一个空位不就不会覆盖了吗这个“找空位塞进去”的想法非常自然我试过之后反而发现了一个更有意思的坑。加一个 occupied 布尔数组做线性探测int pos rank; while (pos n occupied[pos]) { pos; } sorted[pos] arr[i]; occupied[pos] true;对 [2, 1, 1, 3]这个探测版本的结果是 [1, 2, 1, 3]。第二个 1 的秩是 0当 0 号位被第一个 1 占用后它一路探测到 2 号位于是 1 被插到了 2 和 3 之间顺序彻底坏了。表面上它没有覆盖实际上“谁先谁后”的逻辑已经被破坏得面目全非。这个案例很好地说明了一个结论重复元素处理关键不是“放置时怎么找空位”而是“计算秩的时候就要把相等元素拆开”。3. 重复元素与稳定性真正的考点在这一行条件里3.1 修复把“出现得更早”也计入秩重复元素的本质问题是相等元素之间没有定义先后次序。如果两个 1 都认为自己该站第 0 位它们之间必须有一个规则来分先后。最简单的规则就是利用原始下标在原数组中下标更小的那个在排序后依然站在前面。代码改动非常小把统计条件从 arr[j] arr[i] 改成arr[j] arr[i] || (arr[j] arr[i] j i)含义就是统计“比当前元素小”的元素个数再加上“和当前元素相等但原始下标比我小”的元素个数。这样一来每个元素的秩都是独一无二的并且恰好是 [0, n-1] 的一个完整排列。回到 [2, 1, 1, 3]第一个 1下标 1没有更小的也没有更早的相等元素秩是 0第二个 1下标 2没有更小的但有一个更早的相等元素下标 1秩是 12下标 0有两个 1 比它小秩是 23下标 3有三个元素比它小秩是 3。按秩放回去得到 [1, 1, 2, 3]而且两个 1 的相对顺序和原数组保持一致。这就是稳定排序。修正后的完整代码public static void rankSort(int[] arr) { int n arr.length; int[] sorted new int[n]; for (int i 0; i n; i) { int rank 0; for (int j 0; j n; j) { if (arr[j] arr[i] || (arr[j] arr[i] j i)) { rank; } } sorted[rank] arr[i]; } System.arraycopy(sorted, 0, arr, 0, n); }3.2 稳定性的工程意义多关键字排序的基石如果你只是给一堆整数排序稳定性看起来无关紧要反正相等的整数长一个样。但在工程里排序对象往往是带多个字段的记录比如先按班级排序再按学号排序。如果第二趟排序不稳定第一趟按班级排好的顺序就可能被打乱。稳定排序保证同一班级内部的相对顺序由上一趟排序的结果决定最终多关键字排序才是正确的。很多教材讲秩排序时都默认元素互不相同把重复问题一句带过。但实际写代码时重复元素几乎是必然出现的。我见过不少同学能写出秩排序的骨架被追问“有重复元素怎么办”时却答不上来。所以如果你是在准备面试秩排序这个点真正值得记住的不是双循环而是这一行 tie-break 条件以及它和稳定性的关系。顺带一提计数排序里“逆序遍历原数组”的放置手法本质上也是在用同样的思路维持稳定性两种算法在这里是相通的。4. 两阶段设计把“计算秩”和“搬移数据”拆开4.1 拆开之后调试和复用都变容易了上面的单循环版本是“边算边放”代码短但有一个缺点一旦结果不对很难判断是“秩算错了”还是“放的位置错了”。把两步拆开先算完所有秩再统一搬移调试体验完全不一样public static int[] computeRank(int[] arr) { int n arr.length; int[] rank new int[n]; for (int i 0; i n; i) { for (int j 0; j n; j) { if (arr[j] arr[i] || (arr[j] arr[i] j i)) { rank[i]; } } } return rank; } public static void rankSortTwoPhase(int[] arr) { int[] rank computeRank(arr); int[] sorted new int[arr.length]; for (int i 0; i arr.length; i) { sorted[rank[i]] arr[i]; } System.arraycopy(sorted, 0, arr, 0, arr.length); }我之所以推荐这种写法不只是为了调试。rank 数组本身有独立的信息量相当于“每个元素在最终有序序列中的位置表”。你可以打印它、保存它、给它做进一步统计。很多真实系统在做分布式排序时第一步就是给数据分区并估算每个元素所在的名次再按名次把数据路由到对应节点思路和这个两阶段完全一致。实际工程里把“计算”和“执行”拆开往往是让代码可控、可测试的最简单手段。4.2 in-place 彩蛋省掉 sorted 数组的版本既然 rank 数组在加了 tie-break 之后是 [0, n-1] 的一个排列我们其实可以借助它直接在原数组里把元素放到位不需要 sorted 数组public static void rankSortInPlace(int[] arr) { int n arr.length; int[] rank computeRank(arr); for (int i 0; i n; ) { if (rank[i] i) { i; } else { int j rank[i]; int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; int tr rank[i]; rank[i] rank[j]; rank[j] tr; } } }思路是如果当前下标 i 上的元素它的秩不是 i说明它不该待在这里那就把它换到 rank[i] 位置换过去之后把位置表也同步交换。整个过程像顺着“每个元素指给自己的位置”走迷宫最终所有 rank[i] i数组也就位了。这个版本省掉了一个 sorted 数组但 rank 数组仍然占 O(n) 空间所以空间复杂度的量级没变只是常数更小。代码可读性明显下降我在实际项目里几乎不用它纯当算法趣味研究一下。5. 复杂度账本O(n²) 的时间换来的是什么5.1 时间都花在双重循环上秩排序的时间开销集中在计算秩的双重循环上外层要处理 n 个元素内层要把每个元素和所有其他元素比较一遍总共是 O(n²) 次比较。实际代码里内层循环还包含了一次和自己比较的空操作但常数不影响量级。关键在于不管输入是正序、逆序还是完全随机比较次数都固定是 O(n²)因为每个元素必须亲自和所有其他元素比过才知道自己的位置。这个特性决定了它是“非自适应”排序不像插入排序那样面对接近有序的数据会自动变快。空间上边算边放的版本需要 sorted 数组O(n) 额外空间两阶段版本还需要 rank 数组同样是 O(n)。稳定性方面加上 tie-break 之后秩排序是稳定排序朴素版在重复元素下根本跑不出正确结果稳定性更是无从谈起。5.2 和主流排序算法的对比算法平均/最坏时间额外空间稳定性一句话评价秩排序O(n²)O(n)可稳定一次算准位置比较次数固定冒泡排序O(n²)O(1)稳定交换频繁常数大选择排序O(n²)O(1)不稳定交换少但比较一样多插入排序O(n²)O(1)稳定接近有序时接近 O(n)快速排序O(n log n)O(log n)不稳定实际综合表现最佳的比较排序归并排序O(n log n)O(n)稳定稳定排序中的首选计数排序O(n k)O(k)稳定只适合整数且值域不大的场景从表里能直观看到秩排序的时间复杂度没有任何优势空间也不是最优。那它存在的意义是什么我的答案有两个。第一它是理解“位置等于名次”这个抽象概念的极好入口外排序、并行排序、数据库查询里的排序算子都依赖“先给元素算名次再搬运”这个框架。第二它的常数非常小内层循环就是一次整数比较没有递归、没有额外对象分配在 n 很小的时候它和工程级快速排序的差距并不大代码却简单得多。5.3 说实话什么时候用它什么时候别用我的建议很直接教学、入门、理解排序本质时秩排序值得完整实现一遍尤其是亲自跑一跑重复元素翻车的案例数据量小几十以内且要求代码极简时可以拿它当兜底排序数据量一旦上百上千立刻换 Java 标准库的 Arrays.sort它内部会根据数据规模自动选择双轴快排或归并排序的思路你手写的秩排序完全没有胜算如果数据是有限范围内的整数更优的选择是计数排序下一节细说。另外提一个有意思的点秩排序的每个元素的秩互不影响天然的可以并行计算——你可以把数组切给多个线程各算各的名次。但 n² 的比较次数扛不住数据规模增长并行也只是减缓衰减不是出路。真要做大规模并行排序业界用的是采样分区那一套思路。6. 从秩排序到计数排序一次顺理成章的升级6.1 两两比较太慢了换一个“报数”思路秩排序用两两比较来数“比我小的元素个数”代价是 O(n²)。换个角度如果数组里的值只是非负整数而且值域不大根本不需要两两比较。直接开一个大数组按下标统计每个值出现几次再做前缀和每个值的“起止位置区间”就出来了。前缀和本身就是“小于等于某个值的元素有多少个”这正是秩的批量版本。比如 [2, 1, 1, 3]值域 [0..3]频次数组 count [0, 2, 1, 1]前缀和 [0, 2, 3, 4]含义是“小于等于 v 的元素共有 count[v] 个”于是值 1 占据位置 0 到 1值 2 占据位置 2 到 2值 3 占据位置 3 到 3。这就是计数排序一个循环统计频次一个循环做前缀和最后逆序遍历原数组把元素放到对应位置全程 O(n k)k 是值域宽度。Java 实现如下public static void countingSort(int[] arr, int maxValue) { int[] count new int[maxValue 1]; for (int v : arr) { count[v]; } for (int i 1; i maxValue; i) { count[i] count[i - 1]; } int[] sorted new int[arr.length]; for (int i arr.length - 1; i 0; i--) { int v arr[i]; sorted[--count[v]] v; } System.arraycopy(sorted, 0, arr, 0, arr.length); }注意放元素时要倒着遍历原数组同一个值有多个元素时逆序放置可以保证先出现在原数组的元素落在靠前位置从而保持稳定性。这一步和秩排序里用 j i 打破并列本质上是同一个稳定策略的两种表达。6.2 “秩”这个概念比排序本身更值钱把秩想明白之后你会发现“排名”这个概念到处都是。数据库里的 RANK()、DENSE_RANK() 窗口函数本质上也是给有序结果集的每一行算一个名次统计里的分位数、百分位数说的是“小于某个观测值的比例”搜索引擎和推荐系统把相关内容排序后排名位置本身就是重要信号。秩排序虽然是个冷门排序但背后“数一数前面有多少个”的思维是很多数据处理场景共同的底座。从这个角度看花半小时把秩排序研究透一点都不亏。7. 动手复现之前边界用例、随机对拍和翻车点7.1 第一件事先跑边界用例我在本地验证秩排序时第一轮跑的永远是这几个用例空数组不能抛异常结果还是空数组单元素数组直接返回全部相同[5, 5, 5, 5]排序后不变这是稳定性测试的极端场景已经有序[1, 2, 3, 4, 5]验证不会越界或产生乱序完全逆序[5, 4, 3, 2, 1]最常见的反例素材包含负数比如 [-3, 7, -8, 0]秩排序只依赖比较不依赖数值范围所以应该正常工作混合大范围元素加入 Integer.MAX_VALUE 和 Integer.MIN_VALUE重点检查比较条件里有没有把相等误判成更小。这些用例覆盖了绝大部分隐藏 bug。我自己踩过的第一个坑就是在统计条件里写成 arr[j] arr[i]把相等的元素也算成“比我小”结果所有重复值的秩整体偏大输出直接乱掉。7.2 随机对拍让机器替你把所有路径跑一遍光靠手写用例远远不够。最可靠的验证是拿随机数组和 Java 标准库的 Arrays.sort 对拍生成一批随机数组分别用秩排序和标准排序然后逐位比较。代码不长Random random new Random(42); for (int size : new int[]{0, 1, 2, 10, 100}) { for (int t 0; t 1000; t) { int[] a random.ints(size, -1000, 1000).toArray(); int[] expected a.clone(); Arrays.sort(expected); rankSort(a); if (!Arrays.equals(a, expected)) { System.out.println(不匹配size size , t t); } } }建议固定随机种子这样出问题时能稳定复现。跑完 5 组规模、每组 1000 次随机对拍如果全部通过至少说明常见路径没有大问题。想再狠一点就把元素取值范围缩小比如限定在 [-2, 2] 之间取值这样可以强制产生大量重复元素专门考验稳定性处理。7.3 三个高频翻车点提前给你打预防针第一个翻车点是忘记把 sorted 数组拷贝回原数组。方法内部排得再漂亮原数组没变调用方拿到的还是乱序。这属于“看起来很对一测就挂”的经典错误。第二个翻车点是前面讲过的“线性探测空位”式补救。它看似绕开了覆盖问题实际却把重复元素的次序彻底打乱对拍测试最容易抓到的就是它。正确做法永远是在秩的计算阶段把并列元素拆开而不是在放置阶段找空位。第三个翻车点是自以为秩排序天然稳定。如果统计条件里没有 j i 这个 tie-break它面对重复元素根本无法完成排序面试时被追问一句“有重复值怎么办”很容易露馅。我建议把稳定版秩排序当成唯一版本记朴素版只作为理解过程的产品。7.4 一点个人体会带过几轮同学实现这个算法之后我发现大家普遍能在五分钟内写出双循环骨架却在重复元素上卡二三十分钟。这其实是好事一个看似冷门的排序算法恰好把“排序的本质是确定位置”和“稳定性的工程意义”这两个核心概念压在同一道题里。我后来在讨论算法时也喜欢用秩排序当引子它足够短可以当场写完又足够深能引出稳定性和复杂度两个大话题。建议你也别只读文章动手把朴素版、稳定版、两阶段版、in-place 版各写一遍再用对拍脚本跑一遍。写代码时盯着那行 tie-break 条件多问自己一句为什么 j i 能保证稳定想通这一句秩排序才真正变成你自己的东西。 
长河君 · 2026/10/16 3:47:40 · 阅读 1.2k 秩排序的原理与Java实现：从重复元素到稳定性解析
很多人第一次听到“秩排序”Rank Sort这个名字都会下意识把它归到“冷门排序”那一类。实际上它的核心思想简单到可以用一句话讲完给每个元素数一数数组里有多少个元素比它小这个数字就是它在最终有序序列里的位置然后把它直接放到对应下标上。没错排序这件事在这里被简化成了“数数”加“放位置”。我最初认真琢磨这个算法是因为A同学在讨论排序稳定性时顺手写了个按“比它小的元素个数”来排的玩具代码结果被重复元素折磨到怀疑人生。这篇文章就从这个朴素问题出发我用 Java 把秩排序从零实现一遍拆解重复元素如何处理、稳定性如何保证再把它和计数排序、快速排序等经典算法放在一起对比最后给你一份可以直接复现的测试清单。无论你是刚学数据结构的学生还是在准备算法面试这篇都适合你。1. 排序的底层逻辑给每个元素算一个“该待的位置”1.1 秩是什么从“排第几位”说起“秩”这个字在线性代数里通常和矩阵相关表示极大线性无关组的向量个数但在数据结构里我们可以理解得更朴素——“某个元素在一堆元素中从小到大排第几位”。比如 [50, 10, 20, 40, 30] 中10 是最小的它的秩是 020 前面只有一个 10秩是 130 的秩是 240 的秩是 350 的秩是 4。如果我把每个元素按自己的秩放到新数组的下标上就得到 [10, 20, 30, 40, 50]排序完成。这里的关键认识是排序的本质是给每个元素确定目标位置。插入排序、冒泡排序、快速排序都是通过不停地比较和交换让元素一步一步逼近目标位置而秩排序的思路完全不同——一次算准一次到位。它不做交换不搞递归只需要回答一个简单的问题在我之外还有多少个元素应该排在我前面正因为这个“先算位置、再放元素”的思路足够干净秩排序才经常被用来和“通过交换逼近位置”的传统排序作对比。很多讲排序原理的课程喜欢把它放在计数排序之前讲也是因为这个位置思想是理解计数排序、基数排序的天然跳板。1.2 把“数一数前面有几个人”写成代码计算一个元素 arr[i] 的秩最直接的办法就是遍历整个数组统计满足 arr[j] arr[i] 的 j 的个数int rank 0; for (int j 0; j arr.length; j) { if (arr[j] arr[i]) { rank; } }外层循环负责遍历每个元素内层循环负责给当前元素数“前面有多少个更小的”。每次数完arr[i] 的目标位置就是 rank。这样一个双重循环写下来你已经完成了能处理“所有元素互不相同”情况的秩排序的核心骨架。用生活场景类比就是一排同学按身高从低到高拍照每个人只需要知道自己前面站了几个比自己矮的人。站第 0 位的最矮站最后位的最高每个人的“前面人数”就是他的秩而照片站位就是按秩排出来的。2. 第一版 Java 实现直接数、直接放然后翻车2.1 最直观的写法往往问题最多顺着上面的思路我一开始写出来的版本长这样public static void rankSortNaive(int[] arr) { int n arr.length; int[] sorted new int[n]; for (int i 0; i n; i) { int rank 0; for (int j 0; j n; j) { if (arr[j] arr[i]) { rank; } } sorted[rank] arr[i]; } System.arraycopy(sorted, 0, arr, 0, n); }代码很简短先开一个和原数组等长的 sorted 数组对每个元素统计比它小的元素个数然后直接把元素放到 sorted 的对应下标。最后用 System.arraycopy 把结果拷回原数组保证调用之后原数组被真正排序。注意内层循环里 j 从 0 到 n-1包含 j i 的情况因为一个元素不可能小于自己所以这个比较是空操作不影响结果但比较次数会略微超过理论值这个我们在后面复杂度部分再说。如果数组元素全部不同这个版本是正确的。比如 [5, 2, 8, 1, 9]5 的秩是 22 的秩是 18 的秩是 31 的秩是 09 的秩是 4放到新数组后得到 [1, 2, 5, 8, 9]。问题在于一旦出现重复元素这个版本的逻辑就立刻崩溃。2.2 翻车现场两个相同元素抢同一个位置以 [2, 1, 1, 3] 为例我用上面的代码跑一遍第一个 1下标 1的秩是 0因为没有任何元素比它小第二个 1下标 2的秩仍然是 0因为两个 1 是相等关系用 arr[j] arr[i] 判定时相等元素之间不会互相计数2 的秩是 1因为它前面有两个 13 的秩是 3因为前面有三个元素比它小。两个 1 都想去 0 号位后写的那一个会把先写的覆盖掉。我实际运行的结果是sorted 数组最终变成了一个包含 0 默认值的乱序状态比如 [1, 0, 0, 3]完全不可用。到这里A同学的第一反应是那我在放置之前判断一下如果 rank 位置被占了就往后找第一个空位不就不会覆盖了吗这个“找空位塞进去”的想法非常自然我试过之后反而发现了一个更有意思的坑。加一个 occupied 布尔数组做线性探测int pos rank; while (pos n occupied[pos]) { pos; } sorted[pos] arr[i]; occupied[pos] true;对 [2, 1, 1, 3]这个探测版本的结果是 [1, 2, 1, 3]。第二个 1 的秩是 0当 0 号位被第一个 1 占用后它一路探测到 2 号位于是 1 被插到了 2 和 3 之间顺序彻底坏了。表面上它没有覆盖实际上“谁先谁后”的逻辑已经被破坏得面目全非。这个案例很好地说明了一个结论重复元素处理关键不是“放置时怎么找空位”而是“计算秩的时候就要把相等元素拆开”。3. 重复元素与稳定性真正的考点在这一行条件里3.1 修复把“出现得更早”也计入秩重复元素的本质问题是相等元素之间没有定义先后次序。如果两个 1 都认为自己该站第 0 位它们之间必须有一个规则来分先后。最简单的规则就是利用原始下标在原数组中下标更小的那个在排序后依然站在前面。代码改动非常小把统计条件从 arr[j] arr[i] 改成arr[j] arr[i] || (arr[j] arr[i] j i)含义就是统计“比当前元素小”的元素个数再加上“和当前元素相等但原始下标比我小”的元素个数。这样一来每个元素的秩都是独一无二的并且恰好是 [0, n-1] 的一个完整排列。回到 [2, 1, 1, 3]第一个 1下标 1没有更小的也没有更早的相等元素秩是 0第二个 1下标 2没有更小的但有一个更早的相等元素下标 1秩是 12下标 0有两个 1 比它小秩是 23下标 3有三个元素比它小秩是 3。按秩放回去得到 [1, 1, 2, 3]而且两个 1 的相对顺序和原数组保持一致。这就是稳定排序。修正后的完整代码public static void rankSort(int[] arr) { int n arr.length; int[] sorted new int[n]; for (int i 0; i n; i) { int rank 0; for (int j 0; j n; j) { if (arr[j] arr[i] || (arr[j] arr[i] j i)) { rank; } } sorted[rank] arr[i]; } System.arraycopy(sorted, 0, arr, 0, n); }3.2 稳定性的工程意义多关键字排序的基石如果你只是给一堆整数排序稳定性看起来无关紧要反正相等的整数长一个样。但在工程里排序对象往往是带多个字段的记录比如先按班级排序再按学号排序。如果第二趟排序不稳定第一趟按班级排好的顺序就可能被打乱。稳定排序保证同一班级内部的相对顺序由上一趟排序的结果决定最终多关键字排序才是正确的。很多教材讲秩排序时都默认元素互不相同把重复问题一句带过。但实际写代码时重复元素几乎是必然出现的。我见过不少同学能写出秩排序的骨架被追问“有重复元素怎么办”时却答不上来。所以如果你是在准备面试秩排序这个点真正值得记住的不是双循环而是这一行 tie-break 条件以及它和稳定性的关系。顺带一提计数排序里“逆序遍历原数组”的放置手法本质上也是在用同样的思路维持稳定性两种算法在这里是相通的。4. 两阶段设计把“计算秩”和“搬移数据”拆开4.1 拆开之后调试和复用都变容易了上面的单循环版本是“边算边放”代码短但有一个缺点一旦结果不对很难判断是“秩算错了”还是“放的位置错了”。把两步拆开先算完所有秩再统一搬移调试体验完全不一样public static int[] computeRank(int[] arr) { int n arr.length; int[] rank new int[n]; for (int i 0; i n; i) { for (int j 0; j n; j) { if (arr[j] arr[i] || (arr[j] arr[i] j i)) { rank[i]; } } } return rank; } public static void rankSortTwoPhase(int[] arr) { int[] rank computeRank(arr); int[] sorted new int[arr.length]; for (int i 0; i arr.length; i) { sorted[rank[i]] arr[i]; } System.arraycopy(sorted, 0, arr, 0, arr.length); }我之所以推荐这种写法不只是为了调试。rank 数组本身有独立的信息量相当于“每个元素在最终有序序列中的位置表”。你可以打印它、保存它、给它做进一步统计。很多真实系统在做分布式排序时第一步就是给数据分区并估算每个元素所在的名次再按名次把数据路由到对应节点思路和这个两阶段完全一致。实际工程里把“计算”和“执行”拆开往往是让代码可控、可测试的最简单手段。4.2 in-place 彩蛋省掉 sorted 数组的版本既然 rank 数组在加了 tie-break 之后是 [0, n-1] 的一个排列我们其实可以借助它直接在原数组里把元素放到位不需要 sorted 数组public static void rankSortInPlace(int[] arr) { int n arr.length; int[] rank computeRank(arr); for (int i 0; i n; ) { if (rank[i] i) { i; } else { int j rank[i]; int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; int tr rank[i]; rank[i] rank[j]; rank[j] tr; } } }思路是如果当前下标 i 上的元素它的秩不是 i说明它不该待在这里那就把它换到 rank[i] 位置换过去之后把位置表也同步交换。整个过程像顺着“每个元素指给自己的位置”走迷宫最终所有 rank[i] i数组也就位了。这个版本省掉了一个 sorted 数组但 rank 数组仍然占 O(n) 空间所以空间复杂度的量级没变只是常数更小。代码可读性明显下降我在实际项目里几乎不用它纯当算法趣味研究一下。5. 复杂度账本O(n²) 的时间换来的是什么5.1 时间都花在双重循环上秩排序的时间开销集中在计算秩的双重循环上外层要处理 n 个元素内层要把每个元素和所有其他元素比较一遍总共是 O(n²) 次比较。实际代码里内层循环还包含了一次和自己比较的空操作但常数不影响量级。关键在于不管输入是正序、逆序还是完全随机比较次数都固定是 O(n²)因为每个元素必须亲自和所有其他元素比过才知道自己的位置。这个特性决定了它是“非自适应”排序不像插入排序那样面对接近有序的数据会自动变快。空间上边算边放的版本需要 sorted 数组O(n) 额外空间两阶段版本还需要 rank 数组同样是 O(n)。稳定性方面加上 tie-break 之后秩排序是稳定排序朴素版在重复元素下根本跑不出正确结果稳定性更是无从谈起。5.2 和主流排序算法的对比算法平均/最坏时间额外空间稳定性一句话评价秩排序O(n²)O(n)可稳定一次算准位置比较次数固定冒泡排序O(n²)O(1)稳定交换频繁常数大选择排序O(n²)O(1)不稳定交换少但比较一样多插入排序O(n²)O(1)稳定接近有序时接近 O(n)快速排序O(n log n)O(log n)不稳定实际综合表现最佳的比较排序归并排序O(n log n)O(n)稳定稳定排序中的首选计数排序O(n k)O(k)稳定只适合整数且值域不大的场景从表里能直观看到秩排序的时间复杂度没有任何优势空间也不是最优。那它存在的意义是什么我的答案有两个。第一它是理解“位置等于名次”这个抽象概念的极好入口外排序、并行排序、数据库查询里的排序算子都依赖“先给元素算名次再搬运”这个框架。第二它的常数非常小内层循环就是一次整数比较没有递归、没有额外对象分配在 n 很小的时候它和工程级快速排序的差距并不大代码却简单得多。5.3 说实话什么时候用它什么时候别用我的建议很直接教学、入门、理解排序本质时秩排序值得完整实现一遍尤其是亲自跑一跑重复元素翻车的案例数据量小几十以内且要求代码极简时可以拿它当兜底排序数据量一旦上百上千立刻换 Java 标准库的 Arrays.sort它内部会根据数据规模自动选择双轴快排或归并排序的思路你手写的秩排序完全没有胜算如果数据是有限范围内的整数更优的选择是计数排序下一节细说。另外提一个有意思的点秩排序的每个元素的秩互不影响天然的可以并行计算——你可以把数组切给多个线程各算各的名次。但 n² 的比较次数扛不住数据规模增长并行也只是减缓衰减不是出路。真要做大规模并行排序业界用的是采样分区那一套思路。6. 从秩排序到计数排序一次顺理成章的升级6.1 两两比较太慢了换一个“报数”思路秩排序用两两比较来数“比我小的元素个数”代价是 O(n²)。换个角度如果数组里的值只是非负整数而且值域不大根本不需要两两比较。直接开一个大数组按下标统计每个值出现几次再做前缀和每个值的“起止位置区间”就出来了。前缀和本身就是“小于等于某个值的元素有多少个”这正是秩的批量版本。比如 [2, 1, 1, 3]值域 [0..3]频次数组 count [0, 2, 1, 1]前缀和 [0, 2, 3, 4]含义是“小于等于 v 的元素共有 count[v] 个”于是值 1 占据位置 0 到 1值 2 占据位置 2 到 2值 3 占据位置 3 到 3。这就是计数排序一个循环统计频次一个循环做前缀和最后逆序遍历原数组把元素放到对应位置全程 O(n k)k 是值域宽度。Java 实现如下public static void countingSort(int[] arr, int maxValue) { int[] count new int[maxValue 1]; for (int v : arr) { count[v]; } for (int i 1; i maxValue; i) { count[i] count[i - 1]; } int[] sorted new int[arr.length]; for (int i arr.length - 1; i 0; i--) { int v arr[i]; sorted[--count[v]] v; } System.arraycopy(sorted, 0, arr, 0, arr.length); }注意放元素时要倒着遍历原数组同一个值有多个元素时逆序放置可以保证先出现在原数组的元素落在靠前位置从而保持稳定性。这一步和秩排序里用 j i 打破并列本质上是同一个稳定策略的两种表达。6.2 “秩”这个概念比排序本身更值钱把秩想明白之后你会发现“排名”这个概念到处都是。数据库里的 RANK()、DENSE_RANK() 窗口函数本质上也是给有序结果集的每一行算一个名次统计里的分位数、百分位数说的是“小于某个观测值的比例”搜索引擎和推荐系统把相关内容排序后排名位置本身就是重要信号。秩排序虽然是个冷门排序但背后“数一数前面有多少个”的思维是很多数据处理场景共同的底座。从这个角度看花半小时把秩排序研究透一点都不亏。7. 动手复现之前边界用例、随机对拍和翻车点7.1 第一件事先跑边界用例我在本地验证秩排序时第一轮跑的永远是这几个用例空数组不能抛异常结果还是空数组单元素数组直接返回全部相同[5, 5, 5, 5]排序后不变这是稳定性测试的极端场景已经有序[1, 2, 3, 4, 5]验证不会越界或产生乱序完全逆序[5, 4, 3, 2, 1]最常见的反例素材包含负数比如 [-3, 7, -8, 0]秩排序只依赖比较不依赖数值范围所以应该正常工作混合大范围元素加入 Integer.MAX_VALUE 和 Integer.MIN_VALUE重点检查比较条件里有没有把相等误判成更小。这些用例覆盖了绝大部分隐藏 bug。我自己踩过的第一个坑就是在统计条件里写成 arr[j] arr[i]把相等的元素也算成“比我小”结果所有重复值的秩整体偏大输出直接乱掉。7.2 随机对拍让机器替你把所有路径跑一遍光靠手写用例远远不够。最可靠的验证是拿随机数组和 Java 标准库的 Arrays.sort 对拍生成一批随机数组分别用秩排序和标准排序然后逐位比较。代码不长Random random new Random(42); for (int size : new int[]{0, 1, 2, 10, 100}) { for (int t 0; t 1000; t) { int[] a random.ints(size, -1000, 1000).toArray(); int[] expected a.clone(); Arrays.sort(expected); rankSort(a); if (!Arrays.equals(a, expected)) { System.out.println(不匹配size size , t t); } } }建议固定随机种子这样出问题时能稳定复现。跑完 5 组规模、每组 1000 次随机对拍如果全部通过至少说明常见路径没有大问题。想再狠一点就把元素取值范围缩小比如限定在 [-2, 2] 之间取值这样可以强制产生大量重复元素专门考验稳定性处理。7.3 三个高频翻车点提前给你打预防针第一个翻车点是忘记把 sorted 数组拷贝回原数组。方法内部排得再漂亮原数组没变调用方拿到的还是乱序。这属于“看起来很对一测就挂”的经典错误。第二个翻车点是前面讲过的“线性探测空位”式补救。它看似绕开了覆盖问题实际却把重复元素的次序彻底打乱对拍测试最容易抓到的就是它。正确做法永远是在秩的计算阶段把并列元素拆开而不是在放置阶段找空位。第三个翻车点是自以为秩排序天然稳定。如果统计条件里没有 j i 这个 tie-break它面对重复元素根本无法完成排序面试时被追问一句“有重复值怎么办”很容易露馅。我建议把稳定版秩排序当成唯一版本记朴素版只作为理解过程的产品。7.4 一点个人体会带过几轮同学实现这个算法之后我发现大家普遍能在五分钟内写出双循环骨架却在重复元素上卡二三十分钟。这其实是好事一个看似冷门的排序算法恰好把“排序的本质是确定位置”和“稳定性的工程意义”这两个核心概念压在同一道题里。我后来在讨论算法时也喜欢用秩排序当引子它足够短可以当场写完又足够深能引出稳定性和复杂度两个大话题。建议你也别只读文章动手把朴素版、稳定版、两阶段版、in-place 版各写一遍再用对拍脚本跑一遍。写代码时盯着那行 tie-break 条件多问自己一句为什么 j i 能保证稳定想通这一句秩排序才真正变成你自己的东西。