使用Arrays.sort与Comparator排序n×2矩阵的原理详解

一、Arrays.sort的整体执行逻辑 #

Java里的Arrays.sort方法，当排序对象数组（比如这里的int[][]二维数组）时，底层用的是TimSort算法（Java 7及以后版本）——这是一种把归并排序和插入排序结合起来的高效算法，时间复杂度稳定在O(n log n)。

排序的核心过程就是：算法会不断从数组中取出成对的元素，调用你传入的自定义比较规则，判断两者的先后顺序，然后逐步调整所有元素的位置，直到整个数组完全符合你定义的排序规则。

二、自定义Comparator的工作原理 #

你写的Lambda表达式(a, b) -> { ... }，本质是实现了Comparator<int[]>接口的compare(a, b)方法，这个方法的返回值直接决定了两个元素的排序位置：

• 返回负数：说明a应该排在b的前面
• 返回0：说明a和b的排序位置可以互换（不影响最终结果）
• 返回正数：说明b应该排在a的前面

结合你的代码具体拆解规则：

1. 优先比较第一列：先看两个一维数组的第一个元素a[0]和b[0]
   • 如果两者不相等，返回a[0] - b[0]：
     • 比如a[0] = 1、b[0] = 2，返回-1（负数），a排前面，保证第一列升序；
     • 如果a[0] = 4、b[0] = 2，返回2（正数），b排前面，同样维持第一列升序。
2. 第一列相同时比较第二列：当a[0] == b[0]时，比较第二个元素a[1]和b[1]，返回a[1] - b[1]：
   • 比如a = [2,0]、b = [2,3]，返回-3（负数），a排b前面，实现第二列升序。

三、结合示例的排序过程 #

拿你给出的原始矩阵[[2, 0], [4, 1], [1, 2], [2, 3], [5, 4]]来说：

• 排序时算法会两两对比元素：比如对比[2,0]和[1,2]，返回2-1=1（正数），所以[1,2]被调整到前面；
• 再比如对比[2,0]和[2,3]，第一列相同，返回0-3=-3（负数），所以[2,0]排在[2,3]前面；
• 经过多轮这样的比较和位置调整，最终得到排序后的矩阵[[1, 2], [2, 0], [2, 3], [4, 1], [5, 4]]。

内容的提问来源于stack exchange，提问作者Brendan B