★ FEATURED ARTICLE 之前刷题群里有个朋友问我一道题里需要把数组按某个字段排序他直接写了arr.sort()结果出来一排乱序后来发现 JavaScript 的sort()默认按字典序排数字。这事看起来很小但做题时特别常见。排序确实是算法题里最基础的操作之一但恰恰是这种基础操作越是容易在细节上翻车。这篇内容我按照自己刷题几年的实际经验把数组排序在题目里的各种用法、坑、以及“什么时候应该抛弃内建 sort 自己手写”都梳理一遍适合刚开始刷题、或者刷题有一段时间但总在某些排序题上卡住的朋友。1. 排序在题目里的分量大多数时候它不是考点本身1.1 排序通常只是“预处理手段”很多题表面上看是排序题实际上排序只是给后续逻辑铺路。比如合并区间、会议室占用、按频率排列元素、去除重复数字后统计这些题的第一步几乎都是“把数组排个序”。但排序本身不作为考点考的是排序之后的双指针、贪心、前缀和、动态规划等。所以做题时我给自己定了一条原则先把排序函数用对再去想后续算法。排序只是工具工具用错了后续全盘皆输。举个例子合并区间题里先把二维数组按每个区间的起始位置升序排列然后挨个判断当前区间的终点是否覆盖下一个区间的起点。如果排序这一步写错了比如将区间 [10, 30] 排到 [2, 8] 前面合并逻辑再正确也白搭。1.2 复杂度观念要先建立还有一个常见的认知误区排序不是免费的。内建排序时间复杂度通常为O(n log n)这在多数题目里能过但如果题目给的n达到10^6甚至10^7O(n log n)就可能逼近时间上限。此时要思考是否存在更优方案比如计数排序、桶排序后续章节会详细展开。另外排序的稳定性也是做题时的关键特性。所谓稳定性是指“排序前后值相同的元素原有相对顺序不变”。有些题目要求按多个条件排序如果第一次按次要条件排、第二次按主要条件排那就依赖排序的稳定性如果内建排序不稳定可能需要借助结构体附带索引来模拟稳定效果。2. 内建排序实测不同语言之间的差异与翻车点2.1 JavaScript默认字典序是最大的坑JavaScript 的Array.prototype.sort()在不传比较函数时会先把元素转为字符串再按字典序排列。这就导致数字数组[3, 11, 8]排序后得到[11, 3, 8]。很多前端转算法的朋友第一次在这翻车也常发生在“vba数组、js数组”这类脚本处理里。做题时我的固定写法是let nums [3, 11, 8]; nums.sort((a, b) a - b); // 升序降序就是(a, b) b - a。还有一点值得提醒箭头函数里a - b如果数值超过Number.MAX_SAFE_INTEGER会出错但题目里很少见一般不用过度担心。真正要注意的是比较函数必须返回负数、零、正数三种情况而不是返回布尔值。比如nums.sort((a, b) a b); // 错误返回布尔值会被转成 0 或 1不稳定做题时个人习惯是只要涉及排序就强制带上比较函数哪怕数组是字符串也带上localeCompare防止默认行为误导自己。2.2 Pythonsort 与 sorted 的稳定特性和 key 参数Python 里list.sort()原地排序sorted()返回新列表。两者默认都是升序、稳定排序这个稳定特性在做“先按次要条件排再按主要条件排”的题目时非常有用。但 Python 排序里最容易忽略的是key参数。很多人一上来就写自定义比较函数其实key能解决大部分场景。例如按绝对值排序arr.sort(keyabs)按字符串长度排序再按字典序排序arr.sort(keylambda s: (len(s), s))Python 的sorted()还经常和切片一起用比如取排序后前 k 个top_k sorted(arr)[:k]这就是热搜词里“python数组切片命令”在刷题中的应用场景。我踩过的一个坑直接用arr.sort(reverseTrue)做一个对象数组的降序排列结果发现字典序规则导致预期外的顺序。所以做对象字段排序时永远使用keylambda x: x[field]这种方式明确告诉排序依据别依赖默认行为。2.3 JavaComparator 里的溢出风险Java 刷题常用Arrays.sort()和Collections.sort()。对象数组、二维数组排序时要传入ComparatorArrays.sort(intervals, (a, b) - a[0] - b[0]);这段代码很常见但a[0] - b[0]在数据接近Integer.MAX_VALUE或Integer.MIN_VALUE时会整数溢出。例如a[0] 2_000_000_000b[0] -2_000_000_000差值溢出变成负数比较结果就错了。更稳的写法是Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0]));Integer.compare底层直接做逻辑判断不会溢出。Java 里对字符串数组排序可以用Arrays.sort(strArray)默认按字典序。如果想按长度排Arrays.sort(strArray, (a, b) - Integer.compare(a.length(), b.length()));Comparator 的返回值同样必须是负、零、正三态直接写return a[0] b[0];返回布尔值的错误写法在 Java 里编译都过不了反而比 JavaScript 更容易暴露问题。2.4 C 和 C 语言结构体排序与 qsort 的类型转换陷阱C 刷题通常直接用std::sort配合 lambda 表达式。结构体排序时需要自定义比较规则例如按照学生的分数降序、分数相同时按姓名升序struct Student { int score; string name; }; sort(students.begin(), students.end(), [](const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.name b.name; });注意 lambda 里的参数要用const Student引用传递避免不必要的拷贝。C 里还要注意std::sort是不稳定排序std::stable_sort才是稳定的。题目明确要求“相等元素保持原顺序”时记得换成stable_sort。C 语言里常用的qsort写法有一处非常著名的坑比较函数返回*(int*)a - *(int*)b大整数相减同样会溢出。更安全的做法是int cmp(const void *a, const void *b) { int va *(const int*)a; int vb *(const int*)b; return (va vb) - (va vb); }(va vb) - (va vb)这种写法把结果限定在 -1、0、1不会有溢出风险也处理了相等情况。C 语言里的字符串数组排序通常定义成指针数组char *words[] {banana, apple, cherry};然后用strcmp做比较函数比如int cmp_str(const void *a, const void *b) { char * const *pa a; char * const *pb b; return strcmp(*pa, *pb); }这里容易记错qsort的比较函数参数类型它的参数是“指向数组元素的指针”所以指针数组的元素本身就是char*参数需要转成char* const*再取一次指针才能拿到字符串。2.5 各语言内建排序一览表语言常用函数稳定性主要坑点推荐比较写法JavaScriptArray.prototype.sort()稳定ES2019默认字典序(a, b) a - bPythonlist.sort()/sorted()稳定key 与 reverse 同时使用时方向易混keylambda x: ...JavaArrays.sort()/Collections.sort()稳定对象数组a-b 溢出Integer.compare(a, b)Cstd::sort不稳定结构体排序需自定义规则lambda const TCqsort不稳定返回值溢出void 指针转换(va vb) - (va vb)这张表是我做题时给自己整理的速查表每次换语言刷题之前扫一眼能少踩很多坑。3. 做题常见的排序变体字符串、多维数组与对象字段3.1 字符串数组排序字典序、长度与特殊规则字符串数组排序在题目里出现频率不低最基础的是字典序排序。Python 和 C 默认都能直接排Java 用Arrays.sort()也能排字符串。但题目一般不满足于简单字典序而是要求“按某个规则排序后拼接/比较”。典型例子是“最大数”类题目给定一组非负整数要求把它们排列成一个最大的数比如[3, 30, 34, 5, 9]拼接结果是9534330。这道题表面上是排序实际上需要自定义比较规则两个数a和b谁应该排前面不是看a和b的大小而是看拼接后的ab与ba哪个更大。Python 写法from functools import cmp_to_key def largest_number(nums): strs [str(x) for x in nums] strs.sort(keycmp_to_key(lambda a, b: -1 if a b b a else 1)) return 0 if strs[0] 0 else .join(strs)C 的写法类似lambda 里返回布尔值时判断a b b a。这类题是“数组转字符串 排序”结合的典型场景也回应了热搜词里的“数组转字符串”。重点在于理解排序规则完全看题目要求不一定是数值大小。3.2 二维数组按某列排序二维数组在题里最常见的场景是区间、坐标、物品属性表。按哪一列排序取决于算法需要区间合并通常按起始列升序区间选点有时按结束列升序路程计算可能按距离列的绝对值升序Java 里按第二列降序可以写Arrays.sort(arr, (a, b) - Integer.compare(b[1], a[1]));Python 里按第二列排序arr.sort(keylambda x: x[1])这里要注意一个细节Python 的key函数一旦写成lambda x: x[1]会忽略第一列。如果希望“第一列相同时按第二列排”要写成lambda x: (x[1], x[0])或者lambda x: x[1:]。这个细节很容易漏尤其在二维数组长度为 2 或 3 时。3.3 对象数组按字段排序与多重条件组合对象数组排序是“结构体排序”的近亲C 结构体排序在题里出现的频率很高常见错误是漏掉相等条件的处理。比如按成绩降序成绩相同按姓名升序如果 lambda 只写了成绩比较sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; });那么这个 sort 的排序结构是满足要求的但严格来说比较函数没有定义相等情况下的行为。虽然std::sort在大多数编译器下能运行但严格地说应该补上第二条件if (a.score ! b.score) return a.score b.score; return a.name b.name;多重条件排序的通用思路是按优先级从高到低写出所有判断分支先比较最重要的字段相等再比较次要字段。千万不要试图通过return a.score b.score || (a.score b.score a.name b.name);这种单行合并写法虽然能跑但可读性差调试时很难发现问题。3.4 非传统排序规则按奇偶、按绝对值、按出现频率有些题不会直说“排序”但本质就是排序。按奇偶排序奇数在前、偶数在后同类之间相对顺序不变。这种题用内建排序规则定义为“奇数排在偶数前同为奇偶时按原值大小”。按绝对值排序nums.sort(keyabs)一行搞定。但有些题要求“绝对值相同的时候负数排在正数前面”这时就要写成nums.sort(keylambda x: (abs(x), x 0))注意 Python 的True大于False所以如果想“负数在前”要让负数的第二排序键更小。按出现频率排序是更经典的变体先用哈希表统计每个数的频次再按频次对数组排序。这类题在热词“按频率排序”里经常出现也是统计 排序 重构数组的综合题。4. 必须手写排序的场景归并、快排的题目价值4.1 为什么有时候内建排序不够用做题时有一种情况必须抛弃内建排序题目考察的不是“排序结果”而是“排序过程可以顺带算出来的东西”。最典型的就是逆序对数量。在数组[5, 2, 4, 6, 2, 1]中逆序对是指满足i j但a[i] a[j]的数对。朴素做法是双重循环O(n^2)数据量一大就超时。用归并排序在合并过程中统计逆序对数量能压到O(n log n)。内建排序确实可以做这件事但内建排序不会告诉你“排序过程中有多少次逆序”因为这是排序算法的副产品。这就是“手写排序”在题目里的真正价值不是排序本身而是借助排序中间过程解决额外问题。4.2 手写归并排序求逆序对归并排序的核心是分治把数组一分为二分别排序再合并两个有序数组。合并时如果左边临时数组当前指针指向的值大于右边当前值说明左边剩余的所有元素都能和右边这个元素组成逆序对累加数量即可。一个可以记忆的 Python 模板def merge_sort_with_count(arr): if len(arr) 1: return arr, 0 mid len(arr) // 2 left, count_left merge_sort_with_count(arr[:mid]) right, count_right merge_sort_with_count(arr[mid:]) count count_left count_right merged [] i j 0 while i len(left) and j len(right): if left[i] right[j]: merged.append(left[i]) i 1 else: merged.append(right[j]) j 1 count len(left) - i merged.extend(left[i:]) merged.extend(right[j:]) return merged, count这里关键的一行是count len(left) - i当右数组当前元素right[j]小于左数组当前元素left[i]时左数组从i开始到末尾的所有元素都比right[j]大因此一次可以统计多个逆序对。如果遇到逆序对题的同时数值范围很大可以用“离散化 树状数组”做思路类似先对原数组离散化再按顺序遍历在树状数组里查询比当前元素小的个数。两种方案都能做但归并排序的代码不依赖树状数组模板适合快速写出来。4.3 快速排序的 partition 思想不只是排序快速排序的 partition 过程比排序本身更适合解决某些题目。一个典型场景是求数组第 k 大元素TopK 问题。标准快排思路是随机选择 pivot把数组分成小于等于 pivot 和大于 pivot 两部分根据 pivot 的位置判断目标值在哪一侧只递归搜索那一侧。经过 partition 后虽然两侧不一定完全有序但 pivot 已经落到了它在最终有序数组中的准确位置。如果这个位置刚好是n - k第 k 大就直接返回。这种做法的期望复杂度是O(n)比全排序后再取第 k 个要快。C 里可以提供类似写法int quickSelect(vectorint nums, int l, int r, int k) { int pivot nums[l rand() % (r - l 1)]; // 三路 partition返回 pivot 区域的左右边界 // 然后判断 k 落在左、中、右哪个区间递归处理对应区间 }做题时如果不想手写快排用内建排序也行但面试场景下考官更愿意看到你理解 partition 的思想而不是单纯调库。4.4 手写排序的稳定性选择与边界条件很多人在做题手写归并时会在合并循环结束后忘记处理剩余元素。比如上面的merged.extend(left[i:])和merged.extend(right[j:])少了任何一行最终结果就不完整。还有一个小细节归并排序的left[i] right[j]里的等号不能省。这个等号保证了相等元素的相对顺序不变归并排序是稳定排序丢了等号就可能把后出现的相同元素排到前面破坏稳定性。快速排序的边界条件比归并要多要小心左右边界溢出、递归深度过深导致栈溢出。Python 默认递归深度约 1000如果面试/笔试环境没有提高递归深度手写归并的递归写法也可能爆栈。此时可以用迭代式归并或者改用其他方案。5. 突破 O(n log n)计数排序和桶排序的适用场景判断5.1 数据范围小的时候计数排序比快排快一个量级计数排序的思路是先统计每个数字的出现次数再按顺序输出。它不通过比较进行排序所以复杂度从O(n log n)降到O(n range)其中range是数值范围。适用场景非常明确数据量大但数值范围小。比如给10^5个年龄年龄范围只有 0 到 150给10^6个学生的分数满分只有 100。把这些数值统计到计数数组里然后按顺序扩展输出代码非常短def counting_sort(nums, max_val): counts [0] * (max_val 1) for x in nums: counts[x] 1 res [] for value in range(max_val 1): if counts[value]: res.extend([value] * counts[value]) return res这里有一个坑counts数组的长度必须覆盖所有可能值若数据里有负数需要把整体偏移到非负数例如最小值为-100时映射到value 100。5.2 桶排序按频率、按区间分布时的利器桶排序的思路是把数据分到有限个桶里每个桶内部再排序。做题时桶排序最常见的形态是“按出现频率排序元素”。比如 LeetCode 上的“数组中的第 K 个高频元素”这类题可以先统计频率再把频率作为桶下标往对应桶里放元素最后从高到低取出。代码示例from collections import Counter def top_k_frequent(nums, k): freq Counter(nums) max_freq max(freq.values()) buckets [[] for _ in range(max_freq 1)] for num, f in freq.items(): buckets[f].append(num) result [] for f in range(len(buckets) - 1, 0, -1): for num in buckets[f]: result.append(num) if len(result) k: return result这个写法的好处是频率本身就是天然的桶下标不需要比较排序一次哈希统计加一次遍历就能得到结果。5.3 判断是否该用计数/桶排序的三条标准我给自己定了三条判断标准缺一不可元素的取值范围是否可控且有限如果不确定最大值需要先遍历一遍确认但遍历本身也是O(n)不会改变复杂度。内存是否能承受计数数组长度等于数值范围如果范围是10^9那这个数组本身就是内存灾难。是否需要保留额外信息计数排序只适合对整数排序如果需要同时排序附带对象要么用桶配合其他数据结构要么还是走比较排序。桶排序同理桶数量等于频率范围如果元素频率分布极端桶可能空掉很多空间浪费不大但建立空的桶列表本身也需要时间。5.4 基数排序在字符串/整数排序中的延伸基数排序按位从低位到高位或从高位到低位依次用稳定排序处理每一位适合整数和定长字符串。做题时用到的地方相对少因为内建排序通常够快。但在“按字典序排序字符串数组”“按二进制位顺序排列数组”这类题里基数排序的思路偶尔能派上用场。不过我的建议是做题时优先用内建sort只有在复杂度不够或者需要借助排序过程中的额外信息时才手写排序。计数排序、桶排序、基数排序这些非比较排序是为了特定数据形态准备的“备用武器”不是默认选项。6. 排序题的边界与调试经验从空数组到去重再到稳定性6.1 空数组和单元素数组这是最容易被忽略的边界。[].sort()或者sorted([])通常不会报错返回空数组。但有时排序代码里夹带了取arr[0]、arr[-1]这类操作空数组就会直接越界。我的习惯是排序之后如果需要访问首尾元素一定先判断数组长度是否至少为 1。如果是区间题排序后要拿第一个区间的终点做合并初始值那就要提前判断n 0的情况返回空结果。单元素数组排不排都无所谓但比较函数依然会被调用吗不一定。不同语言、不同运行时对单元素数组优化不同不应该依赖这个行为写逻辑。6.2 稳定性什么时候会“要命”按多重条件排序时有两条路一是把多个条件写进同一个比较函数二是先按次要条件排序再按主要条件排序但第二种方法只有排序算法稳定时才可靠。比如要对学生按“班级升序、分数降序”排列可以先按分数降序排再按班级升序排。Python 的sort稳定所以这个写法没问题。C 的std::sort不稳定第二次按班级排序时分数相同的左右顺序可能被打乱此时应该用std::stable_sort。做题时如果遇到“先按 A 排再按 B 排且 A 相同时保持 B 顺序”的题面优先考虑把两个条件合并进一个比较函数这样就不用操心稳定性了。6.3 排序与去重配合数组去重有两种常见思路一种是用集合去重另一种是先排序再相邻去重arr.sort() unique [] for x in arr: if not unique or unique[-1] ! x: unique.append(x)这种做法的好处是如果后续还需要有序数据排序和去重可以一次搞定。缺点是改变了原始数组顺序。如果题目要求保留原顺序去重就不能用这种方法得用seen集合配合遍历。C 里也可以用sort加uniquesort(nums.begin(), nums.end()); nums.erase(unique(nums.begin(), nums.end()), nums.end());unique只是把重复元素移到末尾必须配合erase才能真正删除这个细节初学者很容易漏。6.4 设计排序相关的测试用例做题提交前我都会用几个固定用例自测空数组[]单元素数组[1]全部相同元素的数组[1,1,1]已升序、已降序、完全乱序含负数、含零、含最大值/最小值边界值的数组多维数组长度不一时是否依然按预期排序排序后访问首尾元素确认没有越界这些用例看起来基础但真的能拦截绝大多数因为比较函数写错导致的翻车。比如[3, 30, 34, 5, 9]的最大数题如果不自定义比较规则直接用字典序排就会得到[9, 5, 34, 30, 3]而不是正确的排序方式。6.5 数组排序写完后记得检查“是否改变了原数组”不同语言对原地排序和新数组的处理不一样JavaScript 的sort()是原地排序Python 的list.sort()也是原地排序但sorted()返回新列表Java 的Arrays.sort()原地排序C 的sort()原地排序。做题时如果后续逻辑依赖原数组顺序就要注意别在排序时把原数组改掉。一种做法是用拷贝sorted_nums sorted(nums) # 原数组不变另一种是先用 List/对象包装索引排序时带着索引一起排indexed list(enumerate(nums)) indexed.sort(keylambda x: x[1])这种做法常用于需要“知道每个元素在排序后处于哪个位置”的题目比如计算每个数右侧比自己小的个数或者按身高重建队列。这类题的精髓在于排序时保留原始索引信息就能在排序后重建与原位置的映射关系。我在实际刷题中把排序相关的常见套路都整理成了一个小清单先确认排序规则再确认稳定性要求再确认是原地排序还是返回新数组最后测试边界值。这套流程走下来排序相关的低级错误基本不会在带着题目交卷时再现。代码能编译能过样例不算结束把排序背后的规则想透了后面遇到任何“排序变体题”才能不慌。
阅读完成 · 觉得有帮助？
