企业官网建设流程全解析

很多人第一次听到“秩排序”（Rank Sort）这个名字，都会下意识把它归到“冷门排序”那一类。实际上它的核心思想简单到可以用一句话讲完：给每个元素数一数，数组里有多少个元素比它小，这个数字就是它在最终有序序列里的位置，然后把它直接放到对应下标上。没错，排序这件事，在这里被简化成了“数数”加“放位置”。我最初认真琢磨这个算法，是因为A同学在讨论排序稳定性时，顺手写了个按“比它小的元素个数”来排的玩具代码，结果被重复元素折磨到怀疑人生。这篇文章就从这个朴素问题出发：我用 Java 把秩排序从零实现一遍，拆解重复元素如何处理、稳定性如何保证，再把它和计数排序、快速排序等经典算法放在一起对比，最后给你一份可以直接复现的测试清单。无论你是刚学数据结构的学生，还是在准备算法面试，这篇都适合你。

1. 排序的底层逻辑：给每个元素算一个“该待的位置”

1.1 秩是什么：从“排第几位”说起

“秩”这个字，在线性代数里通常和矩阵相关，表示极大线性无关组的向量个数；但在数据结构里，我们可以理解得更朴素——“某个元素在一堆元素中从小到大排第几位”。比如 [50, 10, 20, 40, 30] 中，10 是最小的，它的秩是 0；20 前面只有一个 10，秩是 1；30 的秩是 2；40 的秩是 3；50 的秩是 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 的秩是 2，2 的秩是 1，8 的秩是 3，1 的秩是 0，9 的秩是 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，因为它前面有两个 1；
• 3 的秩是 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），秩是 1；
• 2（下标 0）：有两个 1 比它小，秩是 2；
• 3（下标 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 和主流排序算法的对比

从表里能直观看到，秩排序的时间复杂度没有任何优势，空间也不是最优。那它存在的意义是什么？我的答案有两个。第一，它是理解“位置等于名次”这个抽象概念的极好入口，外排序、并行排序、数据库查询里的排序算子，都依赖“先给元素算名次再搬运”这个框架。第二，它的常数非常小：内层循环就是一次整数比较，没有递归、没有额外对象分配；在 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 能保证稳定？想通这一句，秩排序才真正变成你自己的东西。