“7-2 单词排序”这道题乍一看就是个Java编程练习里的小关卡核心要求无非是给你一堆单词按顺序排好。可真正动手之后你会发现它远不止“调一个sorted就完事”那么简单。里面既有Java集合框架的API选型问题也有字符串比较规则细节更避不开快速排序在实现时的各种边界陷阱。如果你是在准备课程实验、面试手撕代码或者单纯想把排序这层窗户纸捅破这篇内容会从题目拆解到底层原理、再到手写快排的完整代码一次讲透。我自己当年写这道题的时候第一反应也是直接用Collections.sort几行代码搞定交上去也能过。但后来深入研究才发现这个看似简单的实验题恰好是把Java sort体系的入口和快排原理串起来的最佳样本。下面我把整个思考过程、代码实现和踩过的坑都整理一遍。1. 先拆题单词排序到底想让你练什么1.1 题目背后隐藏的三个考点很多同学看到“单词排序”第一反应是“这有什么难的”但题目既然叫“7-2”通常是从教学进度里来的它考察的是三个层面的东西。第一层是API使用能力你会不会正确地调用Java中现成的排序方法并且能自定义比较规则。这里的核心操作是传入一个Comparator或者让存储单词的对象实现Comparable接口。这一层考察的是工程中“会用工具”的基础素养。第二层是算法原理理解标题里明确写了“java sort快排”说明希望你不仅要会用还要理解Java排序底层涉及快速排序的思路。Arrays.sort对基本类型数组确实用的是双基准快速排序算法而对于对象数组则用了经过改良的归并排序TimSort。所以“快排”这个词在Java语境下既有实指也有泛指。第三层是边界情况处理单词排序听起来简单但真实输入里可能有空字符串、重复单词、大小写混排、带空格短语甚至中文单词。这些情况如果不处理排序结果可能不符合直觉或者直接让程序崩溃。1.2 用API排序还是手写快排答案并不唯一在做这个题的时候你会面临一个选择直接用Arrays.sort/Collections.sort还是自己实现一遍快速排序。从任务完成角度直接调API最稳也不容易出bug。但从学习角度我建议你两种都做一遍——先用API把逻辑跑通再用手写快排加深对分区和递归的理解。实际工程里手写排序的场景极少因为JDK的排序算法经过大量优化远比普通开发者自己写的版本可靠。但在面试场景里手写快排是高频题。所以这道题的“标准操作”应该是理解API用法能讲解底层快排原理并且能独立写出一个不越界、不死循环的快排版本。2. Java的sort家族你天天用但未必知道它底层是快排2.1 Arrays.sort 处理对象数组和基本类型数组是两套逻辑很多同学用Arrays.sort用得很溜但没注意过一个细节它针对不同类型的数据底层策略是不同的。如果你对一个int[]排序JDK使用的是Dual-Pivot Quicksort双基准快速排序这也是标题里“快排”二字最直接的出处。双基准快排和传统单基准快排的区别在于它一次选取两个基准值把数组划分为三个区间这样能减少递归深度同时在处理重复元素时表现更好。但如果你对一个String[]这样的对象数组排序底层就不再是快排了对象数组走的是ComparableTimSort也就是归并排序的优化版本。这个选择的背后逻辑很实际对象比较通常比数值比较慢归并排序能保证稳定性相同元素的相对位置不变而快排做不到稳定。2.2 Collections.sort 又有自己的路径Collections.sort接收List类型底层会调用List.sort在ArrayList场景下最终也会落到Arrays.sort对对象数组的处理逻辑即TimSort路线。也就是说不管你是用集合还是数组只要排的是String这种对象底层都不是快速排序而是归并排序家族。这里很多人会有疑问那标题说“java sort快排”是不是错的了其实不是。教学场景里的“java sort快排”更多是指“Java中sort的底层思想跟快排相关”同时鼓励你自己动手实现快排来理解排序过程。如果你用Arrays.sort(new int[]{...})你确实是在用JDK的双基准快排。2.3 双基准快排在性能上做对了什么JDK里的双基准快排并非一开始就拍脑袋设计出来它考虑了实际数据的几个痛点如果数据基本有序传统快排容易退化到O(n²)如果数据里重复元素特别多传统快排的分区效率也会拉胯。双基准快排配合“近乎有序时改走插入排序”的策略让整体表现稳定很多。讲到这块我建议你做个实验生成一个一百万元素的有序数组分别用Arrays.sort和手写单基准快排去跑你会发现JDK版本几乎瞬间完成而手写快排在运气不好时会栈溢出或慢到无法接受。这个实验能直观感受到工程级排序算法的讲究。3. 手写快排实现单词排序完整可运行的方案3.1 先定比较规则字典序到底怎么比排序之前必须先明确“单词大小”的定义。中文语境里说字典序基本对应英文的lexicographic order也就是从左到右逐字符比较遇到第一个不同字符时根据该字符的Unicode码点大小决定结果。Java字符串的compareTo方法实现的就是这个逻辑。这里有一个容易忽略的坑compareTo是区分大小写的大写字母的Unicode码点例如A65小于小写字母例如a97。所以“Apple”和“apple”排序时“Apple”会排在前面。如果你的题目要求不区分大小写排序就得用compareToIgnoreCase或者自己写一个忽略大小写的Comparator。接着还要注意如果两个单词是包含关系比如“app”和“apple”compareTo的处理是较短的串排在前面因为它在较短位置返回长度的差值。这符合我们字典里“apple”排在“application”前面后的直观认知。3.2 手写快速排序的核心代码选定基准与分区快速排序的核心思想可以类比成整理扑克牌先随便抽一张牌当基准然后把比它小的牌放到左边比它大的牌放到右边接着再对左右两堆各自重复这个过程最终整个牌堆就有序了。代码实现上我习惯用Lomuto分区方案它比教科书里那个双向扫描的Hoare方案更不容易写错。完整示例代码如下public class QuickSortWords { public static void quickSort(String[] words, int low, int high) { if (low high) { return; } int pivotIndex partition(words, low, high); quickSort(words, low, pivotIndex - 1); quickSort(words, pivotIndex 1, high); } private static int partition(String[] words, int low, int high) { // 取最后一个元素作为基准值 String pivot words[high]; int i low - 1; for (int j low; j high; j) { // 这里按字典序升序排列 if (words[j].compareTo(pivot) 0) { i; swap(words, i, j); } } swap(words, i 1, high); return i 1; } private static void swap(String[] words, int i, int j) { String temp words[i]; words[i] words[j]; words[j] temp; } }这里分区逻辑的关键点是i指针左边始终是已经确定小于基准值的元素区间j指针负责向后扫描。每次发现一个小于基准值的元素就把它换到左边已处理区的末尾。最后把基准值放到i 1位置它左边全小、右边全大一次分区就完成了。3.3 配一个能跑通的标准输入输出示例快排写好了还得有调用入口。为了贴近实验题的需求我用Scanner读入一行由空格分隔的单词输出一行排好序的结果完整代码如下import java.util.Scanner; public class WordSortDemo { public static void main(String[] args) { Scanner scanner new Scanner(System.in); System.out.println(请输入多个单词用空格分隔); String line scanner.nextLine(); String[] words line.split(\\s); QuickSortWords.quickSort(words, 0, words.length - 1); StringBuilder sb new StringBuilder(); for (int i 0; i words.length; i) { if (i 0) { sb.append( ); } sb.append(words[i]); } System.out.println(排序结果 sb); } }这里的line.split(\\s)用正则分割能自动处理多个空格连续出现的情况。如果题目给的单词是每行一个那只要换成循环读取再存进数组或List就行。3.4 排序正确性验证手工数据走一遍写完代码之后别着急交先用自己构造的数据验证一遍。比如输入pear apple orange banana脑子里过一遍第一次分区选“banana”为基准比它小的“apple”放左边其余放右边递归处理左右区间最终结果应该是apple banana orange pear。跑一次代码对比结果和预期一致后再换更复杂的数据测试。我验证的时候还会专门准备一种极端数据比如输入全相同的单词test test test。这个场景能让不少手写快排直接翻车因为如果比较条件写成而不是循环里会出现大量无意义的交换但至少不会死循环。如果基准选取得不好比如每次都选到当前区间最后一个元素而数据本身已经有序就会导致递归深度变成O(n)甚至栈溢出。这些都是面试官最喜欢追问的点。4. 排序细节与边界情况容易翻车的几个点4.1 空字符串、单字符和重复单词处理在实际输入里空字符串并不是不可能出现。比如用户连续输入两个空格split(\\s)不会产生空串但如果用split( )就会产生。空字符串的compareTo行为很特殊它永远比任何非空字符串都小因为长度是0比较时返回的是负数。这个逻辑其实合理但如果题目要求“忽略空串”你就应该在排序之前先把它们过滤掉。单字符单词也值得一提比如a和b排序很简单但如果混着abc和ac就要明确“先比首字符再比后续字符”。Java的compareTo对这个场景天生支持不需要你自己循环遍历字符数组。重复单词是最容易被忽视的。用手写快排处理重复元素时如果你用Lomuto分区且比较条件是 0那么重复元素会被分到基准值右边不会出问题。可如果用 0重复元素会频繁和基准值交换虽然结果仍然正确但性能会退化。处理大量重复数据的正确姿势是三路快排——把等于基准值的元素单独放到中间区间这样左右递归规模都能显著缩小。4.2 大小写混合排序到底该不该忽略大小写你从键盘输入一堆单词时很难保证用户全按小写输入。默认的字典序区分大小写这导致“Zoo”会排在“apple”前面因为大写字母的Unicode码点整体小于小写字母。这在很多实际业务场景里并不符合用户预期用户通常希望忽略大小写让“Apple”和“apple”挨在一起。解决方案很简单Arrays.sort(words, String::compareToIgnoreCase);但注意compareToIgnoreCase只是把字符统一转成大写或小写后再比较它不会改变原串。所以排序后的结果里apple和Apple相对顺序可能会受原始输入顺序影响因为compareToIgnoreCase认为它们相等时最终顺序取决于排序算法是否稳定。如果你用手写快排这种稳定性是没有保证的。4.3 中文单词排序用compareTo够吗这一块是很多同学会忽略的。如果你用中文单词做实验比如“苹果”“香蕉”“橙子”compareTo依然能排序因为JDK对字符串的比较是基于Unicode码点中文也在Unicode范围内。但结果可能不符合拼音字典序。比如“苹果”的拼音是ping香蕉是xiang橙子是cheng按Unicode码点排出来可能是“橙子”“苹果”“香蕉”虽然碰巧顺序看起来合理但它其实不是按拼音来的。如果你希望按拼音排序就需要引入Collatorimport java.text.Collator; import java.util.Locale; Arrays.sort(words, Collator.getInstance(Locale.CHINESE));这个类的底层用到了ICU的排序规则能按拼音、笔画等多种规则排序。对应到这个实验题我建议题目没明确要求拼音排序时直接用默认字典序但你要知道还有这么一层选择。4.4 时间复杂度和稳定性手写快排的短板手写快排的平均时间复杂度是O(n log n)最坏是O(n²)。最坏情况通常出现在基准值每次都选到当前区间最大值或最小值时比如一个已经升序排列的数组你去选最后一个元素作为基准。解决手段常见的就三个随机选择基准、取首中尾三数取中、在递归区间小于某个阈值时改用插入排序。稳定性方面快速排序是不稳定排序。两个值相等的单词排序后相对位置可能变化。如果你要排的是带序号的数据比如“第1条 apple”“第2条 apple”你肯定不希望排序后两条记录的先后顺序被调换。这时候请选择稳定的归并排序也就是直接使用Collections.sort它底层是稳定排序。5. 实测踩坑记录与排查实录5.1 越界与死循环手写快排最容易翻车的地方我第一次手写这个题的时候犯了两个经典错误。第一个是quickSort递归入口没有判断low high导致空区间继续递归最终栈溢出。第二个是分区后错误地把pivotIndex本身又放回递归区间导致它永远无法收敛。排查这类问题的通用办法是打印每一次分区的边界值。我发现很多同学不会定位死循环其实只要在partition方法里加一句System.out.println(low low high high)就能非常直观地看到程序卡在哪一层递归。还有一种越界情形是基准值的compareTo调用抛空指针。如果你把数组里某个元素设置成null且没有做判空处理排序过程会直接抛NullPointerException。应对方法是在排序前过滤掉null或者自定义Comparator时判断a null ? 1 : -1这类规则。5.2 输入数据带隐藏字符的坑这个坑我印象很深。一次实验课上有人反馈说代码明明没问题但排序结果看起来不对——输出里有些单词前面好像多了一个不可见字符。排查后发现问题出在输入数据来源Windows环境下的文本文件行尾有\r\n而Scanner.nextLine()默认不会把\r去掉。这个\r会粘在单词后面导致比较结果错乱。解决方式很简单读进来之后做一次清理用word.replace(\r, )或者word.trim()。这个例子告诉我们动手写排序逻辑前先确保原始数据结构是干净的。5.3 比较器写反导致倒序输出用Arrays.sort的时候很多人喜欢匿名内部类或Lambda自定义Comparator结果一不小心就把参数顺序写反Arrays.sort(words, (a, b) - b.compareTo(a)); // 变成了倒序如果你本来想要升序这样写出来的结果是反的。我自己的习惯是最后统一加一个Arrays.sort(words)默认的升序已经能满足实验题要求。只有当题目明确要求倒序或忽略大小写时才去动 Comparator。5.4 问题排查速查表现象可能原因解决思路栈溢出递归结束条件写错或基准值选得极端检查if (low high)改用三数取中排序结果为倒序Comparator参数顺序写反检查(a, b) - a.compareTo(b)的写法空指针异常数组里有null元素排序前过滤或自定义判空逻辑大小写顺序不符合直觉使用了区分大小写的compareTo换成compareToIgnoreCase输出中有看不见的字符Windows行尾\r残留读取后执行replace(\r, )全相同元素排序极慢分区条件用了大量重复交换改用三路快排或在递归小区间走插入排序写在最后的一些经验这道“7-2 单词排序”我前前后后写过三版纯API调用版、手写单基准快排版、三路快排版。每一版写下来对Java排序机制的理解都会深一层。如果让我给正在写这个题的人一个建议那就是不要把目光局限于“让输出结果正确”多追问一下底层为什么这样设计。另外分享一个小技巧如果实验要求里允许使用现成的排序API就不要为了“炫技”去强行手写快排。但手写快排这个能力还是要练因为面试手撕代码时它出现频率极高。平时可以自己在IDE里把这道题反复写几遍重点检查分区逻辑和递归边界写到不用过脑子也能A掉为止。这道题之后你完全可以拿它当跳板再去试试“按频率排序单词”、“最长单词链”等变体你会发现之前掌握的排序基本功比想象中更能复用。