快速排序与归并排序：分治策略、Java实现与工程选型对比

假设你面前摆着一张已经被打乱的《蒙娜丽莎》原图被裁成上千个小方块每个方块背面都标着它在原图中的位置编号。现在要做的就是按照编号把这些碎片重新排回去让蒙娜丽莎重新出现在你面前。这个过程不需要艺术鉴赏力只需要一个可靠的排序规则。排序算法做的就是这件事。所有排序算法中快速排序Quick Sort和归并排序Merge Sort又是最经典、最常被拿来对比的两个。很多人能背出快排代码却说不清为什么归并排序必须开额外数组知道归并是稳定排序却解释不了快排为什么不稳定。这些困惑的根源通常是没有把算法放到一个具体的“重组”场景里想清楚。这篇文章用“重组蒙娜丽莎”作为主线先讲透两种算法的分治策略差异再给出 Java 实现、复杂度对比以及一个把图片裁块、打乱、再用排序恢复的完整 Demo。读完你会得到一个明确判断快速排序靠“分界”缩小问题归并排序靠“有序合并”逐步还原选哪个取决于你的数据特征、内存压力和对稳定性的要求。1. 这篇文章真正要解决的问题CSDN 上关于快速排序和归并排序的文章已经很多但大部分停留在“贴代码 画流程图”层面。真正容易卡住开发者的是下面这几个问题第一边界记不住。quickSort(arr, low, high)到底传不传high - 1while (i mid j right)要不要等号partition写完了为什么数组还是乱序这些边界问题不解决代码只能靠硬背。第二只理解“递归”不理解“分治”。递归二路归并排序看起来就是“自己调自己”但如果不明白归并发生在递归返回之后就会觉得代码像魔法。第三稳定性理解不到位。很多文章说“归并稳定快排不稳定”但没说清楚稳定性到底在什么场景下重要。等你做按多个字段排序的对象数组时才意识到这是个坑。第四选型没有依据。同样是 O(n log n) 级别为什么 Java 的Arrays.sort()对基本类型和对象类型用了不同策略为什么大数据外部排序首选归并这些问题需要一层一层拆开看。本文不会只给答案而是先建立一个“重组碎片”的心智模型再把代码、边界、复杂度和工程选型全部串起来。读完你不仅能手写代码还能说清楚每一步为什么不会越界以及项目中该选谁。2. 先理解“重组蒙娜丽莎”排序到底在做什么先明确一个抽象任何排序问题都有三个要素。待排序集合比如一堆蒙娜丽莎碎片或者一个 int 数组。比较键key碎片上是否有空间值得注意编码的“背面编号”、对象的年龄、字符串的字典序都可以作为排序依据。全序关系任意两个元素通过比较能够确定谁应该在前面。所谓排序就是根据 key 把无序集合重新排列成递增或递减序列。用蒙娜丽莎举例最直接的做法是把图片按blockSize * blockSize像素切块每一块记录自己的“原始位置编号”然后随机打乱整个碎片数组。此时碎片数组是无序的但每块碎片的编号还保留着。接下来只要调用一个排序算法按编号从小到大排列碎片再按数组顺序绘制回画布一张蒙娜丽莎就重新出现了。这个例子看起来很简单但它精确反映了排序的本质排序只是按照某个 key 把元素放到正确顺序它不关心元素内部的画面、内容、结构。这也是为什么两个经典分治排序可以套用在几乎所有数据上。从策略上看两种算法都在“分治”但分和合的方式完全不同快速排序先选一个基准元素把数组分成左小右大的两个区间再递归处理每个区间。分的过程已经让基准元素到了最终正确位置合的过程几乎不需要额外工作。归并排序先把数组对半拆到只剩一个元素然后在递归返回时两两合并。分的过程不做交换真正的工作发生在“合”的阶段。简单记成一句话快排是“边分边排”归并是“拆到最小再拼”。还有一个概念要第 2 章就点出来否则后面容易卡住稳定性。稳定排序指的是如果两个元素 key 相同排序后它们的前后顺序保持不变。归并排序在合并时遇到相等元素可以先取左半部分所以能保持稳定性。快速排序在分区过程中会反复交换元素无法保证相等元素的相对位置所以它不稳定。在“重组蒙娜丽莎”场景里碎片编号是唯一的稳定性没有意义。但如果你先按“年级”再按“分数”给一个学生数组排序第二趟排序必须是稳定的。这个坑在后面会展开。3. 快速排序选基准、分两侧、再递归3.1 核心思想基准元素确定位置快速排序是 Tony Hoare 在 1959 年提出的核心操作是 partition分区。在蒙娜丽莎例子中分区可以这样理解从一堆碎片中随便拿起一块把它当作基准。然后遍历其余碎片编号比基准小的放到左边一堆编号比基准大的放到右边一堆。做完之后基准碎片所在的位置就是它在最终排序序列中的正确位置因为左边所有碎片编号都比它小右边所有碎片编号都比它大。接着对左堆和右堆分别重复这个过程直到每一个区间只剩下一个元素。关键点在于每完成一次 partition基准元素不需要再移动。这是快排比很多简单排序快的原因一个元素一次分区后就已经“归位”。3.2 时间复杂度和最坏情况平均时间复杂度O(n log n)。最坏时间复杂度O(n²)。当输入已经有序或逆序且每次都选中最大或最小元素作为基准时分区极度不均匀递归深度退化为 O(n)。空间复杂度严格说不是 O(1)递归需要栈空间平均 O(log n)最坏 O(n)。稳定性不稳定。最坏情况在真实开发中并不仅是一个理论值。如果手写快排时固定取arr[high]作为基准对一个已经有序的数组排序性能会迅速劣化成冒泡级别。这也是为什么工程实现要用随机基准、三数取中或者在小区间改用插入排序。3.3 Java 实现经典 Lomuto 分区下面给出一个闭区间[low, high]实现这种写法最容易记忆也便于和归并排序统一。public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low high) { return; } int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } private static int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, high); return i 1; } private static void swap(int[] arr, int a, int b) { int tmp arr[a]; arr[a] arr[b]; arr[b] tmp; } }这段代码有几个需要特别说明的地方递归出口是low high不是low high。因为pivotIndex - 1可能小于low用更稳。i初始化为low - 1它指向“已经确认小于基准的最后一个位置的左边”。每次找到一个小于基准的元素先i再交换。循环结束后i 1就是基准元素该在的位置把arr[i 1]和arr[high]交换基准归位。这里的arr[j] pivot没有取等号导致相等元素只会被放到一侧能减少无用交换但也会让重复元素场景下递归更不平衡。处理重复元素更稳的是后面要说的三路快排。不同的快排写法还有 Hoare 分区、双轴快排等但 Lomuto 版代码最简单适合面试先写出正确实现。4. 归并排序拆到底、两两合并、层层归位4.1 核心思想先拆分再合并归并排序的英文名是 Merge Sort核心操作是 merge合并。它是一种典型的“递归二路归并排序”。回到蒙娜丽莎碎片场景先把整堆碎片从中间分成两堆让两堆分别继续对半拆直到每一堆只剩一个碎片。只有一个碎片时它天然有序。然后在递归返回过程中把两个有序堆合并成一个更大的有序堆。合并时比较两个堆最前面的碎片编号谁小先取谁。这个操作反复执行最终整堆碎片变成一个全局有序序列。注意区分两个阶段拆分阶段不移动任何元素只计算 mid递归切分。合并阶段真正排序发生在递归返回之后通过 merge 把两个有序子数组归并。这也是“递归二路归并排序”这个名字的来源二路是指每次合并两个有序区间递归是指不断递归拆分直到区间只剩一个元素。4.2 时间复杂度和空间复杂度时间复杂度无论最好、最坏、平均都是 O(n log n)。因为每次拆分都能把问题规模减半而每一层的合并总耗时是 O(n)递归树深度是 log n。空间复杂度O(n)。合并时需要临时数组这是归并排序最明显的缺点。稳定性稳定。合并两个有序数组时如果arr[i] arr[j]先取左半部分的元素相等元素不会发生交换。适用性尤其适合链表排序和外部排序。链表中归并不需要额外线性空间理论上不需要额外数组外部排序中可以把数据分批读入内存合并有序片段。4.3 Java 实现递归合并public class MergeSort { public static void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } private static void merge(int[] arr, int left, int mid, int right) { int[] tmp new int[right - left 1]; int i left; int j mid 1; int k 0; while (i mid j right) { if (arr[i] arr[j]) { tmp[k] arr[i]; } else { tmp[k] arr[j]; } } while (i mid) { tmp[k] arr[i]; } while (j right) { tmp[k] arr[j]; } System.arraycopy(tmp, 0, arr, left, tmp.length); } }代码解释mid left (right - left) / 2而不是(left right) / 2是为了防止 left 和 right 很大时整型溢出。merge中临时数组长度是区间长度所以空间复杂度按所有递归层加起来是 O(n log n)不注意每次递归的临时数组合并后会释放理论峰值是 O(n)。不过如果不释放 reference峰值会更大。在 Java 中每次 merge 新建数组递归栈中的上层等到下层返回后才创建自己的数组所以同一时刻只有一条递归链上的临时数组叠加总内存接近 O(n)。如果再考虑 GC实际峰值可能更高工程上会复用同一个临时数组来优化。arr[i] arr[j]是稳定性的关键。如果改成遇到相等元素会先取右半部分稳定性就被破坏了。两个剩余 while 循环处理一边已经取完、另一边还有剩余的情况。因为左右两个子数组都已经有序直接复制剩余部分即可。从蒙娜丽莎的角度看归并排序就是每个人先把一小摞碎片排好然后两个人不断合并成一大摞。谁都想做“合”的动作所以它天然适合稳定场景。5. 快速排序和归并排序的核心对比用表格把两种算法放在一起看会更直观。对比维度快速排序归并排序分治策略先分区再递归先递归拆分再合并平均时间复杂度O(n log n)O(n log n)最坏时间复杂度O(n²)O(n log n)最好时间复杂度O(n log n)可优化到 O(n)O(n log n)空间复杂度O(log n) 平均递归栈O(n) 临时数组稳定性不稳定稳定排序方式原数组内部交换借助额外数组归并适用场景内存紧张、数据在内存中要求稳定、链表排序、外部排序最怕什么几乎有序且固定选最大/最小为基准内存有限数据量巨大接下来回答一个很多面试者被问住的问题既然归并排序最坏也是 O(n log n)为什么实际工程中快速排序反而更常见答案有三个层面。第一内存局部性。快排在分区时对数组做原地交换操作集中在一小段连续内存上CPU 缓存命中率高。归并排序要先写临时数组再 copy 回去写入和读取跨了两块内存区域缓存命中率低。第二空间成本。快排平均只需要 O(log n) 的递归栈空间归并要额外申请 O(n) 数组。如果数据量是 1 亿个 int归并需要额外约 400MB 内存这在很多服务端环境里是不可接受的。第三工程优化。真实世界的快排并不是简单选最后一个元素作基准。Java 的Arrays.sort(int[])底层使用双轴快排会对分区大小、有序性做检测小数组还切换到插入排序基本避免最坏退化。归并则被封装进 TimSort用于对象数组排序。但这不代表归并弱于快排。归并排序的优点是可预测无论输入如何都是 O(n log n)稳定而且适合不能随机访问的场景。比如排序链表归并排序只需要 O(1) 额外空间排序磁盘上的大文件外部归并排序是标准方案。因此选快排还是归并本质是选稳定性与最坏情况保障还是选内存效率与缓存表现。6. 代码实战用随机数组验证两种排序前面两章分别给了快排和归并的类。现在用一个主类把它们串起来验证排序结果正确并简单统计耗时。import java.util.Arrays; import java.util.Random; public class SortCompare { public static void main(String[] args) { int n 200000; int[] base new Random(42).ints(n, 0, 100000).toArray(); int[] arr1 base.clone(); long start1 System.currentTimeMillis(); QuickSort.quickSort(arr1, 0, arr1.length - 1); long end1 System.currentTimeMillis(); System.out.println(QuickSort 耗时: (end1 - start1) ms); System.out.println(QuickSort 排序结果正确: isSorted(arr1)); int[] arr2 base.clone(); long start2 System.currentTimeMillis(); MergeSort.mergeSort(arr2, 0, arr2.length - 1); long end2 System.currentTimeMillis(); System.out.println(MergeSort 耗时: (end2 - start2) ms); System.out.println(MergeSort 排序结果正确: isSorted(arr2)); System.out.println(两者结果一致: Arrays.equals(arr1, arr2)); } private static boolean isSorted(int[] arr) { for (int i 1; i arr.length; i) { if (arr[i] arr[i - 1]) { return false; } } return true; } }运行方式javac QuickSort.java MergeSort.java SortCompare.java java SortCompare预期输出大致是两行耗时和两个 true。不同的机器、JDK 版本结果不同但排序结果必须是 true。这段代码更重要的是提供一种验证思路任何排序算法写完先拿随机数组测再用Arrays.equals跟 JDK 自带的排序结果比对。这是一种最简单的“对拍”验证。7. 进阶实战把蒙娜丽莎切碎再排序拼回去现在进入文章主线对应的完整示例。思路如下用ImageIO.read()读取一张图片假设是mona_lisa.png。按blockSize把图片切成很多小方块每个方块记录原始位置编号index。用Collections.shuffle()将方块数组随机打乱拼成shuffled.png模拟已经打乱的蒙娜丽莎。调用快速排序把方块按照index重新排好。将排序后的方块按数组顺序绘制到画布输出recovered.png。这里的关键是排序的对象是图片碎片而比较的 key 是碎片原本在画布中的位置编号。完整代码如下import javax.imageio.ImageIO; import java.awt.Graphics; import java.awt.image.BufferedImage; import java.io.File; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Random; public class RebuildMonaLisa { static class Block { int index; BufferedImage image; Block(int index, BufferedImage image) { this.index index; this.image image; } } public static void main(String[] args) throws Exception { BufferedImage original ImageIO.read(new File(mona_lisa.png)); int width original.getWidth(); int height original.getHeight(); int blockSize 40; int rows height / blockSize; int cols width / blockSize; if (rows 0 || cols 0) { System.out.println(图片太小请增大 blockSize 或换一张大图); return; } int total rows * cols; Block[] blocks new Block[total]; int idx 0; for (int r 0; r rows; r) { for (int c 0; c cols; c) { BufferedImage sub original.getSubimage( c * blockSize, r * blockSize, blockSize, blockSize); blocks[idx] new Block(idx, sub); idx; } } ListBlock blockList new ArrayList(List.of(blocks)); Collections.shuffle(blockList, new Random(2024)); Block[] shuffled blockList.toArray(new Block[0]); saveImage(compose(shuffled, rows, cols, blockSize, width, height), shuffled.png); quickSortByIndex(shuffled, 0, shuffled.length - 1); saveImage(compose(shuffled, rows, cols, blockSize, width, height), recovered.png); System.out.println(完成: shuffled.png 和 recovered.png 已生成); } static void quickSortByIndex(Block[] arr, int low, int high) { if (low high) { return; } Block pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j].index pivot.index) { i; Block tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } } Block tmp arr[i 1]; arr[i 1] arr[high]; arr[high] tmp; int pivotIndex i 1; quickSortByIndex(arr, low, pivotIndex - 1); quickSortByIndex(arr, pivotIndex 1, high); } static BufferedImage compose(Block[] blocks, int rows, int cols, int blockSize, int width, int height) { BufferedImage output new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB); Graphics g output.getGraphics(); for (int r 0; r rows; r) { for (int c 0; c cols; c) { Block block blocks[r * cols c]; g.drawImage(block.image, c * blockSize, r * blockSize, null); } } g.dispose(); return output; } static void saveImage(BufferedImage image, String path) throws Exception { ImageIO.write(image, png, new File(path)); } }这段代码要解释几个点getSubimage()返回的子图与原图共享像素数据但因为我们只是读取并绘制不会修改原图。rows height / blockSize会丢弃图片右侧和底部不足一块的像素。如果原图宽 800、高 600、blockSize 40正好能整除如果宽高是 810会丢弃 10 像素边缘。compose按blocks[r * cols c]顺序绘制。画布上第 r 行第 c 列的位置应该展示原始位置编号为r * cols c的碎片。打乱后第一次调用 composeblocks 数组是乱序的所以生成乱图排序后第二次调用 composeblocks 数组顺序已经恢复所以生成原图。如果想得到完全可复现的随机打乱效果给Collections.shuffle传入一个固定Random(2024)每次运行结果一致不传则每次随机。如果不想真的准备一张蒙娜丽莎图片也可以把图片换成任意一张喜欢的插画甚至用一个纯色渐变图。重点是观察“打乱再恢复”的过程而不是图片内容本身。如果想换成归并排序恢复图片只需把quickSortByIndex替换成按Block.index比较的归并版本因为 Block 是一个引用类型写通用比较器稍微复杂一点。更简洁的做法是只对int[]索引数组排序例如Integer[] order new Integer[total]; for (int i 0; i order.length; i) { order[i] i; } // 用快排或归并让 order 按 shuffled[i].index 排序这个思路留给读者去扩展。核心已经明确快排和归并排序的对象可以是任意数据只要你能定义一个比较 key。8. 运行结果与效果验证运行RebuildMonaLisa后会得到两个文件shuffled.png蒙娜丽莎碎片被完全打乱画面呈现出许多小块随机排列的“抽象”效果。recovered.png碎片恢复原顺序视觉上应与原图一致。怎么判断恢复是否成功肉眼观察最直接如果recovered.png和原图几乎一模一样说明排序逻辑正确。但更严谨的做法是代码校验。可以在 main 方法末尾增加如下逻辑boolean ok true; for (int i 0; i shuffled.length; i) { if (shuffled[i].index ! i) { ok false; break; } } System.out.println(恢复验证结果: ok);因为排序完成后数组第 i 个位置的碎片其index必须正好等于 i。如果任何一个位置不满足说明分区或交换逻辑有 bug。如果第一次运行发现recovered.png不对优先检查下面几处partition中arr[j].index pivot.index是否写成了普通整型数组的逻辑。递归区间是否传错quickSortByIndex(shuffled, 0, shuffled.length - 1)这行是否在高位下标处写成了length。compose中是否使用了blocks[r * cols c]而不是blocks[c * rows r]后者会导致图片转置或错位。从排序正确性来说只要一个小的随机 int 数组能排对图片恢复基本不会出问题。这也说明算法做对一次就能复用到完全不同类型的数据上。9. 常见问题与排查思路问题现象可能原因排查方式解决方案快速排序在数据量很大时栈溢出基准选得不好递归深度退化成 O(n)打印递归区间大小观察是否长期接近原始长度随机选择基准或使用三数取中小区间切换插入排序归并排序内存占用过高每次 merge 都新建临时数组且数据量巨大用-Xmx调低堆内存复现观察堆内存曲线复用同一个临时数组或改用原地归并注意复杂度变化快排结果部分有序但仍有错位partition 返回值位置错误或递归区间边界写错对固定小数组逐步打印每轮 partition 结果统一使用闭区间[low, high]递归时传pivotIndex - 1和pivotIndex 1归并结果不是稳定排序merge 比较时写成arr[i] arr[j]构造两个相同 key 的对象数组验证顺序改成arr[i] arr[j]图片恢复后颜色不对或图像错位blockSize 不能整除宽高导致边缘被裁剪对比 recovered.png 和原图分辨率选择能整除宽高的 blockSize或单独处理边缘块排序耗时与预期差距大输入数据几乎有序且固定选最后一个为基准用有序数组测试观察是否退化为 O(n²)随机基准、三数取中、局部插入排序递归二路归并理解不透只知道递归不理解 merge 阶段发生在返回后在 merge 前后打印 left、mid、right 和数组片段手动模拟一个 4 元素数组的递归和合并全过程这些问题是新手最容易踩的坑也是面试手写排序时最容易翻车的地方。10. 最佳实践与工程建议10.1 生产环境优先用标准库排序实际项目里不要自己写快排去处理对象数组。JDK 已经提供了高效的排序实现对int[]、long[]等基本类型数组Arrays.sort()使用双轴快排。对Object[]Arrays.sort()使用 TimSort它是稳定排序。Collections.sort()同样使用 TimSort。手写算法的主要场景是面试、教学、理解底层原理以及一些特殊环境比如不能使用标准库的限制性编程环境。如果生产代码非要自己写一定要做好测试和压测。10.2 稳定性选型如果排序对象是对象且有多字段排序需求推荐使用稳定排序。例如先按id排序再按score排序。第一趟结果经过第二趟稳定排序后相同score的用户仍然保持id升序。如果第二趟用不稳定排序第一趟的顺序就会被破坏用户id顺序可能乱掉。归并排序和 TimSort 都是稳定排序适合这种场景。10.3 大数据与内存受限场景数据量超过内存容量时归并排序是外部排序的基础。外部归并排序把大文件拆成多个有序片段再多路归并成一个文件这种能力快排不具备。反过来如果数据完全在内存中且内存紧张快排更合适因为它不需要额外 O(n) 空间。10.4 重复元素很多怎么办经典快排在重复元素很多时效率下降因为基准周围的重复元素会不断参与递归。工程上可以用三路快排三向切分小于基准的放左边。等于基准的放中间。大于基准的放右边。这样所有与基准相等的元素一次分区后全部归位递归只处理小于和大于两个区间。Java 的 DualPivotQuickSort 也是基于类似思想通过双基准减少比较次数处理重复元素时性能更好。10.5 手写算法时的测试用例无论面试还是项目验证排序算法至少测这 6 种输入空数组。只有一个元素。已经有序。完全逆序。全部元素相等。随机大数组。对拍验证时可以把自己的排序结果和Arrays.sort()的结果用Arrays.equals()比较。这比肉眼检查可靠得多。10.6 边界记法建议一个最稳定的手写姿势就是在任何递归或循环里都坚持闭区间排序范围是[low, high]。递归出口是low high。快排 partition 循环条件是j high。归并循环条件是i mid j right。不要一会儿用开区间一会儿用闭区间否则最容易出现越界和漏排。11. 总结与后续学习方向现在可以对这两种算法下一个更明确的结论快速排序是靠“找到一个正确的分界线”来缩小问题归并排序是靠“把两个有序序列合并”来从头构建有序序列。它们都是分治法但性格完全不同。快排激进、省内存却不够稳定归并踏实、稳定但必须付出额外空间代价。如果准备面试建议你在 IDE 里用今天文章中的三类例子练习随机 int 数组验证排序正确、图片碎片恢复验证算法作用于真实数据、对拍验证稳定性。尤其是图片恢复这个实验比单纯看代码直观得多。接下来可以继续学习三个方向一是堆排序理解为什么它与快排、归并并列为三大 O(n log n) 排序但实际工程中反而偏弱二是 TimSort研究 Java 和 Python 默认排序到底怎样融合归并和插入排序三是外部排序理解海量数据文件如何在内存不足时完成“重组”。排序算法是数据结构与算法的基础但基础并不等于简单。能解释清楚“为什么相等元素保持顺序很重要”“为什么快排最坏情况会退化”“为什么归并适合外部排序”才算真正吃透了它们。拿一张图片做实验比死记一万遍代码都有用。