从Java sort到MIPS汇编：彻底吃透排序算法与结构体排序

1. 从一次日常开发需求说起：为什么所有语言都绕不开Sort

写业务代码写久了，你会发现一个规律：几乎任何系统里都躲不开"排序"这件事。订单要按时间倒序排列，排行榜要按分数从高到低，审批列表要按状态和优先级来排。哪怕你只是写一个让用户查账的小接口，也有可能需要把交易记录按金额从大到小列出来。这些需求背后都指向同一个核心操作——sort。

这里的sort不是单指某个语言的某个函数，而是一整套"让数据按照某种规则变得有序"的思维和方法。再看这次项目的热词，很有意思：java sort、mips mars、.data array、sort函数排序结构体，这几个词凑在一起，其实把排序这个话题从应用层一路拉到了底层实现。毕竟你平时在Java里写Collections.sort()只花一秒钟，但这一秒钟背后，编译器把它翻译成了什么、CPU怎么执行比较和交换、内存里那些数据究竟是怎么被搬来搬去的，很多人并没有真正想明白。

所以这篇博文我想换个聊法：不单纯讲Java里怎么调sort，也不单纯讲排序算法原理，而是把这两层东西串起来。你会看到同样的排序逻辑，在Java高层API里怎么写、在MIPS汇编里怎么一步步实现、在给结构体排序时又有哪些容易踩的坑。我尽量用实际能跑的代码说话，也把我在真实项目里踩过的坑拿出来分享。适合刚学完基础语法但想深入理解排序本质的人，也适合准备面试、需要把"算法"和"工程实现"打通的人。

2. 排序这事儿的本质：从一组乱序数组讲起

2.1 变量、数组和结构体：一层比一层复杂的排序对象

如果只看"排序"这个动作本身，它其实非常朴素：把一组数据按预定义的规则重新排列。但难点从来不在"排序"这两个字上，而在于待排序的数据长什么样。

先看最基础的情况——排一个整数数组。比如热词里提到的array: .word 3, 10, 8, 2, 5, 2, 3，这就是MIPS汇编里常见的一个数据段声明，含义是在内存里连续存放7个32位整数。排序这种数组，本质上就是内存里的值两两比较、互换位置，比较规则是数值大小，交换单位是单个int。这种场景最简单，只要搞清楚比较和交换两个动作就行。

稍微升级一点，排序对象变成一个类的实例，比如Java里的一个订单对象：

class Order { String orderId; double amount; int status; long createTime; }

这时候问题就来了：两个订单对象之间，什么算"大"，什么算"小"？是按金额比，还是按时间比？如果金额相同，要不要再看时间？这就是"结构体排序"或者说"对象排序"的核心难点。你传给排序函数的不是一个简单的int，而是一堆字段的组合，排序规则完全取决于业务上怎么定义"先后顺序"。

从数组到结构体，看起来只是数据形态变复杂了，但它带来的思考方式变化是本质性的：排序不再是语言帮你做好的"最小功能"，而是要求你先定义清楚"序"是什么。我在实际项目里见过太多因为排序规则没定义清楚而返工的情况，所以我想先把这个底层逻辑点透——无论你用的是Java、C还是汇编，排序的第一步永远是数学意义上的一一映射规则，然后才是代码意义上的比较器逻辑。

2.2 排序结果的不变性：稳定性这个概念别忽略

聊到排序，一定绕不开"稳定性"。但很多新手甚至一些工作两年左右的开发者，对稳定性的理解还停留在"知道有这么个概念、记不住怎么用"的程度。我换个角度解释：稳定排序的意思是，当两个元素在排序规则下被认为"相等"时，它们在排序前的前后顺序在排序后依然保持。

举个真实业务例子。后台管理系统里有一个客户列表，先按注册时间排好序，然后要求再按城市分组展示。如果你用的是不稳定排序，那么第二次排序时，同一座城市内的客户顺序可能会被打乱，用户看到的列表就不是"注册时间由早到晚"了。但如果你用的是稳定排序，第二次排序后，注册时间顺序会原样保留。

那平常我们调用的sort到底稳不稳定？要看具体实现。Java的Arrays.sort对基本类型数组用的是双轴快速排序，它是不稳定的——不过基本类型数组也不存在"相同元素"的概念，稳定不稳定无所谓；对对象数组，Java用的则是TimSort或者类似于归并排序的实现，是稳定的。MIPS汇编里你自己写排序，那就完全取决于你写的是选择排序、冒泡排序还是别的什么，稳定性和性能都归你负责。搞清楚这个区别很重要，因为面试和实坑里都会遇到。

3. Java里的sort全家桶：Api调用、Comparator与结构体排序

3.1 Arrays.sort和Collections.sort怎么选

回到Java这个大家日常使用频率最高的语言。Java里给数据排序的门面接口主要有两个：Arrays.sort和Collections.sort。很多初学者搞不清二者的区别，其实很好记：Arrays是给数组用的，Collections是给List这类集合用的。底层逻辑其实是同一套，Collections.sort底层就是把List先转成数组，排完序再写回List。

具体代码如下：

import java.util.Arrays; import java.util.Collections; import java.util.List; public class SortDemo { public static void main(String[] args) { int[] intArray = {3, 10, 8, 2, 5, 2, 3}; Arrays.sort(intArray); System.out.println(Arrays.toString(intArray)); // [2, 2, 3, 3, 5, 8, 10] List<Integer> list = Arrays.asList(3, 10, 8, 2, 5, 2, 3); Collections.sort(list); System.out.println(list); // [2, 2, 3, 3, 5, 8, 10] } }

这里的排序规则很简单：基本类型的数组用数值的自然顺序升序排列；对象类型需要用Comparable或者Comparator来指定规则。默认情况下，如果List里的元素是Integer、String这种实现了Comparable接口的类，那么直接调用Collections.sort就能用它们的自然顺序进行排序。Integer的自然顺序是数值大小，String的自然顺序是字典序。

但如果List里的元素是自定义对象，比如订单、用户、商品，没有实现Comparable，那么直接调用Collections.sort(list)会直接抛ClassCastException。解决途径有两个：一是让类实现Comparable接口，二是单独传入Comparator实例。两种方案都有应用场景，我一般优先用Comparator，因为排序规则属于外部策略，改起来更灵活，不用动实体类代码。

3.2 结构体排序：Comparator到底该怎么写

现在到了热词里最核心的"sort函数排序结构体"。假设有这样一个需求：根据订单金额降序排列，如果金额相同，则按创建时间升序排列。Java里用Comparator表达是这样的：

import java.util.*; public class OrderSortDemo { static class Order { String orderId; double amount; long createTime; Order(String orderId, double amount, long createTime) { this.orderId = orderId; this.amount = amount; this.createTime = createTime; } @Override public String toString() { return "Order{" + orderId + ", " + amount + ", " + createTime + "}"; } } public static void main(String[] args) { List<Order> orders = new ArrayList<>(); orders.add(new Order("A001", 100.5, 1000L)); orders.add(new Order("A002", 80.2, 1100L)); orders.add(new Order("A003", 100.5, 900L)); orders.add(new Order("A004", 200.0, 1200L)); orders.sort(Comparator .comparingDouble((Order o) -> o.amount) .reversed() .thenComparingLong(o -> o.createTime)); for (Order o : orders) { System.out.println(o); } } }

这段代码值得拆开讲一下。Comparator.comparingDouble是第一个比较键，它提取订单金额；reversed表示降序；thenComparingLong是次级排序键，金额相同时按createTime升序。这种链式写法最大的好处是直观，一行代码把多级排序规则说清楚了，而且不会出现把两级规则混在一个compare方法里然后写错if-else的尴尬。

那如果不用链式写法，用传统的compare方法实现一遍，你会更直观地理解排序规则到底是怎么生效的：

orders.sort((o1, o2) -> { if (o1.amount != o2.amount) { return Double.compare(o2.amount, o1.amount); // 金额降序 } return Long.compare(o1.createTime, o2.createTime); // 时间升序 });

这里Double.compare和Long.compare都是Java 7以后引入的静态方法，专门用于在Comparator里比较基本类型封装值，避免了手写大于小于判断时的精度问题和低级错误。我强烈建议所有人在排序相关代码里使用compare方法，而不是写if (a > b) return 1;这样的手写判断。原因嘛，等你遇到double类型比较出现NaN或者精度丢失的时候就会明白了。

还有一个实际开发中常见的坑：Comparator的reversed()方法只反转前一个比较器的结果，如果你在thenComparing之后调用reversed()，它反转的是整个链。想"金额降序+时间降序"和想"金额降序+时间升序"写出来的代码完全不同。刚从C#或者Python转过来的人特别容易在这里翻车，我见过不止一次线上排序结果和预期完全相反的事故。

3.3 稳定性和性能：Java底层到底做了哪些事

Java的Arrays.sort在被调用时，底层会做一次类型检查。如果排序的是对象数组，它会使用TimSort，这是一种把归并排序和插入排序结合起来的混合排序算法，时间复杂度在最坏情况下是O(n log n)，而且稳定。如果是基本类型数组，则使用DualPivotQuicksort（双轴快速排序），平均情况下比TimSort更快，但不稳定。

这就是为什么你应该尽量用基本类型数组做性能敏感排序，而排序对象本身不要求稳定的时候，可以按实际需要选择。比如一个几百万规模的基础数据排序，用Arrays.sort基本类型版本，实测性能远好于用Collections.sort包装后的List排序，因为后者经历了自动装箱和拆箱、临时数组拷贝等额外开销。

我自己在做一个大数据量的标签去重排序任务时，就专门把Integer[]换成了int[]，把List 换成了原始数组加快速排序，整个链路耗时从接近10秒降到了1秒左右。很多场景下排序慢不是因为算法不行，而是因为你在排序前做了一堆无谓的对象包装。

4. 再来看看汇编的世界：MIPS MARS里手写一个排序

4.1 MARS环境和.data段：底层数据是如何存放的

如果前面Java部分聊的是"怎么优雅地调用别人写好的排序"，那MIPS汇编这部分聊的就是"排序到底是怎么一步一步走出来的"。MARS是教学中很常用的MIPS模拟器，可以在没有真实硬件的情况下演示MIPS指令的执行过程。虽然实际工作里你大概率不会用汇编写排序，但搞清楚汇编层面的数据操作对视障有特别大帮助。

使用MARS时，代码通常分两个段：.data段存放初始化的数据，.text段存放指令。开头热词里的array: .word 3,10,8,2,5,2,3就是.data段里声明了一个标签array，后面跟着7个word（32位整数）。注意，MARS从高地址向低地址或者从低地址向高地址分配空间取决于配置，但默认情况下这些数据是连续存放的。这里的3,10,8,2,5,2,3其实就是我们要排序的原始数组，和你在Java里int[] arr = {3,10,8,2,5,2,3}完全等价。

在MIPS里访问数组元素，核心靠基址寄存器+偏移量。比如lw $t0, 0($s0)表示从$s0寄存器存放的地址开始，读取4个字节（一个word）到$t0。如果$s0存的是array的起始地址，那么lw $t0, 4($s0)读到的就是array[1]的值，也就是10。这就是为什么在汇编里写"数组下标"需要自己换算成字节偏移量：下标1对应的字节偏移是4，下标2对应8，以此类推。很多初学者在这里容易搞混，写成lw $t0, 1($s0)，拿到的数据完全不对。

4.2 排序流程：冒泡排序的汇编级实现

在汇编里写排序，我一般建议先从冒泡排序开始，因为逻辑最单一：外层循环控制总共需要多少轮比较，内层循环从头到尾两两比较，如果前一个大于后一个就交换。整个过程不需要额外的缓存区，最省内存。下面给出一个可在MARS里直接运行的完整冒泡排序示例，用来把数组{3,10,8,2,5,2,3}排成升序。

.data array: .word 3, 10, 8, 2, 5, 2, 3 size: .word 7 msg: .asciiz "Sorted array: " .text .globl main main: la $s0, array # $s0 = 数组起始地址 lw $s1, size # $s1 = 数组长度 7 li $t0, 0 # 外层循环变量 i = 0 outer_loop: slt $t1, $t0, $s1 # i < size? beq $t1, $zero, print # 如果 i >= size，排序完成，去输出 li $t2, 0 # 内层循环变量 j = 0 sub $t3, $s1, $t0 # size - i sub $t3, $t3, 1 # size - i - 1，内层比较的剩余次数 inner_loop: slt $t4, $t2, $t3 # j < size - i - 1? beq $t4, $zero, outer_next sll $t5, $t2, 2 # 字节偏移 = j * 4 add $t6, $s0, $t5 # 当前元素地址 array + j*4 lw $t7, 0($t6) # 读取 array[j] lw $t8, 4($t6) # 读取 array[j+1] slt $t9, $t8, $t7 # array[j+1] < array[j] ? beq $t9, $zero, no_swap sw $t8, 0($t6) # 交换：把小的放到前面 sw $t7, 4($t6) no_swap: addi $t2, $t2, 1 # j++ j inner_loop outer_next: addi $t0, $t0, 1 # i++ j outer_loop print: la $s0, array lw $s1, size li $v0, 4 la $a0, msg syscall li $t0, 0 print_loop: slt $t1, $t0, $s1 beq $t1, $zero, exit sll $t5, $t0, 2 add $t6, $s0, $t5 lw $a0, 0($t6) li $v0, 1 syscall li $a0, 32 li $v0, 11 syscall addi $t0, $t0, 1 j print_loop exit: li $v0, 10 syscall

这段代码的执行顺序是这样的：初始化$s0为数组起始地址、$s1为数组长度；进入外层循环后，每轮内层循环都把相邻两个元素比较一次，如果顺序不对就交换；一轮结束后，最大的元素就像气泡一样冒到末尾；下一轮就可以少比较一次；循环直到所有元素有序。这段代码在MARS里直接按F5运行，会在Console中打印"Sorted array: 2 2 3 3 5 8 10"。

一个我在带新人时反复强调的细节是：MARS的syscall调用约定是$v0存放系统调用号，$a0存放第一个参数。打印整数的调用号是1，打印字符串是4，打印单个字符是11，退出程序是10。如果你把$v0设错，或者寄存器没有在调用前给对参数，屏幕上要么什么都不输出，要么直接报运行时错误，排错排查需要逐行检查。更隐蔽的是，syscall会修改$v0和$a0，如果你在循环里要长期保持某个值，千万别放在这两个寄存器里，否则每次syscall之后它就变成新的返回值了。

4.3 汇编排序和Java排序，差别到底在哪

把Java的Collections.sort和上面这段MIPS冒泡排序放在一起对比，你会发现很有意思的事情。Java里一行代码就搞定了，但这一行代码背后，JVM要做类型检查、调用TimSort或DualPivotQuicksort、比较元素、必要时交换引用。而MIPS里每一步操作都需要你显式地告诉CPU：加载这个值到寄存器，比较两个寄存器，根据比较结果跳转，把结果存回内存。

Java带给你的抽象是"排序"这个动作本身，你只关心排序规则；MIPS带给你的抽象几乎为零，你得亲手搭建"比较-交换-循环控制"这些积木，而且每种数据布局都要自己设计。这就是为什么我建议有时间的开发者都去手写一遍汇编排序：它逼你把"计算机到底是怎么执行排序的"这件事彻底想明白。

从性能角度看，现代CPU有分支预测、乱序执行、多级缓存，一个简单的冒泡排序在Java里编译成JIT机器码后，很可能比你在MIPS模拟器里跑的汇编代码快好几个数量级。这不代表汇编没用了，而是说明算法的工程落地比"用低级语言写"更复杂。理解底层，不等于凡事都要用底层去做。

5. 着手排错之前，先看点排序算法在实战里的选择逻辑

5.1 时间复杂度和空间复杂度：面试和架构都要用到

排序算法的时间复杂度决定了它在大数据量下的表现。对随机数据来说，快速排序的期望时间复杂度是O(n log n)；归并排序稳定且稳定地为O(n log n)；冒泡排序和插入排序最坏都是O(n²)，但数据量小的时候插入排序因为有极低的常数因子，反而可能比快排还快。所以Java的TimSort会在数据量小于某个阈值时退化为二分插入排序，这就是工程实践对理论算法做的权衡。

我整理了一个常用的对比表，方便你查阅时一目了然：

这里最容易被面试官追问的是：为什么快速排序最坏会退化成O(n²)？答案和基准值的选择有关。如果每次选的基准值都是当前区间的最小或最大值，分区就极度不平衡，递归深度变成n，整体退化为平方级。解决办法包括随机选择基准值、三数取中法等。Java里的DualPivotQuicksort使用双轴和三数取中策略来避免这种情况，工程上非常稳健。

5.2 数据量小时该用哪种：一个真实的心情测试

我在做一个小工具时遇到这样一个场景：数据量最多不超过20个元素，但每次请求都要排序一次，而且要求排序结果绝对稳定。当时我第一反应是调用Collections.sort，这个选择本身没问题，TimSort对这种小规模数据做了大量优化，性能非常好，代码也不用多写。但我也顺手测了一下手写插入排序和冒泡排序的表现，结果很有意思：在大约20个元素的时候，插入排序和TimSort的耗时几乎一样，冒泡排序稍慢一点但可以接受；但数据量超过1万后，冒泡排序的性能急剧下降，需要好几秒才能完成一次排列，而TimSort几乎瞬时。

从这个测试我得到一个判断规则：如果你的业务场景数据规模永远很小（比如几十个以内），任何一种排序算法差异都不大，优先关注代码可读性和稳定性；如果数据量可能到十万级甚至千万级，老老实实用语言自带的高级排序实现，别自己造轮子。除非你需要实现一个排序算法练手，或者业务实在对内存使用有极端的限制，否则在Java里手写排序九成情况下不是聪明的决定。

5.3 自定义比较器写错了，排序结果“看起来对但实际不对”

这个坑必须单独拿出来说。很多时候你的排序结果表面上没有报错，但仔细一核对，顺序却和预期不一致。最常见的原因是compare方法没有满足反身性、对称性和传递性。反身性要求compare(x, x) == 0；对称性要求compare(x, y)和compare(y, x)符号相反；传递性就是如果x<y且y<z，那么x<z。任何一个条件不满足，排序算法就可能出现诡异的乱序，而且不同的算法表现出不同的错法，特别难排查。

我记得有一次在开发时排序一批文件，按文件名排序，但文件名里有数字部分，比如"file2"、"file10"。默认字符串排序会让"file10"排在"file2"前面，因为我们想要"自然排序"，需要比较器提取数字部分再比较。结果我第一次写的比较器只提取了第一个数字前面的部分，没有考虑同一个文件名里出现多个数字的情况，排出来的顺序偶尔对、偶尔错，找了好几个小时才定位到是比较器逻辑不严谨。

这种问题用文字描述很难精准排查，建议方式是：写一小段测试数据，把自定义Comparator单独跑一遍，打印每一对比较结果，人工核对是否符合预期。尤其是Compare方法里同时包含中文、英文、数字、null值这些边界条件时，更要小心。Comparator里对null的处理默认是直接抛NullPointerException的，但业务数据中字段为null的情况太常见了，你需要显式地定义null值的排序位置。用Comparator.nullsFirst(...)或Comparator.nullsLast(...)包装一层是最省事的方案。

6. 排序问题的排查技巧实录：我在实践中攒下的一套方法

6.1 先打印再排序：调试排序问题最笨但最有效的方法

遇到排序结果不对时，不少人第一反应是上网搜"为什么我的sort没有生效"，然后越看越乱。我的做法很朴素：先把排序前的原始数据、排序用的比较器、排序后的结果，分别打印出来，一一对照。一旦你看到原始数据是什么样的，比较器提取出来的排序键是什么，排序后数据怎么变位的，绝大多数问题都会暴露出来。

orders.forEach(o -> System.out.println( "id=" + o.orderId + ", amount=" + o.amount + ", time=" + o.createTime ));

打印时注意别只印整个对象，如果你的实体类没有重写toString，打印出来的可能是一串内存地址，那等于白打。重写一个toString只显示排序相关的几个字段，或者干脆打印排序键列表，效率会高很多。我自己就吃过这个亏，对象没有toString，打出来全是Order@762efe5d，排查效率极低。

6.2 排查Comparator反给错了方向怎么办

有些时候你调试时发现排序结果完全反了，第一反应是"比较器写反了"。确实，(o1, o2) -> o1 - o2是升序，(o2, o1) -> o1 - o2也是升序，但如果你写的是(o1, o2) -> o2 - o1就是降序，这两个方向很容易搞混。我建议先在代码里注释清楚：哪个返回负值代表o1排在o2前面，哪个返回正值代表相反。不要等到上线了再去猜。

还有一点容易踩坑：如果要排的是long类型的字段，千万别写成return (int)(o1.createTime - o2.createTime)。createTime的差可能超过int的表示范围，导致溢出，排序结果完全错乱。一定使用Long.compare(o1.createTime, o2.createTime)。

6.3 大型排序任务出现OutOfMemoryError怎么办

排序本身基本不产生额外的大对象分配，但有些场景会在排序前或排序中产生大量临时对象。比如对一个很大的List调用Collections.sort，底层需要把List转成数组，这个数组会占用额外的内存；如果List本身是LinkedList包装了很多节点对象，复制数组的开销会更大。遇到OutOfMemoryError，先确认JVM堆内存设置是否合理，再用内存分析工具看一下是哪些对象撑爆了堆，别一上来就怀疑是排序算法的问题。

如果确认是排序过程内存吃紧，可以考虑直接用Arrays.sort对原始数组排序，尽量复用已有的数组，避免复制。List.sort的内部实现其实也是先调用toArray再排序再写回，所以如果你对性能要求极高，直接操作数组永远是最省内存的方式之一。

6.4 并行排序什么时候能用

Java 8以后提供了Arrays.parallelSort，它利用Fork/Join框架把排序任务拆分到多个线程并行执行。这个方案的性能提升不是免费的——它在线程调度和任务拆分上有额外开销，数据量不够大的时候，并行排序反而比普通排序更慢。我实测过自己的环境，大约在数组规模超过几十万元素时，parallelSort才表现出优势；百万级以下，我基本只用Arrays.sort。

并行排序还有一个隐含要求：排序算法的稳定性会变。parallelSort对对象数组依然保证稳定性，因为它内部实现是基于稳定的归并排序做的并行化。但如果你的业务依赖稳定排序并且数据量不大，我没理由去用并行版本，成本大于收益。

7. 从sort这个小词延伸出去：工程里排序设计的几个心得

这两个维度我都实际执行过，代码少、逻辑直观、问题容易定位。真等某个排序规则已经散落在十几个调用点里、前面还套着各种if-else分支的时候，再想统一改规则，那才是真正的灾难现场。

多级排序规则用Comparator链式写法比如Comparator.comparing(...).thenComparing(...)就足够清晰了，不需要自己写一长串if-else。规则复杂到一门语言无法表达清楚时，要么重新梳理一下需求，看看是不是把排序的维度定得太多了，而不是马上在代码层面硬凑。

数据量一大，排序前尽量把参与排序的键提取成轻量的数组，比如只排序long[]或int[]，排序后再关联回原对象。这种思路在内存紧张时特别有用。我做过一个千万级订单数据的导出功能，需要按金额从大到小输出前一万条，直接排序完整订单对象十分奢侈，我改成先构建一个索引数组，索引按金额排序，然后按索引取记录，排序时间和内存占用都降到了原来的三分之一左右。

最后再分享一个我自己的做法：给排序逻辑写一点"验证代码"，比如用一个已知有序的集合打乱后排序，检查结果和预期是否一致。这个习惯也许看起来多此一举，但在我经历过多次线上排序小事故之后，我再也不会省略这一步。排序是个太基本的操作，正因为基本，一旦错了，影响面就特别大，排查起来还常常让人措手不及。