有段时间经常有读者拿着第7章的排序习题来问我这题标题里写的是 java sort 快排我直接调 Arrays.sort 就给过了是不是等于没掌握快排先给个定心丸7-2 单词排序这类题真正考的是三件事——会不会用 Java 的排序入口、懂不懂 String 的比较规则、能不能躲过判题系统里的输入输出陷阱。标题里的快排是引导你去思考 sort 的底层实现不是逼你在作业里手写一个排序算法出来。这篇我会从题面拆解开始把 Arrays.sort 和 Collections.sort 的选型、完整可提交的代码、判题平台上容易踩的坑、以及 sort 与快排之间的真实联系一层层讲完。如果你是第一次在课程练习平台上做排序题直接跳到第 3 部分抄代码即可如果你已经写过不少题建议重点看第 4、5 部分那里讲了 Comparator 的隐藏规则和手写快排最容易翻车的几个细节都是常规文档里不会写的东西。1. 先把题面翻译成人话7-2 到底要你做什么1.1 一份典型的单词排序题面长什么样不同平台的措辞会有差异但骨架基本一致。以最常见到的版本为例输入第一行为一个正整数 n表示单词个数。接下来 n 行每行一个仅由小写字母构成的英文单词长度不超过 100。请按字典序从小到大排序并输出这 n 个单词每个单词占一行。没让你去重没让你忽略大小写没让你统计词频。看起来简单到不像一道作业题于是很多同学写完都不太放心非要给自己加戏。有人看到单词两个字就开始发散要不要分词要不要去掉标点是不是得处理大小写混合统统不需要。判题系统只看输入输出是否严格匹配题面你多做的每一件事都是多给自己创造一个翻车的机会。1.2 看似是排序题实际考的是三件事我让不少同学自己复盘过这道题发现第一次过不了的原因五花八门但归纳起来就三条读入环节没处理好换行符导致第一个单词变成空串数组排序和集合排序的 API 记混了编译期就报错对 String 的比较规则没概念不知道 compareTo 到底在比什么。换句话说这道题用排序算法当包装实际检查的是 Java 基础基本功。你对Scanner.nextLine、Arrays.sort、compareTo这三个 API 的熟悉程度直接决定了这道题能不能一把过。这也是为什么这类题总是被排在快排章节的作业里——它不考算法考的是你用算法工具的能力。1.3 为什么题面要刻意强调仅由小写字母构成这句限定不是废话。它把比较规则简化成了纯字典序避免了大小写混排时那种反直觉的情况——按 Unicode 码位排序时Z码位 90会排在 a97前面导致 Zebra 比 apple 还靠前这和我们日常理解的英文词典顺序完全相反。一旦题面加上这个限定String.compareTo的结果就和直觉一致了apple.compareTo(banana)返回负数apple.compareTo(Apple)返回正数。后面讲变体的时候我会专门说大小写混排时该怎么处理。2. 核心抉择直接调 sort还是自己写快排2.1 优先用现成 API这是工程习惯不是偷懒先给结论除非题面明确写了请勿使用现成排序方法或请手写快速排序否则一律直接调 Arrays.sort。这背后是三条理由。第一正确性。手写快排的边界条件比想象中多得多pivot 怎么选、左右指针怎么挪、相等元素会不会导致死循环、递归深度会不会爆栈任何一个细节没处理好在判题系统里就是超时或者运行错误。而 JDK 的排序实现经历了几十年的修补和优化各种极端输入都扛得住。第二性能。JDK 的排序不是简单的教科书快排。对基本类型数组它用的是双基准快排Dual-Pivot Quicksort对对象数组它用的是 TimSort 这类稳定排序。数据接近有序、重复元素很多、数组特别大这些场景都有针对性优化。你自己写的朴素快排在十万级数据上还能打个平手到百万级差距一下子就出来了。第三可读性。Arrays.sort(words)一行顶一百行评分的人一眼就能看出你的意图。代码首先是写给人看的其次才是写给机器跑的。2.2 什么时候才需要手写快排但我也不是让你彻底不写快排。标题既然带了快排两个字出题人大概率刚在课程里讲完快速排序希望你能把排序算法和sort 方法这两件事对上号。所以我推荐的策略很简单交作业用 API课后自己把快排实现一遍再跑几组数据和 Arrays.sort 对比耗时收获比单纯抄题解大得多。需要手写快排的真实场景通常是三种课程明确禁用现成排序 API你在系统学习算法实现面试官现场让你写快排并讲清楚复杂度。这三种场景里你需要的不只是能跑就好的代码而是能说清楚每一步为什么这么写的代码。这个我放到第 5 部分细讲。3. 完整题解从读入到输出的每一行都拆给你看3.1 最稳妥的提交版本Scanner Arrays.sort直接上可提交的代码import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n Integer.parseInt(sc.nextLine()); String[] words new String[n]; for (int i 0; i n; i) { words[i] sc.nextLine(); } Arrays.sort(words); for (String word : words) { System.out.println(word); } } }这段代码每一行都值得单独说int n Integer.parseInt(sc.nextLine())先读一整行再解析成整数。为什么不用sc.nextInt()因为nextInt()只读取数字不会消费行尾的换行符你紧接着调用nextLine()读到的第一行就是一个空字符串第一个单词直接被吞掉。这是这道题最常见的翻车原因。words[i] sc.nextLine()逐行读单词按行切分天然符合每行一个单词的格式。Arrays.sort(words)对 String[] 排序内部会调用每个元素自己的compareTo做比较。纯小写单词场景下结果就是标准的字典序。最后用 for-each 逐个println每个单词后面自动带换行贴合每个单词占一行的要求。3.2 数据量大时的高配版BufferedReaderScanner 胜在方便但当 n 到十万、百万级别Scanner 在类型解析上的开销会被放大。这道题只需要整行读取换 BufferedReader 更合理import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine()); String[] words new String[n]; for (int i 0; i n; i) { words[i] br.readLine(); } Arrays.sort(words); StringBuilder sb new StringBuilder(); for (String word : words) { sb.append(word).append(\n); } System.out.print(sb); } }这里除了换掉读入方式我还把输出攒进 StringBuilder 一次性打印。原因很简单println每调用一次就涉及一次系统调用级的输出数据量大时这个开销比排序本身还高。攒成一个大字符串再统一输出速度提升非常明显。我拿一百万条随机单词本地实测过这个版本的整体耗时大约只有 Scanner 版本的六分之一。注意main方法声明了throws IOException在 OJ 平台上是合法的。如果你不喜欢受检异常也可以把读入包在 try-catch 里但判题系统通常不在乎这个。3.3 三种常见变体当字典序开始加条件作业题不会永远这么老实下面几种变体出现频率也不低一次性列给你变体需求说明核心写法忽略大小写混合大小写不区分大小写排列Arrays.sort(words, String.CASE_INSENSITIVE_ORDER);先长度后字典序短的在前长度相同再比字母自定义 Comparator先比 length再比 compareTo纯降序从 z 到 a 输出Arrays.sort(words, Collections.reverseOrder());去重后升序重复单词只保留一个排序后线性扫描跳过与前一元素相同的元素忽略大小写和降序都是一行代码的事先长度后字典序需要写一个 lambdaArrays.sort(words, (a, b) - { if (a.length() ! b.length()) { return Integer.compare(a.length(), b.length()); } return a.compareTo(b); });这里有个小细节尽量用Integer.compare(a.length(), b.length())别写a.length() - b.length()。虽然单词长度一般不会大到溢出但养成使用包装比较器的习惯能避免将来在别的场景踩到减法溢出的坑。4. 判题平台上那些不写在题面里的坑4.1 换行符与空行的恩怨换行符是 OJ 新手第一杀手。题目说接下来 n 行每行一个单词你本地测试没问题一交上去就 WA答案错误很多时候问题就出在输入流末尾有没有多余换行、回车符\r是不是混进了单词里。先说结论用nextLine()和readLine()都能正确处理行尾的\r\n这两类方法会自己把行结束符剥掉不需要专门删\r。容易出问题的反而是sc.next()它按空白分隔一旦题目允许空行或单词后有额外空格行为就不符合预期。所以对一行一个单词的题统一用整行读取。还有很实际的情况判题系统给的输入文件末尾通常有个换行甚至样例复制下来时混进了看不见的空格。我的排查习惯是先不排序只把读入的每个单词用word.length()打印出来确认读进来的确实是你想要的 n 个单词、长度都对再加排序逻辑。如果仍然 WA就先检查输入层别盯着排序对不对瞎猜。4.2 Comparator 的规则一致性一个反例排序规则这块最容易踩的坑是 Comparator 不自洽。比如有人想按最后一个字母排序于是写了个只比较a.charAt(a.length() - 1)的比较器这本身没问题但如果在这个比较器里又掺杂了其他条件且这些条件互相矛盾排序结果就可能乱序甚至直接抛异常。比较器必须满足三条性质自反性、反对称性、传递性。翻译成人话就是a 和 a 比较必须是 0a 比 b 小则 b 比 a 大a 比 b 小且 b 比 c 小则 a 必须比 c 小。一旦违反JDK 排序在特定输入下可能抛出IllegalArgumentException: Comparison method violates its general contract!我在带同学调代码时遇到过典型的例子有人先比单词长度长度相同时不是比字典序而是根据一个外部缓存数组的序号来比两次调用返回结果不一致直接触发异常。所以写自定义比较器时一定要保证它纯函数化——同样的两个对象任何时候调用都返回同样的结果不要依赖外部状态。4.3 重复单词手写快排的死穴字典里当然可以出现重复单词题面没说单词互不重复。而重复元素恰好是朴素快排的经典死穴。全部元素相等时如果分区逻辑写得不好快排会退化成 O(n²) 的平方级操作十万个相同单词面前直接超时。JDK 的排序实现对重复元素做了专门优化自己写快排就必须格外小心这点。第 5 部分我会给出一个在重复元素下不会死循环的写法。如果你的题目变体要求统计每个单词出现次数排序后线性扫描一遍即可——遇到相同元素就计数遇到不同元素就输出前一组并重新计数顺带把去重也做了。4.4 稳定排序到底稳的是什么另一个容易混淆的点教科书快排是不稳定排序而 Java 对字符串数组排序用的稳定排序。这两个概念如果你已经很熟可以跳过不熟的话我举个例子。假设排序对象不只是单词本身而是一个自定义类比如单词 它出现在原文本中的行号。你先把数据按行号排好再按单词排序。如果排序是稳定的字母相同的单词会保持原来的行号顺序如果是不稳定的顺序就会被打乱原始信息就丢了。所以当排序对象是对象数组或 List 时JDK 选择稳定排序实现不只是为了性能更是为了支持这种先按一个条件预处理再按另一个条件排序的用法——第 3.3 节先长度后字典序正是利用了稳定性这层能力。5. 把java sort和快排真正对上号5.1 快排在单词排序里是怎么工作的现在回到标题里那个快排。你可以把快排理解成一条流水线先随便从数组里抓一个单词当基准 pivot把比它小的放到左边比它大的放到右边然后对左右两半分别重复这个过程直到每个子数组都只剩一个元素。举例有一组单词[pear, apple, orange, banana, mango]假设基准是中间的 orange一轮分区后变成[banana, apple, mango] [orange] [pear]具体左右顺序取决于分区写法。然后左边三个再找基准、再分右边一个直接结束。递归到最后任意两个相邻单词都满足左边小于右边整个数组就自然有序了。关键点在于比大小这件事。String 之间的比较交给compareTo快排只负责决定策略比 pivot 小就往左放。这就是Java 的 sort 用快排这句话在概念上没错的原因——排序器本身是快排框架元素怎么比大小由元素自己的 compareTo 决定。5.2 手写快排最容易翻车的三个细节如果你决定课后手动实现一版快排下面几个坑几乎必踩。直接给你一个可用的版本public static void quickSort(String[] arr, int left, int right) { if (left right) { return; } String pivot arr[(left right) 1]; int i left; int j right; while (i j) { while (arr[i].compareTo(pivot) 0) { i; } while (arr[j].compareTo(pivot) 0) { j--; } if (i j) { String tmp arr[i]; arr[i] arr[j]; arr[j] tmp; i; j--; } } quickSort(arr, left, j); quickSort(arr, i, right); }调用方式quickSort(words, 0, words.length - 1);。这段代码看似朴素但有三个细节值得记下来内层 while 用和比较不是和。等于 pivot 的元素不交换因此相等元素不会触发死循环。全部元素相同时i 和 j 会在扫描到 pivot 的相等元素后停住交换并收缩正常退出。递归区间是[left, j]和[i, right]。因为中间可能有一块等于 pivot 的区域被两侧指针共同跨过如果递归成[left, i - 1]和[j 1, right]会把一些元素丢掉。选 pivot 用(left right) 1而不是(left right) / 2。两者在不溢出的情况下等价但无符号右移写法更保险也顺带表达了取中间位置的意思。还有一个代码里看不到但直接影响性能的点当数组接近有序时朴素快排退化成 O(n²) 的主要原因是 pivot 选到极端值。教科书的经典优化是三数取中——从首、中、尾三个位置选出中间值当 pivot。手写版本只要加上这一条面对已经有序的输入就不会那么难看。5.3 JDK 的 sort 和教科书快排不是一回事最后必须说清楚一件事JDK 的 Arrays.sort 并不等于你手写的那种朴素快排。对int[]、long[]这类基本类型数组现代 JDK 使用双基准快排Dual-Pivot Quicksort一轮分区选两个 pivot把数组分成三段平均性能比单基准快排更好但不是稳定排序。对String[]这类对象数组实际走的是 TimSort——一种融合了归并排序优势的稳定排序算法不是快排。为什么对象数组反而不用快排因为对象比较通常比基本类型比较贵稳定排序在先按一个条件排、再按另一个条件排的场景里优势巨大工程师更看重稳定性和最坏情况表现。所以严格讲Java sort 快排这个说法是教科书和 OJ 题面的简化表达。把它理解成sort 方法背后的排序框架包含快排思路可以但你不能说 java sort 对字符串数组用的就是快排。面试时能把这个区别讲清楚比背出十行快排代码更能说明功底。5.4 一个验证手写排序的正确打开方式写完手写快排后怎么确定它和 Arrays.sort 结果真的一致我建议用对拍写个测试程序生成一组随机单词放进两个数组一个用Arrays.sort一个用你的quickSort最后用Arrays.equals比较结果。多跑几百组随机数据再补三组特殊数据——全部相同、已经有序、完全逆序这三种输入是手写快排最容易出问题的场景。我当时学习时就是用这个办法抓到了自己两个隐藏的死循环 bug。后来每次改排序相关的代码第一件事就是跑对拍比任何静态检查都直接。这个习惯放在任何涉及排序的作业里都通用。回到这道 7-2交作业时放心用Arrays.sort课后再把快排默写一遍再拿第 5.2 节的版本跑一遍对拍整个API 使用 原理理解的闭环就完整了。以后再看到任何带快排两个字的题目你都能做到心里有底而不是只停留在会掉 Arrays.sort这一层。