★ FEATURED ARTICLE 这道题我在带新人刷题的时候几乎每次都会遇到。绝对值排序四个字看着没什么但真正动手写的时候一堆人会倒在负号、相等绝对值、排序稳定性这些细节上。它通常出现在教材或者在线题库的排序章节靠后位置编号里带着例55.3这类标记本质上就是一道练习自定义排序规则的小题。但恰恰是这种看似基础的小题把排序的比较规则这个核心概念掘得很深很多人在笔试面试的代码题里栽跟头根源就是对这类题的理解不够透。这篇文章就围绕这个题目展开我会先拆清楚题目的真实意图再给出 C、Python、Java 三种主流语言里我认为最稳妥的写法然后带你走一遍完整的实操流程包括构造输入数据、验证输出、排查常见错误。最后我会把这个套路抽象一下你会发现绝对值排序只是自定义排序规则的一个小入口学会这一套很多所谓的新题其实都只是换了个马甲。1. 先把题目拆清楚绝对值排序到底在排什么1.1 为什么绝对值会让排序变麻烦很多人学排序是从整数开始的升序排、降序排比较的就是数本身。绝对值排序的诡异之处在于它比较的依据不再是数字本身而是每个数到 0 的距离。换句话说负号会被暂时遮住再重新参与排序。举个例子给你三个数 -8、5、-2。如果按数值本身升序排结果是 -8、-2、5但如果按绝对值排-8 的绝对值是 85 的绝对值是 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 Csort 自定义比较函数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; vectorint 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 Pythonkey 元组是偷懒但正确的写法Python 的sort和sorted支持key参数意思是把每个元素映射成一个排序键排序时直接比较键。这种设计天然适合多级排序规则。绝对值排序用 Python 写最简洁可靠的方案是n int(input()) a list(map(int, input().split())) a.sort(keylambda x: (abs(x), x)) print(*a)这里的lambda x: (abs(x), x)返回一个二元组Python 比较元组时先比第一个分量相等再比第二个分量刚好就是绝对值从小到大相等按原值从小到大。但这里有个隐藏的坑Python 的排序是稳定排序。稳定排序意味着如果比较键相同就保持它们在原序列中的相对顺序。如果你图省事写成a.sort(keyabs)结果会怎样-2 和 2 键相同它们的顺序取决于输入顺序。如果输入是2 -2输出就是2 -2如果输入是-2 2输出就是-2 2。而且你没法通过调整数据让标准答案稳定因为题目往往把这种情况视为未定义你可能这次过下次就挂。更隐蔽的情况是有些同学想当然地以为反正我只是按绝对值排相等的随便然后用了keyabs。在本地跑一两次发现结果好像挺正常就没继续深究。这种碰巧正确最危险。我的建议是凡是多级规则一律用元组 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(vectorint 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[j1] 的绝对值交换 // 绝对值相等时如果 a[j] a[j1]也要交换 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你的排序和输出代码要能正确处理空序列。有些同学的代码一遇到 n0 就会输出一个多余的空格或者直接越界虽然大部分题目 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; vectorint 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 起步的选手习惯了keyabs的写法转到 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 就更直接了keylambda 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 我的一点体会绝对值排序这道题真的是我见过性价比最高的小题之一。代码量不大但能把自定义比较规则排序稳定性边界值对拍验证这些非常重要的概念全部串起来。我带的人里凡是认真把这道题吃透的后面遇到排序相关的变种题基本都能举一反三凡是草草交作业的后面在更复杂的数据结构题目里往往还会回来补课。如果你现在正卡在某个排序问题上我建议你别急着看答案先把自己的比较函数在白纸上写清楚第一关键字是什么相等怎么办再相等怎么办。写清楚之后再翻译成代码。这个过程看起来有点笨但效率极高。我自己这些年写排序相关的代码无论面对多奇怪的规则都是从这张白纸开始的。
阅读完成 · 觉得有帮助？
