尧图网站开发 
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] ListInteger 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) { ListOrder 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个word32位整数。注意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[j1] slt $t9, $t8, $t7 # array[j1] 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²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定这里最容易被面试官追问的是为什么快速排序最坏会退化成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)符号相反传递性就是如果xy且yz那么xz。任何一个条件不满足排序算法就可能出现诡异的乱序而且不同的算法表现出不同的错法特别难排查。我记得有一次在开发时排序一批文件按文件名排序但文件名里有数字部分比如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打出来全是Order762efe5d排查效率极低。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[]排序后再关联回原对象。这种思路在内存紧张时特别有用。我做过一个千万级订单数据的导出功能需要按金额从大到小输出前一万条直接排序完整订单对象十分奢侈我改成先构建一个索引数组索引按金额排序然后按索引取记录排序时间和内存占用都降到了原来的三分之一左右。最后再分享一个我自己的做法给排序逻辑写一点验证代码比如用一个已知有序的集合打乱后排序检查结果和预期是否一致。这个习惯也许看起来多此一举但在我经历过多次线上排序小事故之后我再也不会省略这一步。排序是个太基本的操作正因为基本一旦错了影响面就特别大排查起来还常常让人措手不及。 
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] ListInteger 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) { ListOrder 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个word32位整数。注意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[j1] slt $t9, $t8, $t7 # array[j1] 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²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定这里最容易被面试官追问的是为什么快速排序最坏会退化成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)符号相反传递性就是如果xy且yz那么xz。任何一个条件不满足排序算法就可能出现诡异的乱序而且不同的算法表现出不同的错法特别难排查。我记得有一次在开发时排序一批文件按文件名排序但文件名里有数字部分比如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打出来全是Order762efe5d排查效率极低。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[]排序后再关联回原对象。这种思路在内存紧张时特别有用。我做过一个千万级订单数据的导出功能需要按金额从大到小输出前一万条直接排序完整订单对象十分奢侈我改成先构建一个索引数组索引按金额排序然后按索引取记录排序时间和内存占用都降到了原来的三分之一左右。最后再分享一个我自己的做法给排序逻辑写一点验证代码比如用一个已知有序的集合打乱后排序检查结果和预期是否一致。这个习惯也许看起来多此一举但在我经历过多次线上排序小事故之后我再也不会省略这一步。排序是个太基本的操作正因为基本一旦错了影响面就特别大排查起来还常常让人措手不及。