这道题我在带新人刷题的时候几乎每次都会遇到。"绝对值排序"四个字看着没什么,但真正动手写的时候,一堆人会倒在负号、相等绝对值、排序稳定性这些细节上。它通常出现在教材或者在线题库的"排序"章节靠后位置,编号里带着"例55.3"这类标记,本质上就是一道练习自定义排序规则的小题。但恰恰是这种看似基础的小题,把"排序的比较规则"这个核心概念掘得很深,很多人在笔试面试的代码题里栽跟头,根源就是对这类题的理解不够透。
这篇文章就围绕这个题目展开,我会先拆清楚题目的真实意图,再给出 C++、Python、Java 三种主流语言里我认为最稳妥的写法,然后带你走一遍完整的实操流程,包括构造输入数据、验证输出、排查常见错误。最后我会把这个套路抽象一下,你会发现绝对值排序只是"自定义排序规则"的一个小入口,学会这一套,很多所谓的新题其实都只是换了个马甲。
1. 先把题目拆清楚:绝对值排序到底在排什么
1.1 为什么绝对值会让"排序"变麻烦
很多人学排序是从整数开始的,升序排、降序排,比较的就是数本身。绝对值排序的诡异之处在于,它比较的依据不再是数字本身,而是每个数到 0 的距离。换句话说,负号会被暂时"遮住",再重新参与排序。
举个例子,给你三个数 -8、5、-2。如果按数值本身升序排,结果是 -8、-2、5;但如果按绝对值排,-8 的绝对值是 8,5 的绝对值是 5,-2 的绝对值是 2,所以正确的输出顺序应该是 -2、5、-8。这里最关键的一点是:-8 反而排在最后,因为它虽然数值最小,但距离 0 最远。
这就是一个新的分类思路:排序规则不再由"数值大小"定义,而是由"到原点的距离"定义。你要在代码里告诉排序函数"请按这个规则来",而不是依赖默认的升序行为。这种"间接比较"恰恰是初学者最容易翻车的地方——如果直接写return a < b,那排出来完全不是题目想要的结果。
1.2 一个被忽略的前提:绝对值相等时怎么办
题目只会说"按绝对值从小到大排序",可是如果输入里同时出现 -2 和 2,这两个数的绝对值都是 2,到底谁应该排在前面?如果不规定,答案就会有两种可能,判题系统就可能随机判你对或错。
我这里至少要讲清楚一个通用约定,也是大部分教材和题库默认的潜规则:绝对值从小到大排,绝对值相等时按原数值从小到大排。也就是说,-2 排在 2 前面,-8 排在 8 前面,因为 -8 < 8。
这个规则不是可选项,而是必须写进比较逻辑里的。很多人写成return abs(a) < abs(b)就交了,结果一测试,跑出来的顺序每次都一样,就以为没问题。实际上那很可能是"运气好",因为库排序在某些数据下碰巧保持了原顺序,或者评测数据恰好没有绝对值相等的数。一旦数据里出现 -2 和 2 这种成对的情况,稳定性和规则缺陷就暴露了。
我之前帮 A 同学排查过一段代码,他信誓旦旦说"我这代码跑得没问题",我丢了一组5 -2 2 -1 1 0进去,他输出的顺序是0 -1 1 -2 2,而标准答案是0 -1 1 -2 2这组数据看不出问题;再换一组-3 3 -2 2,他输出3 -2 -3 2,完全乱掉。原因就是他依赖了输入顺序,而输入顺序恰好掩盖了规则缺失。所以这一条必须从根上想清楚。
1.3 这道例题的训练目标
"例 55.3"这种编号通常标志着它处在某个章节序列里:前面学过最简单的基础排序(冒泡、选择、插入),或者刚介绍了库函数sort/sorted/Arrays.sort的默认用法。到了这道题,第一次要求你往里塞一个"自定义规则"。
从训练角度看,它有三层目标。第一层是语法目标:会用语言提供的排序接口,并且知道怎么把比较函数传进去。第二层是逻辑目标:能分析出"绝对值相等"的分支细节,能写出满足严格弱排序的比较函数。第三层是工程目标:能主动构造边界数据去验证,而不是凭感觉认为"样例过了就行"。
这三点里,第三点往往最被低估。很多新手做完例题就跑了,从不自测边界。但真正到了比赛、笔试、工作面试,没有人会给你的程序喂"温柔样例"。绝对值排序这道小题,就是让你低成本地体会一次"边界条件的重要性"。
2. 三种主流实现方案的底层逻辑与选型
2.1 C++:sort + 自定义比较函数
C++ 里标准做法是用std::sort,第三参数传一个比较函数。这个函数的返回值语义是:当a应该排在b前面时返回true,否则返回false。很多人第一次接触会绕晕,拿"大于小于"去套模板。
比较函数里最容易出问题的点有两个。第一,abs()要用对。C++ 的abs有整数重载(在<cstdlib>或<cmath>里),对int返回int。但是如果你写return abs(a) < abs(b),这只能处理绝对值不同的情况;绝对值相同的时候它返回false,库排序就不知道该怎么排了。所以必须再加上第二层判断。
第二,lambda 表达式和普通函数在写法上的差异。我推荐直接用 lambda,因为代码更紧凑,也不容易污染命名空间:
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; sort(a.begin(), a.end(), [](int x, int y) { int ax = abs(x), ay = abs(y); if (ax != ay) return ax < ay; return x < y; }); for (int i = 0; i < n; i++) { cout << a[i]; if (i != n - 1) cout << ' '; } return 0; }注意那个if (ax != ay)分支:如果不写,只写return abs(x) < abs(y),-2 和 2 的顺序就是未定义的,可能这次跑在前面,下次跑在后面。排序比较函数必须是"严格弱排序",即相等的元素要返回false不管往哪个方向比较,而你真正想要的是:在绝对值相等的条件下,再按原值决出前后。
2.2 Python:key 元组是偷懒但正确的写法
Python 的sort和sorted支持key参数,意思是把每个元素映射成一个"排序键",排序时直接比较键。这种设计天然适合多级排序规则。绝对值排序用 Python 写,最简洁可靠的方案是:
n = int(input()) a = list(map(int, input().split())) a.sort(key=lambda x: (abs(x), x)) print(*a)这里的lambda x: (abs(x), x)返回一个二元组,Python 比较元组时先比第一个分量,相等再比第二个分量,刚好就是"绝对值从小到大,相等按原值从小到大"。
但这里有个隐藏的坑:Python 的排序是稳定排序。稳定排序意味着如果比较键相同,就保持它们在原序列中的相对顺序。如果你图省事写成:
a.sort(key=abs)结果会怎样?-2 和 2 键相同,它们的顺序取决于输入顺序。如果输入是2 -2,输出就是2 -2;如果输入是-2 2,输出就是-2 2。而且你没法通过调整数据让"标准答案"稳定,因为题目往往把这种情况视为未定义,你可能这次过,下次就挂。
更隐蔽的情况是,有些同学想当然地以为"反正我只是按绝对值排,相等的随便",然后用了key=abs。在本地跑一两次发现结果好像挺正常,就没继续深究。这种"碰巧正确"最危险。我的建议是:凡是多级规则,一律用元组 key,别靠稳定性兜底。
2.3 Java:包装类型与 Comparator 的坑
Java 的Arrays.sort对基本类型数组(int[])是重载版本,它只支持默认升序,不能传入自定义比较器。所以想自定义规则,必须用引用类型数组Integer[],然后用Comparator接口。这是我见过新手最容易卡壳的地方,很多人写了半天 lambda,发现编译不过,就是因为没意识到int[]和Integer[]的区别。
正确的 Java 写法是:
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); Integer[] a = new Integer[n]; for (int i = 0; i < n; i++) a[i] = in.nextInt(); Arrays.sort(a, (x, y) -> { int ax = Math.abs(x), ay = Math.abs(y); if (ax != ay) return Integer.compare(ax, ay); return Integer.compare(x, y); }); for (int i = 0; i < n; i++) { System.out.print(a[i]); if (i != n - 1) System.out.print(' '); } } }注意我用了Integer.compare而不是直接return ax - ay。原因很简单:ax - ay可能溢出。在这个具体问题上,两个整数的绝对值之差通常不会爆,但作为一个习惯,养成用比较接口返回-1, 0, 1是更好的。尤其是绝对值排序的变种题里可能出现大数,用减法判断谁大谁小的习惯一定要尽早改掉。
2.4 手写排序时的正确姿势
不是所有场景都允许你直接用库排序。很多教材练习册在线评测环境会比较封闭,或者练习要求你自己实现冒泡、选择、插入排序。这时候你同样要处理比较规则。
以冒泡排序为例,核心逻辑是"相邻两个元素比较,顺序不对就交换"。排序是升序还是降序,取决于你拿谁和谁比较、谁大了就往后移。绝对值排序只需要把"谁大谁小"的判断替换成自定义规则,其他骨架不用动:
void bubble_sort(vector<int>& a) { int n = a.size(); for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { // 如果 a[j] 的绝对值大于 a[j+1] 的绝对值,交换 // 绝对值相等时,如果 a[j] > a[j+1],也要交换 int aj = abs(a[j]), aj1 = abs(a[j + 1]); bool shouldSwap = false; if (aj > aj1) shouldSwap = true; else if (aj == aj1 && a[j] > a[j + 1]) shouldSwap = true; if (shouldSwap) swap(a[j], a[j + 1]); } } }这段代码里有几个容易犯错的地方。第一,aj == aj1这个分支必须处理,否则 -3 和 3 会保持输入时的相对顺序,这可能违反题意。第二,判断条件别写反,我在带新人的时候发现,很多人写着写着就把>写成<,追了半天发现是交换方向反了。第三,注意循环边界,j < n - 1 - i,这是冒泡排序的精髓,漏掉- i会导致多排一轮,结果往往是对的,但做了很多无用功。
3. 完整实操:从读入到通过一次测试的全过程
3.1 输入格式与常见读入细节
这类题目的输入格式几乎都是固定的:第一行一个整数 n,第二行 n 个整数,用空格分隔。读取本身没有难点,但有几个小细节值得养成习惯。
第一,如果 n 可能为 0,你的排序和输出代码要能正确处理空序列。有些同学的代码一遇到 n=0 就会输出一个多余的空格或者直接越界,虽然大部分题目 n 都大于等于 1,但养成防御性编程习惯总没错。
第二,数据范围。绝对值排序题目里,n 一般不超过 10^5,数值的绝对值可能达到 10^9。这种情况下,int存得下绝对值,但如果你在比较函数里写了abs(a) - abs(b)并且直接返回差值,虽然不会溢出到这个范围,但不是好习惯。稳妥起见,可以用long long做中间转换,或者用比较接口。
第三,读入时注意是否包含换行符。C++ 的cin >> x自动跳过空白,没问题;Python 的input().split()也没问题;Java 的Scanner也没问题。但如果你用 C 语言风格的scanf("%d", &x),要注意处理末尾空格和换行,否则可能出现读入错位。
3.2 核心代码现场:逐行拆解 C++ 解法
我选 C++ 作为主讲方案,因为它最接近竞赛和笔试的主流场景。完整代码如下:
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; sort(a.begin(), a.end(), [](const int& x, const int& y) { int ax = abs(x); int ay = abs(y); if (ax != ay) return ax < ay; // 先按绝对值升序 return x < y; // 绝对值相等,按原值升序 }); for (int i = 0; i < n; ++i) { cout << a[i] << (i == n - 1 ? '\n' : ' '); } return 0; }逐行讲几个关键点。ios::sync_with_stdio(false)和cin.tie(nullptr)这两行是性能优化,通常能让输入输出快不少,尤其当 n 达到十万级别时,不加可能会超时。实测下来,有些评测平台对 I/O 速度比较敏感,加这两行基本不会出错。
sort的第三个参数是 lambda。这里的const int& x和const int& y写成值传递int x, int y也行,因为整数本身很小,拷贝开销可忽略。但养成传引用的习惯对后面处理结构体等大对象有好处。
abs(x)我特意先存到局部变量ax,而不是在return ax < ay里直接调用两次abs(x) < abs(y)。这样写的好处是避免重复计算,代码可读性也更好。等你后面做更复杂的比较逻辑时,局部变量存中间结果的意义会更明显。
我建议你自己亲手敲一遍这段代码,不要直接复制粘贴。敲的时候你会发现,手误把ax != ay写成ax == ay会导致什么结果,手误把x < y写成x > y又会导致什么结果。这种"试错"本身就是经验。
3.3 输出与控制:格式化与空格结尾问题
输出的常见写法有两种。一种是循环里每次输出元素加一个空格,最后一个元素之后也允许有空格,很多评测平台对此不敏感。另一种是严格遵守格式,元素之间空格分隔,最后一个元素后面换行,不能有多余空格。
我推荐第二种,因为不是所有评测平台都宽容尾部空格。有的平台比较严格,多一个空格会被判 Presentation Error 甚至 Wrong Answer。上面代码里用的是三目运算符:
cout << a[i] << (i == n - 1 ? '\n' : ' ');这样最后一个元素后面是换行,其他元素后面是空格,完美规避了尾部空格问题。Python 的print(*a)天然实现了这个效果,Java 里我上面也用同样的手法。
有一个我实际踩过的坑:如果你用for (int i = 0; i < n; i++) cout << a[i] << " ";然后期望评测接受尾部空格,一旦平台严格就会挂。后来我学乖了,任何输出都必须"无多余空格、末尾换行",这个习惯帮你省掉无数无谓的罚时。
3.4 边界用例实测
写代码容易,验证代码才是真正拉开差距的地方。我建议构造这样一组测试数据:
5 0 -45 9 45 -2按照规则走一遍:绝对值排序,0 的绝对值是 0 最小;-2 绝对值 2 其次;9 和 -45 的绝对值分别是 9 和 45,所以 -45 最后;45 和 -45 绝对值相等,原值 -45 < 45,所以 -45 在 45 前面。整体输出应为:
0 -2 9 -45 45为什么 9 排在 -45 前面?因为 9 的绝对值是 9,小于 45。为什么 -45 排在 45 前面?因为绝对值相等,按原值升序,-45 更小。这个测试就同时验证了"绝对值优先"和"二级规则"两个分支。
再来一组专门测相等值的:
4 -3 3 -2 2期望输出是-2 2 -3 3。因为绝对值 2 的排在绝对值 3 的前面,而绝对值相等时负数在前。如果你的程序输出3 -2 -3 2,那问题一定出在比较规则上,大概率是丢了相等分支。
最后一组极限值:
3 -2147483648 0 2147483647这里注意:abs(-2147483648)在 32 位int下是未定义行为,可能变成负数,排序结果就会崩。实际比赛中很少给这个值,但如果你面对的题目允许int存到这个边界,我的建议是改用long long或者特判。这点后面还会展开。
3.5 手写排序版本与复杂度分析
如果题目要求你必须手写排序,选择哪种排序算法取决于 n 的数据范围。n ≤ 1000 的规模下,冒泡排序 O(n^2) 完全没问题;n 到 10^5 就必须用 O(n log n) 的快排或归并。好在大多数教材例题都控制在小数据范围,手写冒泡足够过。
冒泡排序的代码我在 2.4 节给过一版。这里补充一点复杂度分析:比较函数本身是 O(1) 的(做了几次整数运算),所以算法的整体复杂度就是排序框架本身的复杂度,即 O(n^2) 或 O(n log n)。空间复杂度方面,手写冒泡是 O(1),库排序视实现可能是 O(log n) 到 O(n),对一般题目来说都不是瓶颈。
选择排序和插入排序同理,只要把比较规则替换为你自定义的函数即可。需要注意的是:不同算法的稳定性不同——冒泡和插入是稳定的,选择排序和快排通常不稳定。如果题目没有明确规定相等绝对值时的顺序,那么不稳定排序的未定义行为在判题时可能成为隐藏的坑。所以我强调过:核心比较函数必须写全二级规则,不要依赖稳定性。
4. 新手最容易踩的五个坑与排查实录
4.1 坑一:拿差值当绝对值,用abs(a - b)代替abs(a) - abs(b)
这两个式子完全不同。abs(a - b)算的是两个数之间的距离,不是 a 到 0 的距离,也不是 b 到 0 的距离。如果写成return abs(a - b) < abs(c - d),那比较规则就完全跑偏了,排出来的序列和"按绝对值排序"没有关系。
更常见的错误是把比较函数写成了:
return abs(a) < abs(b);然后忘了相等分支。这个的错误我前面反复强调过,因为它是"部分正确"的,很多测试数据能过,你甚至会以为代码没问题。只有当你自己主动构造-x和x成对出现的用例时,问题才会暴露。
我建议所有人在写完排序代码后,都顺手跑一组"正负成对"的数据:
5 1 -1 2 -2 3如果输出里 1 和 -1 的相对顺序和输入一致,说明你依赖了稳定性;如果发生了不确定的改变,说明比较规则不完整。正确的答案应该是1 -1 2 -2 3?不对,仔细想:绝对值 1 的 1 和 -1 原值升序,-1 应该在前,所以应该是-1 1 -2 2 3。如果你得到1 -1 2 -2 3,那就说明二级规则没生效。
4.2 坑二:把"稳定排序的稳定性"当成万能的
C++ 的std::sort不保证稳定,Python 的sorted保证稳定,Java 的Arrays.sort对对象使用归并排序是稳定的,对基本类型使用快速排序不保证稳定。这几种语言的默认行为都不一样。
我见过不少从 Python 起步的选手,习惯了key=abs的写法,转到 C++ 后仍然只写return abs(x) < abs(y),然后在脑子里默认"反正相等的最后顺序无所谓"。这在 Python 里可能真的无所谓(因为稳定排序会保证输入顺序),在 C++ 里就是未定义行为,结果可能每次都不同。
根本的解决思路只有一个:比较函数必须对"相等"情况给出明确答复。这不是可选项。只要你的比较函数对两个键值完全相等的元素返回了false而不是进一步判断,那就等于放弃了这一对元素的顺序控制权。如果你不在乎谁前谁后,题目通常也允许,但你要清楚地知道"我不在乎,所以任意顺序都能过"和"我以为它按原有顺序,结果并不保证"之间的区别。后者会让你的调试过程非常痛苦。
4.3 坑三:abs(INT_MIN)溢出
在 32 位int范围内,最小负数是 -2147483648,取绝对值应该是 2147483648,但这个数已经超出int的最大值 2147483647。所以abs(-2147483648)在 C++ 中是未定义行为,在 Python 里没这个问题(整数可以扩展),在 Java 里Math.abs(Integer.MIN_VALUE)会返回负数。
这不是一个理论问题,我有一次在某个练习平台写"按绝对值排序"的变种时,数据构造者确实塞进了边界负数,我的排序瞬间就乱套。排查了半天才发现是abs的问题。
应对方案很简单:要么用long long存,要么在比较函数里额外处理。C++ 里可以这样写:
long long ax = llabs(x), ay = llabs(y);或用std::abs的重载版本传入long long。Java 里可以用Math.abs((long)x)。如果你的题目值域明确写着绝对值不超过 10^9,那int的abs足够安全,不必过度设计。但我个人的习惯是:能保险就保险,多写几个字符换来稳定,不亏。
4.4 排查实录:写一个对拍脚本
"对拍"是算法竞赛里非常实用的调试手段:你用 Python 或者任何方便的语言写一个"标准答案"版本,再写一个随机数据生成器,不停生成随机输入,然后把你的目标程序输出和标准答案对比,不一致就停下来。
绝对值排序的对拍脚本很简单。Python 数据生成器:
import random n = random.randint(1, 10) print(n) print(' '.join(str(random.randint(-100, 100)) for _ in range(n)))Python 标准答案(用元组 key 排序)就是你想要的正确行为。然后写一个脚本,循环跑"生成数据 -> 跑你的可执行文件 -> 对比"。这在 Linux 或 macOS 下用 shell 就能实现,Windows 用户可以写 Python 脚本调用subprocess。
对拍的价值在于,它能在极短时间内帮你找出手写排序里"错误比较方向"这类隐蔽问题。我记得有一次,某位同学排出来的结果前面大部分都是对的,只有某几个点顺序差一点,肉眼很难发现。我写了个 100 组随机数据一跑,立刻暴露问题——原来他比较绝对值相等时x < y写成了x > y。这种问题靠肉眼盯样例是盯不出来的。
4.5 问题速查表
| 现象 | 可能原因 | 解决办法 |
|---|---|---|
| 输出整体顺序不对,负号没起作用 | 比较函数里用了a < b而不是abs(a) < abs(b) | 改成按绝对值比较 |
| 数据里有成对正负数时顺序随机 | 比较函数缺少相等分支 | 增加ax == ay时按x < y返回 |
边界数据-2147483648时排序错乱 | 32 位abs溢出未定义行为 | 改用long long |
| 输出结尾多了空格被提示格式错误 | 循环里每个元素后都输出了空格 | 用三目运算符或print(*a) |
| Java 里传 lambda 编译不过 | 对int[]传自定义比较器 | 改用Integer[]并装箱 |
| n 为零时程序崩溃 | 未处理空序列 | 排序前判空或用通用输出逻辑 |
这张表基本覆盖了我带教过程中遇到的绝大多数问题。如果你写完代码直接对号入座,会比瞎猜高效很多。
5. 从绝对值排序延伸出去:一种"自定义排序框架"
5.1 换个场景:按到原点的距离排序
绝对值排序其实可以看作"一维空间中点到原点的距离排序"。把每个数看成数轴上的一个点,绝对值就是它的距离。把这个概念推广到二维,就是经典的"平面上 n 个点按到原点距离排序"。
这个问题的比较规则是:先按x*x + y*y升序(平方和可以避免开方的浮点误差),平方和相等时按 x 坐标升序,再相等按 y 坐标升序。用 C++ 写:
sort(points.begin(), points.end(), [](const Point& p, const Point& q) { long long d1 = 1LL * p.x * p.x + 1LL * p.y * p.y; long long d2 = 1LL * q.x * q.x + 1LL * q.y * q.y; if (d1 != d2) return d1 < d2; if (p.x != q.x) return p.x < q.x; return p.y < q.y; });你会发现,这和绝对值排序的结构一模一样:先用主规则,相等再逐级退到下一规则。学会了绝对值排序,这类题基本就是照着模板改。这里的Point是一个自定义结构体,你可以用类、结构体,甚至元素为数组的vector。
5.2 多关键字排序的通用模板
把绝对值排序上升一层,它就是一个"多关键字排序"的活例子。所谓的多关键字排序,就是先按第一关键字排,相等再按第二关键字排,再相等按第三关键字排,以此类推。
我总结过一个通用模板,可以套在很多地方:学生成绩排序(总分降序,总分相同数学成绩降序,再相同学号升序);单词列表排序(长度升序,长度相同字典序升序);订单列表排序(价格升序,价格相同时间升序)。无论是哪种语言,核心逻辑都是嵌套的判断:
// C++ 伪代码:多关键字排序 bool cmp(const Item& a, const Item& b) { if (a.key1 != b.key1) return a.key1 < b.key1; // 主关键字 if (a.key2 != b.key2) return a.key2 < b.key2; // 第二关键字 return a.key3 < b.key3; // 第三关键字 }Python 就更直接了,key=lambda x: (x.key1, x.key2, x.key3)。这就是"元组比较"带来的便利——Python 里元组天然支持按位比较,相当于把多关键字排序的代码连写都省了。但无论语法多简洁,你要理解它背后的逻辑:排序规则是一个有优先级的序列,而不是一个孤立的比较。
5.3 自定义排序框架的核心要点
如果你想彻底掌握自定义排序,我建议你记住三件事。
第一,比较函数必须满足"严格弱排序"。这个术语听着吓人,实质上就是:如果 a 比 b 小,那么 b 不应该比 a 小;如果 a 比 b 小且 b 比 c 小,那么 a 必须比 c 小。如果你在自己的比较函数里写了一些违反传递性的逻辑,排序结果就完全不可预测。绝对值排序里最常见的违规行为是"相等时返回真"——比如return abs(x) <= abs(y),这是灾难性的,因为它让-2和2都认为对方应该排在自己前面,排序算法会陷入混乱。
第二,比较的依据必须稳定可复现。不要用随机数、计时器、地址等不稳定的值作为排序键。有人会开这种玩笑,但在真实代码里确实遇到过有人不小心把比较函数写成了基于某个临时变量的值,导致同一组数据每次排序结果不同。
第三,排序的目的要明确。你是要稳定的顺序,还是仅仅要"某种"顺序?如果题目或业务要求相等时保持原顺序,就不能依赖不稳定的排序算法,要么自己写稳定排序,要么在比较函数里增加一个唯一标识(比如序号)作为最后一级关键字。这种处理方式在多关键字排序里非常常见。
5.4 我的一点体会
绝对值排序这道题,真的是我见过性价比最高的小题之一。代码量不大,但能把"自定义比较规则""排序稳定性""边界值""对拍验证"这些非常重要的概念全部串起来。我带的人里,凡是认真把这道题吃透的,后面遇到排序相关的变种题,基本都能举一反三;凡是草草交作业的,后面在更复杂的数据结构题目里,往往还会回来补课。
如果你现在正卡在某个排序问题上,我建议你别急着看答案,先把自己的比较函数在白纸上写清楚:第一关键字是什么,相等怎么办,再相等怎么办。写清楚之后,再翻译成代码。这个过程看起来有点笨,但效率极高。我自己这些年写排序相关的代码,无论面对多奇怪的规则,都是从这张白纸开始的。