把一张蒙娜丽莎的像素全部随机打乱画面就会瞬间变成满是噪点的“雪花屏”。如果要求你只通过排序算法把它恢复原样你会选用快速排序还是归并排序这个实验看似花哨实际上把排序算法的运行过程变成了一张能“看见”的图哪种算法在逐步恢复图像、哪种算法在中途更接近原图、哪种算法更快都会一目了然。本文将围绕“快速排序 VS 归并排序”这一经典对比展开用 Java 编写一套完整的图像重组实验程序把一张图片打乱后分别用快速排序和归并排序恢复。文章不仅会讲解两种排序算法的核心原理、递归边界和复杂度还会给出可复制的完整代码、运行结果、常见排错思路以及工程选型建议。1. 背景与核心概念1.1 排序算法为什么值得重新学一遍排序算法是计算机科学中最基础、也最常被问到的算法问题。无论是数据库的索引构建、搜索引擎的结果排序还是推荐系统的候选集重排底层都会用到不同种类的排序算法。很多人觉得排序算法在业务开发中很少手写因为 Java、C、Python 都已经提供了成熟的排序库但恰恰因为“有库可用”很多人反而忽略了一个重要事实理解排序的过程是理解递归、分治、时间复杂度和内存开销的最好入口。以快速排序和归并排序为例这是两种最有代表性的分治排序算法。快速排序的平均时间复杂度低、常数小是很多标准库的首选归并排序则稳定、适合外部排序和海量数据。两者常常被放在一起比较但纯粹比较数字很难讲清楚差异。如果能把排序过程直观展示出来理解成本就会降低很多。“重组蒙娜丽莎”实验就是这样一种可视化思路。1.2 快速排序与归并排序的定位快速排序Quick Sort的核心思想是分治每次从待排序区间中选一个基准值pivot把小于基准值的元素放到左边把大于基准值的元素放到右边然后递归处理左右两个子区间。它不需要额外的数组来存储中间结果属于原地排序算法但它的分区过程会破坏元素之间的相对顺序因此是不稳定排序。归并排序Merge Sort的核心思想同样是分治但处理方式完全不同它先把数组持续拆分成两半直到每个子区间只有一个元素然后把相邻的有序区间两两合并成一个更大的有序区间。这个合并过程需要借助额外的临时数组因此空间复杂度更高但合并过程不会打乱相同元素的相对顺序所以归并排序是稳定排序也常被称为“递归二路归并排序”。两种算法一个追求“平均快”一个追求“稳定且可靠”。算法面试中这两道题几乎是必考题目工程实践中很多排序库也会根据数据特征在快速排序和归并排序之间做出取舍。1.3 什么是“重组蒙娜丽莎”“重组蒙娜丽莎”并不是图像修复而是一个排序可视化实验。一张图片由很多像素组成。我们可以把每个像素看成独立的数据项并且给每个像素记录一个原始位置编号。随后把所有像素随机打乱图片便无法辨认。这时候只要把像素按照“原始位置编号”重新排序图片就能恢复原样。关键点在于恢复图像本身不依靠任何图像算法只依靠排序算法。快速排序和归并排序拿到的是同一组乱序像素谁能更快、更稳定地把它们按原始编号排列好谁就相当于更好地完成了“重组”这张画的任务。这个实验的优势是直观普通排序练习面对的是一串数字排序完成后只能用肉眼检查是否升序而图像恢复任务中排序结果可以直接看到。图像从噪点逐渐恢复出轮廓的过程其实就是排序算法内部工作过程的真实反馈。2. 环境准备与版本说明2.1 JDK 与开发工具本文的 Java 示例基于 JDK 8 及以上版本即可运行不依赖任何第三方库。图像读取和写入使用 JDK 自带的javax.imageio.ImageIO像素操作使用java.awt.image.BufferedImage这两个类都包含在标准 JDK 中不需要额外引入 Maven 依赖。开发工具可以根据个人习惯选择IntelliJ IDEAEclipseVS Code Java 插件纯命令行 文本编辑器由于项目不依赖构建工具也可以直接在命令行中使用javac编译、java运行。版本需要根据你的项目实际情况调整本文示例以常见 JDK 8/11/17 环境为例重点演示算法与图像处理的完整流程。2.2 示例项目结构建议创建一个目录来存放实验代码和图片结构如下sort-image-restore/ ├── src/ │ └── ImageSortLab.java ├── mona.png └── output/其中src/ImageSortLab.java是完整实验程序。mona.png是输入图片可以替换成任意 JPG/PNG 图片。output/是程序运行后生成结果的目录包括打乱后的噪点图和恢复后的图片。这里为了便于演示图片直接放在项目根目录。如果使用 IDEA 这类 IDE注意图片路径要以运行时的当前工作目录为基准建议直接使用绝对路径或项目根目录下的相对路径。2.3 测试图片准备理论上任何图片都可以做这个实验但为了让视觉效果更明显需要注意几点图片尺寸不宜过大建议控制在 300 x 300 到 800 x 600 之间。像素太多会明显增加排序耗时不利于快速演示。内容最好有明显轮廓例如人像、动物、风景图。黑白或彩色均可。如果使用 JPG 图片程序输出时会统一保存为 PNG因为排序后的像素包含 ARGB 颜色信息PNG 能更好保留像素数据。本文使用“蒙娜丽莎”作为实验对象因为这幅画属于公有领域且轮廓分明非常适合观察图像恢复过程。你也可以使用任意一张本地图片测试效果只取决于图片内容是否容易辨认。3. 快速排序与归并排序核心原理解读3.1 快速排序选基准分区再递归快速排序的直观过程可以这样理解假设一队人需要按身高从左到右排列。先让队尾的人站出来当基准然后其他人依次和基准比较小于等于基准的人站到左边大于基准的人站到右边。一轮结束后基准左边的人都不高于基准右边的人都高于基准。基准的位置已经正确接下来只需要对左右两队人各自继续执行同样的操作。在代码层面快速排序通常分为两步分区partition和递归quickSort。下面是一个基于 Lomuto 分区方式的 Java 快速排序实现// 快速排序入口 public static void quickSort(int[] arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } // Lomuto 分区以最后一个元素为基准 public 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; int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } } int tmp arr[i 1]; arr[i 1] arr[high]; arr[high] tmp; return i 1; }这段代码中partition返回的pi是基准值最终所在的位置。基准值左边都小于等于它右边都大于它。递归处理左右两侧后整个数组就有序了。快速排序的平均时间复杂度为 O(n log n)最坏情况下会退化到 O(n²)例如数组已经有序且每次都选择最大或最小值作为基准时。通过随机选择基准或“三数取中”法可以有效降低最坏情况出现的概率。3.2 归并排序先拆分后有序合并归并排序的思路和快速排序正好相反。快速排序是先粗略分区然后再递归细化归并排序则是先把数组不断拆到最小再通过合并逐步构建有序序列。直观看归并排序像一场淘汰赛先两两组队排序再四四组合并最终合成一个完整有序队伍。下面是 Java 中“递归二路归并排序”的标准实现// 归并排序入口 public static void mergeSort(int[] arr, int left, int right) { if (left right) { int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } } // 合并两个有序区间 [left, mid] 和 [mid1, right] public static void merge(int[] arr, int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int[] L new int[n1]; int[] R new int[n2]; for (int i 0; i n1; i) { L[i] arr[left i]; } for (int j 0; j n2; j) { R[j] arr[mid 1 j]; } int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; i; } else { arr[k] R[j]; j; } k; } while (i n1) { arr[k] L[i]; i; k; } while (j n2) { arr[k] R[j]; j; k; } }merge方法是归并排序的核心。它假设左右两个区间已经各自有序然后使用双指针从左到右依次比较把较小元素写入原数组。因为比较时使用了相同元素的相对顺序不会改变所以归并排序是一个稳定排序。归并排序的时间复杂度稳定为 O(n log n)但每次merge都需要新建临时数组空间复杂度为 O(n)。3.3 两种排序算法的复杂度与特性对比很多初学者容易混淆快速排序和归并排序的适用场景。下面通过一张表来对比它们的核心差异对比维度快速排序归并排序基本思想选基准分区递归处理左右区间拆分子数组两两有序合并平均时间复杂度O(n log n)O(n log n)最坏时间复杂度O(n²)O(n log n)空间复杂度O(log n)原地交换O(n)需要临时数组稳定性不稳定稳定适合场景内存足够、追求平均速度的内部排序大数据量、链表排序、需要稳定的场景典型实现Java 基本类型排序、C 语言 qsortJava 引用类型排序、外部排序快速排序最大的优势在于原地排序常数较小大多数情况下比归并排序快归并排序最大的优势在于稳定并且最坏时间复杂度依然能保持 O(n log n)非常适合对稳定性有要求的场景。4. “重组蒙娜丽莎”核心设计与像素编码4.1 图像像素的数据模型在 Java 中BufferedImage可以通过getRGB(0, 0, width, height, null, 0, width)一次性获取整张图片的像素数组。数组中的每个元素是一个int代表一个像素的 ARGB 颜色值其中高 8 位是透明度 Alpha后面依次是 Red、Green、Blue。例如一个典型 ARGB 像素可以表示为int argb (255 24) | (128 16) | (64 8) | 32;这个值表示Alpha 透明度为 255红色分量 128绿色分量 64蓝色分量 32。恢复图像时我们需要同时知道两件事像素的 ARGB 颜色值以及这个像素在原始图片中的位置索引。如果分开存储排序时会非常麻烦更好的方案是把这两个信息合并到一个long型变量中。4.2 把“索引 像素值”打包进一个 longJava 的long类型占 64 位可以拆成两个 32 位来使用高 32 位保存原始索引。低 32 位保存 ARGB 像素值。打包代码如下long packed ((long) index 32) | (argb 0xffffffffL);这里有一个容易踩坑的细节ARGB 像素值是有符号的int例如0xFF204080在 Java 中会被当成负数。如果直接用(long) argb做或运算符号扩展会把高 32 位全部变成 1导致索引字段被污染。因此需要先执行argb 0xffffffffL把有符号 int 转成无符号 32 位值再进行合并。取出像素值时做反向操作int argb (int) (packed 0xffffffffL);在这个设计中packed数值的大小主要由高 32 位的索引决定。当只有一个索引唯一的long数组按数值从小到大排序时最终结果就是按索引排列也就是恢复原图顺序。这也正是“重组蒙娜丽莎”实验的核心原理。4.3 打乱像素Fisher-Yates 洗牌拿到打包后的long[]后需要使用洗牌算法把数组顺序打乱。Fisher-Yates 洗牌算法是常见且无偏的随机打乱算法Java 实现如下Random random new Random(42); for (int i shuffled.length - 1; i 0; i--) { int j random.nextInt(i 1); long tmp shuffled[i]; shuffled[i] shuffled[j]; shuffled[j] tmp; }固定随机种子42可以让每次实验的乱序结果一致方便对比快速排序和归并排序在完全相同输入下的表现。如果希望每次运行都不同可以改成new Random()。4.4 恢复流程总览整个“重组蒙娜丽莎”实验可以用文字流程图概括读取图片得到原始像素数组。将每个像素和它的原始索引打包成long。使用洗牌算法打乱数组生成一张噪点图。复制打乱后的数组分别交给快速排序和归并排序按索引排序。排序完成后将数组拆回像素值写回BufferedImage并保存到文件。对比两张恢复图的耗时与效果。整个过程中没有使用任何图像修复算法排序算法就是唯一的“恢复工具”。5. 完整实战用 Java 实现快速排序与归并排序恢复图像5.1 创建项目结构在本地新建目录sort-image-restore并在其中创建src/ImageSortLab.java文件。测试图片可以命名为mona.png放在项目根目录。最终目录结构如下sort-image-restore/ ├── src/ │ └── ImageSortLab.java ├── mona.png └── output/输出目录可以由程序自动创建。5.2 编写完整实验代码下面是完整的ImageSortLab.java代码。代码中包含像素打包、洗牌、快速排序、归并排序、图片写入等完整步骤可以直接复制运行。import javax.imageio.ImageIO; import java.awt.image.BufferedImage; import java.io.File; import java.io.IOException; import java.util.Random; /** * 快速排序 VS 归并排序 —— 重组蒙娜丽莎实验 * * 用法java ImageSortLab [输入图片路径] [输出目录] * 示例java ImageSortLab mona.png output */ public class ImageSortLab { public static void main(String[] args) throws IOException { String inputPath args.length 0 ? args[0] : mona.png; String outputDir args.length 1 ? args[1] : output; File inputFile new File(inputPath); if (!inputFile.exists()) { System.err.println(输入图片不存在: inputFile.getAbsolutePath()); return; } // 1. 读取图片像素 BufferedImage image ImageIO.read(inputFile); int width image.getWidth(); int height image.getHeight(); int[] pixels image.getRGB(0, 0, width, height, null, 0, width); System.out.printf(图片尺寸: %d x %d像素总数: %d%n, width, height, pixels.length); // 2. 打包像素高32位记录索引低32位记录ARGB long[] original packWithIndex(pixels); // 3. 洗牌打乱 long[] shuffled original.clone(); shuffle(shuffled, new Random(42)); saveLongArrayAsImage(shuffled, width, height, outputDir /shuffled.png); // 4. 使用快速排序恢复 long[] quickArray shuffled.clone(); long start System.currentTimeMillis(); quickSort(quickArray, 0, quickArray.length - 1); long quickCost System.currentTimeMillis() - start; saveLongArrayAsImage(quickArray, width, height, outputDir /quick_restored.png); System.out.printf(快速排序耗时: %d ms%n, quickCost); // 5. 使用归并排序恢复 long[] mergeArray shuffled.clone(); start System.currentTimeMillis(); mergeSort(mergeArray, 0, mergeArray.length - 1); long mergeCost System.currentTimeMillis() - start; saveLongArrayAsImage(mergeArray, width, height, outputDir /merge_restored.png); System.out.printf(归并排序耗时: %d ms%n, mergeCost); System.out.println(排序恢复完成图片已输出到: new File(outputDir).getAbsolutePath()); } /** * 将 ARGB 像素数组打包成 long 数组。 * 高32位保存像素原始索引低32位保存ARGB颜色值。 */ private static long[] packWithIndex(int[] pixels) { long[] data new long[pixels.length]; for (int i 0; i pixels.length; i) { data[i] ((long) i 32) | (pixels[i] 0xffffffffL); } return data; } /** * Fisher-Yates 洗牌算法打乱 long 数组。 */ private static void shuffle(long[] arr, Random random) { for (int i arr.length - 1; i 0; i--) { int j random.nextInt(i 1); swap(arr, i, j); } } private static void swap(long[] arr, int i, int j) { long tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } /** * 快速排序Lomuto 分区。 */ private static void quickSort(long[] arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } private static int partition(long[] arr, int low, int high) { long 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 mergeSort(long[] arr, int left, int right) { if (left right) { int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } } private static void merge(long[] arr, int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; long[] leftArr new long[n1]; long[] rightArr new long[n2]; for (int i 0; i n1; i) { leftArr[i] arr[left i]; } for (int j 0; j n2; j) { rightArr[j] arr[mid 1 j]; } int i 0; int j 0; int k left; while (i n1 j n2) { if (leftArr[i] rightArr[j]) { arr[k] leftArr[i]; } else { arr[k] rightArr[j]; } } while (i n1) { arr[k] leftArr[i]; } while (j n2) { arr[k] rightArr[j]; } } /** * 将 long 数组恢复成 BufferedImage 并保存为 PNG 图片。 */ private static void saveLongArrayAsImage(long[] data, int width, int height, String path) throws IOException { BufferedImage out new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB); int[] pixels new int[data.length]; for (int i 0; i data.length; i) { pixels[i] (int) (data[i] 0xffffffffL); } out.setRGB(0, 0, width, height, pixels, 0, width); File file new File(path); File parent file.getParentFile(); if (parent ! null !parent.exists()) { parent.mkdirs(); } ImageIO.write(out, png, file); } }5.3 编译与运行如果使用命令行在sort-image-restore目录下执行javac -encoding UTF-8 src/ImageSortLab.java -d out java -cp out ImageSortLab mona.png output如果使用 IntelliJ IDEA只需要把mona.png放到项目根目录然后直接运行main方法即可。程序会自动在项目根目录下创建output目录。运行成功后控制台会输出类似下面的信息图片尺寸: 480 x 640像素总数: 307200 快速排序耗时: 78 ms 归并排序耗时: 121 ms 排序恢复完成图片已输出到: /path/to/sort-image-restore/output需要说明的是具体耗时数值会因机器性能、图片分辨率、JVM 状态以及数据乱序程度而不同。不同机器上的结果不必强求一致重点是比较两种排序在同一份数据上的相对耗时。5.4 运行结果说明运行完成后output目录下会出现三张图片shuffled.png原始图片像素被随机打乱后的噪点图。quick_restored.png使用快速排序恢复后的图片。merge_restored.png使用归并排序恢复后的图片。打开quick_restored.png和merge_restored.png两者应该都能成功还原出蒙娜丽莎的图像。如果还原成功说明排序算法确实把像素按原始索引重新排好了。这个实验最有意思的地方在于如果你把打包方式从“高 32 位保存索引”改成“高 32 位保存灰度值”排序结束后图像不会恢复原样而是变成一张从暗到亮的灰度渐变图。这种扩展可以进一步帮助观察排序算法的可视化效果。6. 快速排序边界问题与易错点分析6.1 快排边界怎么记“快速排序的几种边界怎么记”是初学者最常遇到的问题。以本文使用的 Lomuto 分区为例可以用下面几条规则帮助记忆递归出口low high区间内至少有两个元素才继续递归。基准位置选择arr[high]作为基准。循环范围j从low遍历到high - 1最后一个元素留给基准。返回值分区结束时基准被交换到i 1位置所以返回i 1。递归区间左区间[low, pi - 1]右区间[pi 1, high]pi本身已经就位不能再参与递归。快速排序最典型的越界错误是递归时把右区间写成[pi, high]。这样pi位置会被反复当作未排序区间处理虽然不一定立刻报错但会导致死循环或栈溢出。6.2 归并排序的边界注意点归并排序的边界主要集中在中点和递归拆分上。mid的正确计算方式是int mid left (right - left) / 2;这种方式可以避免(left right) / 2在 left 和 right 都很大时可能出现的整数溢出问题。递归拆分时左区间为[left, mid]右区间为[mid 1, right]两边不能重叠也不能遗漏。合并阶段merge方法需要把两个有序子数组写回原数组。此时要注意三个指针的移动i指向左子数组j指向右子数组k指向原数组写入位置。循环结束后还要把剩余元素全部拷贝回去否则原数组会丢失部分数据。6.3 稳定性和空间开销对结果的影响快速排序和归并排序在“重组蒙娜丽莎”实验中都能恢复图片因为实验中的排序键是唯一的像素索引不需要考虑稳定性。但在实际业务排序中稳定性可能很重要。比如对学生先按班级排序、再按成绩排序如果第二次排序是稳定的那么同分的同学会继续保持班级顺序如果第二次排序不稳定班级顺序就可能被打乱。归并排序适合这种场景快速排序则不适合。另外归并排序每次合并都需要创建临时数组频繁的数组创建会带来 GC 压力工程中如果必须手写归并排序通常会复用同一个临时数组来减少内存分配。7. 常见问题与排查7.1 高频问题速查表下面整理了一些实验过程中容易遇到的问题以及对应的解决思路问题现象常见原因解决思路程序报ArrayIndexOutOfBoundsException快速排序递归区间写错或者分区返回值越界检查递归边界左区间到pi - 1右区间从pi 1开始恢复后的图片全是黑色或透明取出像素时没有做 0xffffffffL转换导致符号扩展使用int argb (int)(data[i] 0xffffffffL)图片打乱后恢复过程耗时很长图片分辨率太大或者快速排序遇到已经有序的数据退化到 O(n²)缩小图片尺寸或使用随机基准 / 三数取中优化快速排序归并排序恢复结果正确但内存占用较高每次merge都新建临时数组在类中复用同一个临时数组或减少测试图片像素量输出图片路径找不到程序工作目录与图片路径不一致使用绝对路径或者检查 IDE 的当前工作目录配置递归调用过深导致栈溢出快速排序最坏情况下递归深度接近 n改用非递归实现或使用随机化基准降低退化概率PTA / 在线评测平台要求严格递归结构递归二路归并排序的输出方式与平台要求不一致仔细阅读题目要求确认输出分隔符和排序方向7.2 图片恢复结果不完整的排查步骤如果排序后图片看起来只是部分恢复可以按以下顺序排查检查packWithIndex方法中的索引是否正确确认排序数组长度的确等于宽乘高。检查保存图片时是否使用了TYPE_INT_ARGB如果原图是 JPG也可以改用TYPE_INT_RGB。检查洗牌是否只打乱了数组顺序而没有丢失任何元素。可以对排序前后的数组长度做一次断言。检查排序算法是否修改了数组中的元素值。排序只应该调整long值的顺序不应该改变long本身。7.3 图像实验中的安全性提醒这个实验只涉及本地图片的读取和写入不涉及网络请求或数据库操作整体比较安全。但如果你把程序改成批量处理大量图片需要注意内存占用和磁盘空间不要无限制加载大图。生产环境中处理图片时最好明确文件来源和保存范围避免覆盖原始文件。8. 最佳实践与工程建议8.1 实际开发中优先使用标准库虽然本文的代码手动实现了快速排序和归并排序但这是为了教学和实验。实际业务开发中应优先使用语言或框架提供的排序方法JavaArrays.sort()对基本类型使用双轴快速排序对引用类型使用 TimSort一种稳定的归并排序变体。C标准库提供qsort()。C标准库提供std::sort()和std::stable_sort()。例如在 Java 中对long[]数组排序可以直接使用Arrays.sort(arr);标准库排序经过大量优化性能和安全性都远超手写实现。只有当你明确需要掌握算法原理、或者处理非常特殊的数据结构时才考虑自己实现排序。8.2 算法选型建议快速排序和归并排序的选型没有绝对标准但可以参考下面几个方向如果数据量不大且不需要稳定性快速排序通常更合适。如果需要稳定性例如多关键字排序使用归并排序。如果要排序的数据存储在链表中归并排序不需要随机访问下标实现更自然。如果内存非常紧张又不要求稳定性快速排序的原地交换特性更有优势。如果数据量远大于内存需要使用外部排序归并排序是最经典的思路。8.3 图像排序实验的工程化细节“重组蒙娜丽莎”实验虽然代码简单但有一些工程细节值得记住。首先是位运算的正确性。Java 的int是有符号的ARGB 像素值经常大于Integer.MAX_VALUE必须用 0xffffffffL转换成无符号 32 位长整型否则打包时会破坏索引字段。其次是随机种子的使用。固定随机种子可以保证实验可复现这是调试和对比算法性能的重要习惯。演示阶段使用固定种子生产环境中使用真正的随机种子。第三是日志输出。排序耗时统计建议使用System.nanoTime()做精确测量输出测试图片使用System.currentTimeMillis()即可满足大部分需求。8.4 代码可维护性建议本文为了演示方便把代码都写在一个类里。实际项目中更好的做法是按职责拆分一个类负责图像读写。一个类负责像素编码与解码。一个类或接口负责排序策略方便在快速排序和归并排序之间切换。例如可以定义一个SortStrategy接口public interface SortStrategy { void sort(long[] arr); }然后分别实现QuickSortStrategy和MergeSortStrategy。这样后续扩展堆排序、希尔排序都非常方便测试代码也不需要大量改动。8.5 跨语言实现要点如果你是学习 C 语言或 C 的同学可以把本文的 Java 思路直接迁移过去。C 语言中快速排序可以使用标准库qsort需要自定义比较函数#include stdlib.h int compare(const void *a, const void *b) { long x *(const long *)a; long y *(const long *)b; return (x y) - (x y); } qsort(arr, n, sizeof(long long), compare);C 中归并排序可以使用std::stable_sort#include algorithm std::stable_sort(arr, arr n);底层原理与本文讲解的算法一致但不同语言对变量类型、内存管理的处理方式有差异读者需要根据实际语言环境调整。9. 总结与学习路线通过“重组蒙娜丽莎”这个实验我们完成了三件事第一理解了快速排序和归并排序的核心原理。快速排序依赖基准值分区归并排序依赖拆分后的有序合并两者的时间复杂度和适用场景有明显差异。第二掌握了完整的图像像素编码方式。通过把“索引 ARGB 像素值”打包进一个long可以用排序算法直接恢复打乱的图片整个过程直观且有趣。第三梳理了常见的边界问题和工程建议。快速排序的递归边界、归并排序的合并边界、位运算符号扩展等细节都是实际编码中容易出错的点。如果还想继续深入可以尝试以下方向在本文基础上增加“按灰度值排序”模式观察排序过程中图像如何从噪点逐渐变成灰度渐变图。把排序过程中间帧每隔一定次数保存成 PNG再用工具合成为 GIF直观对比两种排序算法的收敛过程。使用非递归方式重写快速排序和归并排序理解系统栈与手动栈的区别。学习 Java 中Arrays.sort的底层实现了解双轴快速排序和 TimSort 的优化思路。动手实验比单纯看文章印象更深刻。建议你找一张自己喜欢的高清图片替换掉mona.png在本地跑一遍完整流程然后对比快速排序和归并排序的耗时差异与恢复效果。
快速排序 vs 归并排序：用Java图像重组实验看懂排序算法
把一张蒙娜丽莎的像素全部随机打乱画面就会瞬间变成满是噪点的“雪花屏”。如果要求你只通过排序算法把它恢复原样你会选用快速排序还是归并排序这个实验看似花哨实际上把排序算法的运行过程变成了一张能“看见”的图哪种算法在逐步恢复图像、哪种算法在中途更接近原图、哪种算法更快都会一目了然。本文将围绕“快速排序 VS 归并排序”这一经典对比展开用 Java 编写一套完整的图像重组实验程序把一张图片打乱后分别用快速排序和归并排序恢复。文章不仅会讲解两种排序算法的核心原理、递归边界和复杂度还会给出可复制的完整代码、运行结果、常见排错思路以及工程选型建议。1. 背景与核心概念1.1 排序算法为什么值得重新学一遍排序算法是计算机科学中最基础、也最常被问到的算法问题。无论是数据库的索引构建、搜索引擎的结果排序还是推荐系统的候选集重排底层都会用到不同种类的排序算法。很多人觉得排序算法在业务开发中很少手写因为 Java、C、Python 都已经提供了成熟的排序库但恰恰因为“有库可用”很多人反而忽略了一个重要事实理解排序的过程是理解递归、分治、时间复杂度和内存开销的最好入口。以快速排序和归并排序为例这是两种最有代表性的分治排序算法。快速排序的平均时间复杂度低、常数小是很多标准库的首选归并排序则稳定、适合外部排序和海量数据。两者常常被放在一起比较但纯粹比较数字很难讲清楚差异。如果能把排序过程直观展示出来理解成本就会降低很多。“重组蒙娜丽莎”实验就是这样一种可视化思路。1.2 快速排序与归并排序的定位快速排序Quick Sort的核心思想是分治每次从待排序区间中选一个基准值pivot把小于基准值的元素放到左边把大于基准值的元素放到右边然后递归处理左右两个子区间。它不需要额外的数组来存储中间结果属于原地排序算法但它的分区过程会破坏元素之间的相对顺序因此是不稳定排序。归并排序Merge Sort的核心思想同样是分治但处理方式完全不同它先把数组持续拆分成两半直到每个子区间只有一个元素然后把相邻的有序区间两两合并成一个更大的有序区间。这个合并过程需要借助额外的临时数组因此空间复杂度更高但合并过程不会打乱相同元素的相对顺序所以归并排序是稳定排序也常被称为“递归二路归并排序”。两种算法一个追求“平均快”一个追求“稳定且可靠”。算法面试中这两道题几乎是必考题目工程实践中很多排序库也会根据数据特征在快速排序和归并排序之间做出取舍。1.3 什么是“重组蒙娜丽莎”“重组蒙娜丽莎”并不是图像修复而是一个排序可视化实验。一张图片由很多像素组成。我们可以把每个像素看成独立的数据项并且给每个像素记录一个原始位置编号。随后把所有像素随机打乱图片便无法辨认。这时候只要把像素按照“原始位置编号”重新排序图片就能恢复原样。关键点在于恢复图像本身不依靠任何图像算法只依靠排序算法。快速排序和归并排序拿到的是同一组乱序像素谁能更快、更稳定地把它们按原始编号排列好谁就相当于更好地完成了“重组”这张画的任务。这个实验的优势是直观普通排序练习面对的是一串数字排序完成后只能用肉眼检查是否升序而图像恢复任务中排序结果可以直接看到。图像从噪点逐渐恢复出轮廓的过程其实就是排序算法内部工作过程的真实反馈。2. 环境准备与版本说明2.1 JDK 与开发工具本文的 Java 示例基于 JDK 8 及以上版本即可运行不依赖任何第三方库。图像读取和写入使用 JDK 自带的javax.imageio.ImageIO像素操作使用java.awt.image.BufferedImage这两个类都包含在标准 JDK 中不需要额外引入 Maven 依赖。开发工具可以根据个人习惯选择IntelliJ IDEAEclipseVS Code Java 插件纯命令行 文本编辑器由于项目不依赖构建工具也可以直接在命令行中使用javac编译、java运行。版本需要根据你的项目实际情况调整本文示例以常见 JDK 8/11/17 环境为例重点演示算法与图像处理的完整流程。2.2 示例项目结构建议创建一个目录来存放实验代码和图片结构如下sort-image-restore/ ├── src/ │ └── ImageSortLab.java ├── mona.png └── output/其中src/ImageSortLab.java是完整实验程序。mona.png是输入图片可以替换成任意 JPG/PNG 图片。output/是程序运行后生成结果的目录包括打乱后的噪点图和恢复后的图片。这里为了便于演示图片直接放在项目根目录。如果使用 IDEA 这类 IDE注意图片路径要以运行时的当前工作目录为基准建议直接使用绝对路径或项目根目录下的相对路径。2.3 测试图片准备理论上任何图片都可以做这个实验但为了让视觉效果更明显需要注意几点图片尺寸不宜过大建议控制在 300 x 300 到 800 x 600 之间。像素太多会明显增加排序耗时不利于快速演示。内容最好有明显轮廓例如人像、动物、风景图。黑白或彩色均可。如果使用 JPG 图片程序输出时会统一保存为 PNG因为排序后的像素包含 ARGB 颜色信息PNG 能更好保留像素数据。本文使用“蒙娜丽莎”作为实验对象因为这幅画属于公有领域且轮廓分明非常适合观察图像恢复过程。你也可以使用任意一张本地图片测试效果只取决于图片内容是否容易辨认。3. 快速排序与归并排序核心原理解读3.1 快速排序选基准分区再递归快速排序的直观过程可以这样理解假设一队人需要按身高从左到右排列。先让队尾的人站出来当基准然后其他人依次和基准比较小于等于基准的人站到左边大于基准的人站到右边。一轮结束后基准左边的人都不高于基准右边的人都高于基准。基准的位置已经正确接下来只需要对左右两队人各自继续执行同样的操作。在代码层面快速排序通常分为两步分区partition和递归quickSort。下面是一个基于 Lomuto 分区方式的 Java 快速排序实现// 快速排序入口 public static void quickSort(int[] arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } // Lomuto 分区以最后一个元素为基准 public 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; int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } } int tmp arr[i 1]; arr[i 1] arr[high]; arr[high] tmp; return i 1; }这段代码中partition返回的pi是基准值最终所在的位置。基准值左边都小于等于它右边都大于它。递归处理左右两侧后整个数组就有序了。快速排序的平均时间复杂度为 O(n log n)最坏情况下会退化到 O(n²)例如数组已经有序且每次都选择最大或最小值作为基准时。通过随机选择基准或“三数取中”法可以有效降低最坏情况出现的概率。3.2 归并排序先拆分后有序合并归并排序的思路和快速排序正好相反。快速排序是先粗略分区然后再递归细化归并排序则是先把数组不断拆到最小再通过合并逐步构建有序序列。直观看归并排序像一场淘汰赛先两两组队排序再四四组合并最终合成一个完整有序队伍。下面是 Java 中“递归二路归并排序”的标准实现// 归并排序入口 public static void mergeSort(int[] arr, int left, int right) { if (left right) { int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } } // 合并两个有序区间 [left, mid] 和 [mid1, right] public static void merge(int[] arr, int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; int[] L new int[n1]; int[] R new int[n2]; for (int i 0; i n1; i) { L[i] arr[left i]; } for (int j 0; j n2; j) { R[j] arr[mid 1 j]; } int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; i; } else { arr[k] R[j]; j; } k; } while (i n1) { arr[k] L[i]; i; k; } while (j n2) { arr[k] R[j]; j; k; } }merge方法是归并排序的核心。它假设左右两个区间已经各自有序然后使用双指针从左到右依次比较把较小元素写入原数组。因为比较时使用了相同元素的相对顺序不会改变所以归并排序是一个稳定排序。归并排序的时间复杂度稳定为 O(n log n)但每次merge都需要新建临时数组空间复杂度为 O(n)。3.3 两种排序算法的复杂度与特性对比很多初学者容易混淆快速排序和归并排序的适用场景。下面通过一张表来对比它们的核心差异对比维度快速排序归并排序基本思想选基准分区递归处理左右区间拆分子数组两两有序合并平均时间复杂度O(n log n)O(n log n)最坏时间复杂度O(n²)O(n log n)空间复杂度O(log n)原地交换O(n)需要临时数组稳定性不稳定稳定适合场景内存足够、追求平均速度的内部排序大数据量、链表排序、需要稳定的场景典型实现Java 基本类型排序、C 语言 qsortJava 引用类型排序、外部排序快速排序最大的优势在于原地排序常数较小大多数情况下比归并排序快归并排序最大的优势在于稳定并且最坏时间复杂度依然能保持 O(n log n)非常适合对稳定性有要求的场景。4. “重组蒙娜丽莎”核心设计与像素编码4.1 图像像素的数据模型在 Java 中BufferedImage可以通过getRGB(0, 0, width, height, null, 0, width)一次性获取整张图片的像素数组。数组中的每个元素是一个int代表一个像素的 ARGB 颜色值其中高 8 位是透明度 Alpha后面依次是 Red、Green、Blue。例如一个典型 ARGB 像素可以表示为int argb (255 24) | (128 16) | (64 8) | 32;这个值表示Alpha 透明度为 255红色分量 128绿色分量 64蓝色分量 32。恢复图像时我们需要同时知道两件事像素的 ARGB 颜色值以及这个像素在原始图片中的位置索引。如果分开存储排序时会非常麻烦更好的方案是把这两个信息合并到一个long型变量中。4.2 把“索引 像素值”打包进一个 longJava 的long类型占 64 位可以拆成两个 32 位来使用高 32 位保存原始索引。低 32 位保存 ARGB 像素值。打包代码如下long packed ((long) index 32) | (argb 0xffffffffL);这里有一个容易踩坑的细节ARGB 像素值是有符号的int例如0xFF204080在 Java 中会被当成负数。如果直接用(long) argb做或运算符号扩展会把高 32 位全部变成 1导致索引字段被污染。因此需要先执行argb 0xffffffffL把有符号 int 转成无符号 32 位值再进行合并。取出像素值时做反向操作int argb (int) (packed 0xffffffffL);在这个设计中packed数值的大小主要由高 32 位的索引决定。当只有一个索引唯一的long数组按数值从小到大排序时最终结果就是按索引排列也就是恢复原图顺序。这也正是“重组蒙娜丽莎”实验的核心原理。4.3 打乱像素Fisher-Yates 洗牌拿到打包后的long[]后需要使用洗牌算法把数组顺序打乱。Fisher-Yates 洗牌算法是常见且无偏的随机打乱算法Java 实现如下Random random new Random(42); for (int i shuffled.length - 1; i 0; i--) { int j random.nextInt(i 1); long tmp shuffled[i]; shuffled[i] shuffled[j]; shuffled[j] tmp; }固定随机种子42可以让每次实验的乱序结果一致方便对比快速排序和归并排序在完全相同输入下的表现。如果希望每次运行都不同可以改成new Random()。4.4 恢复流程总览整个“重组蒙娜丽莎”实验可以用文字流程图概括读取图片得到原始像素数组。将每个像素和它的原始索引打包成long。使用洗牌算法打乱数组生成一张噪点图。复制打乱后的数组分别交给快速排序和归并排序按索引排序。排序完成后将数组拆回像素值写回BufferedImage并保存到文件。对比两张恢复图的耗时与效果。整个过程中没有使用任何图像修复算法排序算法就是唯一的“恢复工具”。5. 完整实战用 Java 实现快速排序与归并排序恢复图像5.1 创建项目结构在本地新建目录sort-image-restore并在其中创建src/ImageSortLab.java文件。测试图片可以命名为mona.png放在项目根目录。最终目录结构如下sort-image-restore/ ├── src/ │ └── ImageSortLab.java ├── mona.png └── output/输出目录可以由程序自动创建。5.2 编写完整实验代码下面是完整的ImageSortLab.java代码。代码中包含像素打包、洗牌、快速排序、归并排序、图片写入等完整步骤可以直接复制运行。import javax.imageio.ImageIO; import java.awt.image.BufferedImage; import java.io.File; import java.io.IOException; import java.util.Random; /** * 快速排序 VS 归并排序 —— 重组蒙娜丽莎实验 * * 用法java ImageSortLab [输入图片路径] [输出目录] * 示例java ImageSortLab mona.png output */ public class ImageSortLab { public static void main(String[] args) throws IOException { String inputPath args.length 0 ? args[0] : mona.png; String outputDir args.length 1 ? args[1] : output; File inputFile new File(inputPath); if (!inputFile.exists()) { System.err.println(输入图片不存在: inputFile.getAbsolutePath()); return; } // 1. 读取图片像素 BufferedImage image ImageIO.read(inputFile); int width image.getWidth(); int height image.getHeight(); int[] pixels image.getRGB(0, 0, width, height, null, 0, width); System.out.printf(图片尺寸: %d x %d像素总数: %d%n, width, height, pixels.length); // 2. 打包像素高32位记录索引低32位记录ARGB long[] original packWithIndex(pixels); // 3. 洗牌打乱 long[] shuffled original.clone(); shuffle(shuffled, new Random(42)); saveLongArrayAsImage(shuffled, width, height, outputDir /shuffled.png); // 4. 使用快速排序恢复 long[] quickArray shuffled.clone(); long start System.currentTimeMillis(); quickSort(quickArray, 0, quickArray.length - 1); long quickCost System.currentTimeMillis() - start; saveLongArrayAsImage(quickArray, width, height, outputDir /quick_restored.png); System.out.printf(快速排序耗时: %d ms%n, quickCost); // 5. 使用归并排序恢复 long[] mergeArray shuffled.clone(); start System.currentTimeMillis(); mergeSort(mergeArray, 0, mergeArray.length - 1); long mergeCost System.currentTimeMillis() - start; saveLongArrayAsImage(mergeArray, width, height, outputDir /merge_restored.png); System.out.printf(归并排序耗时: %d ms%n, mergeCost); System.out.println(排序恢复完成图片已输出到: new File(outputDir).getAbsolutePath()); } /** * 将 ARGB 像素数组打包成 long 数组。 * 高32位保存像素原始索引低32位保存ARGB颜色值。 */ private static long[] packWithIndex(int[] pixels) { long[] data new long[pixels.length]; for (int i 0; i pixels.length; i) { data[i] ((long) i 32) | (pixels[i] 0xffffffffL); } return data; } /** * Fisher-Yates 洗牌算法打乱 long 数组。 */ private static void shuffle(long[] arr, Random random) { for (int i arr.length - 1; i 0; i--) { int j random.nextInt(i 1); swap(arr, i, j); } } private static void swap(long[] arr, int i, int j) { long tmp arr[i]; arr[i] arr[j]; arr[j] tmp; } /** * 快速排序Lomuto 分区。 */ private static void quickSort(long[] arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } private static int partition(long[] arr, int low, int high) { long 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 mergeSort(long[] arr, int left, int right) { if (left right) { int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } } private static void merge(long[] arr, int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; long[] leftArr new long[n1]; long[] rightArr new long[n2]; for (int i 0; i n1; i) { leftArr[i] arr[left i]; } for (int j 0; j n2; j) { rightArr[j] arr[mid 1 j]; } int i 0; int j 0; int k left; while (i n1 j n2) { if (leftArr[i] rightArr[j]) { arr[k] leftArr[i]; } else { arr[k] rightArr[j]; } } while (i n1) { arr[k] leftArr[i]; } while (j n2) { arr[k] rightArr[j]; } } /** * 将 long 数组恢复成 BufferedImage 并保存为 PNG 图片。 */ private static void saveLongArrayAsImage(long[] data, int width, int height, String path) throws IOException { BufferedImage out new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB); int[] pixels new int[data.length]; for (int i 0; i data.length; i) { pixels[i] (int) (data[i] 0xffffffffL); } out.setRGB(0, 0, width, height, pixels, 0, width); File file new File(path); File parent file.getParentFile(); if (parent ! null !parent.exists()) { parent.mkdirs(); } ImageIO.write(out, png, file); } }5.3 编译与运行如果使用命令行在sort-image-restore目录下执行javac -encoding UTF-8 src/ImageSortLab.java -d out java -cp out ImageSortLab mona.png output如果使用 IntelliJ IDEA只需要把mona.png放到项目根目录然后直接运行main方法即可。程序会自动在项目根目录下创建output目录。运行成功后控制台会输出类似下面的信息图片尺寸: 480 x 640像素总数: 307200 快速排序耗时: 78 ms 归并排序耗时: 121 ms 排序恢复完成图片已输出到: /path/to/sort-image-restore/output需要说明的是具体耗时数值会因机器性能、图片分辨率、JVM 状态以及数据乱序程度而不同。不同机器上的结果不必强求一致重点是比较两种排序在同一份数据上的相对耗时。5.4 运行结果说明运行完成后output目录下会出现三张图片shuffled.png原始图片像素被随机打乱后的噪点图。quick_restored.png使用快速排序恢复后的图片。merge_restored.png使用归并排序恢复后的图片。打开quick_restored.png和merge_restored.png两者应该都能成功还原出蒙娜丽莎的图像。如果还原成功说明排序算法确实把像素按原始索引重新排好了。这个实验最有意思的地方在于如果你把打包方式从“高 32 位保存索引”改成“高 32 位保存灰度值”排序结束后图像不会恢复原样而是变成一张从暗到亮的灰度渐变图。这种扩展可以进一步帮助观察排序算法的可视化效果。6. 快速排序边界问题与易错点分析6.1 快排边界怎么记“快速排序的几种边界怎么记”是初学者最常遇到的问题。以本文使用的 Lomuto 分区为例可以用下面几条规则帮助记忆递归出口low high区间内至少有两个元素才继续递归。基准位置选择arr[high]作为基准。循环范围j从low遍历到high - 1最后一个元素留给基准。返回值分区结束时基准被交换到i 1位置所以返回i 1。递归区间左区间[low, pi - 1]右区间[pi 1, high]pi本身已经就位不能再参与递归。快速排序最典型的越界错误是递归时把右区间写成[pi, high]。这样pi位置会被反复当作未排序区间处理虽然不一定立刻报错但会导致死循环或栈溢出。6.2 归并排序的边界注意点归并排序的边界主要集中在中点和递归拆分上。mid的正确计算方式是int mid left (right - left) / 2;这种方式可以避免(left right) / 2在 left 和 right 都很大时可能出现的整数溢出问题。递归拆分时左区间为[left, mid]右区间为[mid 1, right]两边不能重叠也不能遗漏。合并阶段merge方法需要把两个有序子数组写回原数组。此时要注意三个指针的移动i指向左子数组j指向右子数组k指向原数组写入位置。循环结束后还要把剩余元素全部拷贝回去否则原数组会丢失部分数据。6.3 稳定性和空间开销对结果的影响快速排序和归并排序在“重组蒙娜丽莎”实验中都能恢复图片因为实验中的排序键是唯一的像素索引不需要考虑稳定性。但在实际业务排序中稳定性可能很重要。比如对学生先按班级排序、再按成绩排序如果第二次排序是稳定的那么同分的同学会继续保持班级顺序如果第二次排序不稳定班级顺序就可能被打乱。归并排序适合这种场景快速排序则不适合。另外归并排序每次合并都需要创建临时数组频繁的数组创建会带来 GC 压力工程中如果必须手写归并排序通常会复用同一个临时数组来减少内存分配。7. 常见问题与排查7.1 高频问题速查表下面整理了一些实验过程中容易遇到的问题以及对应的解决思路问题现象常见原因解决思路程序报ArrayIndexOutOfBoundsException快速排序递归区间写错或者分区返回值越界检查递归边界左区间到pi - 1右区间从pi 1开始恢复后的图片全是黑色或透明取出像素时没有做 0xffffffffL转换导致符号扩展使用int argb (int)(data[i] 0xffffffffL)图片打乱后恢复过程耗时很长图片分辨率太大或者快速排序遇到已经有序的数据退化到 O(n²)缩小图片尺寸或使用随机基准 / 三数取中优化快速排序归并排序恢复结果正确但内存占用较高每次merge都新建临时数组在类中复用同一个临时数组或减少测试图片像素量输出图片路径找不到程序工作目录与图片路径不一致使用绝对路径或者检查 IDE 的当前工作目录配置递归调用过深导致栈溢出快速排序最坏情况下递归深度接近 n改用非递归实现或使用随机化基准降低退化概率PTA / 在线评测平台要求严格递归结构递归二路归并排序的输出方式与平台要求不一致仔细阅读题目要求确认输出分隔符和排序方向7.2 图片恢复结果不完整的排查步骤如果排序后图片看起来只是部分恢复可以按以下顺序排查检查packWithIndex方法中的索引是否正确确认排序数组长度的确等于宽乘高。检查保存图片时是否使用了TYPE_INT_ARGB如果原图是 JPG也可以改用TYPE_INT_RGB。检查洗牌是否只打乱了数组顺序而没有丢失任何元素。可以对排序前后的数组长度做一次断言。检查排序算法是否修改了数组中的元素值。排序只应该调整long值的顺序不应该改变long本身。7.3 图像实验中的安全性提醒这个实验只涉及本地图片的读取和写入不涉及网络请求或数据库操作整体比较安全。但如果你把程序改成批量处理大量图片需要注意内存占用和磁盘空间不要无限制加载大图。生产环境中处理图片时最好明确文件来源和保存范围避免覆盖原始文件。8. 最佳实践与工程建议8.1 实际开发中优先使用标准库虽然本文的代码手动实现了快速排序和归并排序但这是为了教学和实验。实际业务开发中应优先使用语言或框架提供的排序方法JavaArrays.sort()对基本类型使用双轴快速排序对引用类型使用 TimSort一种稳定的归并排序变体。C标准库提供qsort()。C标准库提供std::sort()和std::stable_sort()。例如在 Java 中对long[]数组排序可以直接使用Arrays.sort(arr);标准库排序经过大量优化性能和安全性都远超手写实现。只有当你明确需要掌握算法原理、或者处理非常特殊的数据结构时才考虑自己实现排序。8.2 算法选型建议快速排序和归并排序的选型没有绝对标准但可以参考下面几个方向如果数据量不大且不需要稳定性快速排序通常更合适。如果需要稳定性例如多关键字排序使用归并排序。如果要排序的数据存储在链表中归并排序不需要随机访问下标实现更自然。如果内存非常紧张又不要求稳定性快速排序的原地交换特性更有优势。如果数据量远大于内存需要使用外部排序归并排序是最经典的思路。8.3 图像排序实验的工程化细节“重组蒙娜丽莎”实验虽然代码简单但有一些工程细节值得记住。首先是位运算的正确性。Java 的int是有符号的ARGB 像素值经常大于Integer.MAX_VALUE必须用 0xffffffffL转换成无符号 32 位长整型否则打包时会破坏索引字段。其次是随机种子的使用。固定随机种子可以保证实验可复现这是调试和对比算法性能的重要习惯。演示阶段使用固定种子生产环境中使用真正的随机种子。第三是日志输出。排序耗时统计建议使用System.nanoTime()做精确测量输出测试图片使用System.currentTimeMillis()即可满足大部分需求。8.4 代码可维护性建议本文为了演示方便把代码都写在一个类里。实际项目中更好的做法是按职责拆分一个类负责图像读写。一个类负责像素编码与解码。一个类或接口负责排序策略方便在快速排序和归并排序之间切换。例如可以定义一个SortStrategy接口public interface SortStrategy { void sort(long[] arr); }然后分别实现QuickSortStrategy和MergeSortStrategy。这样后续扩展堆排序、希尔排序都非常方便测试代码也不需要大量改动。8.5 跨语言实现要点如果你是学习 C 语言或 C 的同学可以把本文的 Java 思路直接迁移过去。C 语言中快速排序可以使用标准库qsort需要自定义比较函数#include stdlib.h int compare(const void *a, const void *b) { long x *(const long *)a; long y *(const long *)b; return (x y) - (x y); } qsort(arr, n, sizeof(long long), compare);C 中归并排序可以使用std::stable_sort#include algorithm std::stable_sort(arr, arr n);底层原理与本文讲解的算法一致但不同语言对变量类型、内存管理的处理方式有差异读者需要根据实际语言环境调整。9. 总结与学习路线通过“重组蒙娜丽莎”这个实验我们完成了三件事第一理解了快速排序和归并排序的核心原理。快速排序依赖基准值分区归并排序依赖拆分后的有序合并两者的时间复杂度和适用场景有明显差异。第二掌握了完整的图像像素编码方式。通过把“索引 ARGB 像素值”打包进一个long可以用排序算法直接恢复打乱的图片整个过程直观且有趣。第三梳理了常见的边界问题和工程建议。快速排序的递归边界、归并排序的合并边界、位运算符号扩展等细节都是实际编码中容易出错的点。如果还想继续深入可以尝试以下方向在本文基础上增加“按灰度值排序”模式观察排序过程中图像如何从噪点逐渐变成灰度渐变图。把排序过程中间帧每隔一定次数保存成 PNG再用工具合成为 GIF直观对比两种排序算法的收敛过程。使用非递归方式重写快速排序和归并排序理解系统栈与手动栈的区别。学习 Java 中Arrays.sort的底层实现了解双轴快速排序和 TimSort 的优化思路。动手实验比单纯看文章印象更深刻。建议你找一张自己喜欢的高清图片替换掉mona.png在本地跑一遍完整流程然后对比快速排序和归并排序的耗时差异与恢复效果。
