ARTICLE DETAIL

资讯详情

深耕郑州网站建设与运营推广的一线实战洞察。

快速排序与归并排序:分治策略、复杂度与边界问题详解

快速排序与归并排序:分治策略、复杂度与边界问题详解 在平时的算法学习与面试准备中排序算法几乎是绕不开的一类基础问题。而在所有排序算法里快速排序与归并排序又是被问得最多的两个“分治代表”。很多初学者能背出它们的时间复杂度但真正到了手写代码、分析边界、对比选型的时候又容易卡住。本文结合“重组蒙娜丽莎”这个有趣的场景把快速排序和归并排序的原理、实现、复杂度、边界问题一次讲透帮助你把这两个算法真正装进脑子里。1. 为什么要把两个排序算法放在一起对比1.1 两者在算法家族中的位置在数据结构与算法的知识体系中排序算法可以分为几大类插入排序、选择排序、交换排序、归并排序、基数排序等。其中快速排序属于交换排序归并排序属于归并类排序。虽然它们的分类不同但两者的共同点非常明显都采用了“分治”思想都把一个大问题拆成若干小问题分别解决再合并结果。正因为它们都基于分治策略很多初学者会把两者搞混甚至以为它们是同一种算法的不同写法。实际上快速排序和归并排序在“怎么分”、“怎么合”、“是否需要额外空间”、“是否稳定”这些关键维度上有本质区别。掌握这些区别是真正理解这两个算法的分水岭。1.2 “重组蒙娜丽莎”是什么意思为了更直观地理解排序过程这里引入一个生活化的比喻想象你手里有一幅蒙娜丽莎画像它被分成了若干小块每块标有一个灰度值或像素权重。这些小块被打乱后你需要按像素值从小到大排列它们重新拼出完整图像。这个场景可以完美模拟排序算法的本质输入一个无序的像素序列经过排序后输出一个有序序列。归并排序像是一个“拆开再拼回去”的过程它先把图像区域不断二分分成单个小块后再逐层合并成有序的整体快速排序则像是“选一个基准值把小块按大小分到左右两侧”然后对两侧继续重复这个过程直到所有块都有序。两种思路都能完成重组但花费的时间和额外空间不同这正是本文要重点分析的内容。2. 算法原理回顾2.1 归并排序先分后合归并排序的核心理念是“分而治之合而有序”。它把待排序数组从中间一分为二对左右两个子数组分别递归地执行归并排序最后将两个有序子数组合并成一个有序数组。递归的终止条件是子数组长度为 1 或 0因为单个元素天然有序。合并过程是归并排序最关键的一步同时扫描两个有序子数组每次取较小的元素放入辅助数组直到其中一个子数组取完再把剩余元素全部拷贝过去。用“重组蒙娜丽莎”来理解就是先把整幅画分成上下两半再把每半分成上下两半直到每一块只有一个像素然后从最小的块开始两两按灰度排序合并逐渐拼出更大的有序区域最终得到整幅有序的图像。归并排序的“合”是重头戏它的稳定性也正来源于合并时相等的元素保持原有顺序。2.2 快速排序选定基准分区快速排序同样基于分治思想但它与归并排序的“分”不同。快速排序首先从数组中挑一个“基准值”然后通过一次扫描把数组分成两个部分左边部分的所有元素都不大于基准值右边部分的所有元素都不小于基准值。基准值最终会落在它排序后的正确位置上。接下来对基准值左右两侧的子数组分别递归执行同样的分区操作。递归终止条件是子数组长度小于等于 1此时整个数组已经有序。快速排序的“分”是核心动作它不依赖额外的辅助数组来完成整轮排序而是通过交换元素在原数组上就地操作。这也是它空间效率高于归并排序的根本原因。对应到蒙娜丽莎的场景快速排序更像是一位经验丰富的拼图师随手拿起一块作为基准将比它更暗的块放左边、比它更亮的块放右边然后对左右两边继续重复这个策略直到所有像素块都在正确位置上。2.3 两种分治策略最本质的区别两个算法的分治策略有非常直观的差异对比维度归并排序快速排序分的策略固定从中间切分与元素大小无关根据基准值划分分区结果与数据分布有关合并过程必须有显式的 merge 操作需要辅助数组无需显式合并分区后天然有序递归的触发点先递归分割再回溯合并先分区确定基准位置再递归两侧关键操作merge合并partition分区空间开销O(n) 辅助空间O(log n) 递归栈空间平均理解了这个区别就能明白为什么归并排序稳定、而快速排序通常不稳定为什么归并排序的最坏时间复杂度是严格的 O(n log n)而快速排序的理论最坏情况会退化到 O(n²)。3. 完整代码实现理论部分理解后下面进入最关键的实践环节。这里分别用 Java 和 C 实现归并排序与快速排序这两个语言也是面试和工程中使用频率最高的。3.1 Java 实现归并排序// 文件路径MergeSort.java public class MergeSort { // 对外暴露的排序入口 public static void mergeSort(int[] arr) { if (arr null || arr.length 2) { return; } // 借助辅助数组避免在递归中频繁创建新数组 int[] temp new int[arr.length]; sort(arr, 0, arr.length - 1, temp); } // 递归分割 private static void sort(int[] arr, int left, int right, int[] temp) { if (left right) { return; } int mid left (right - left) / 2; // 防止整数溢出 sort(arr, left, mid, temp); // 对左半部分排序 sort(arr, mid 1, right, temp); // 对右半部分排序 merge(arr, left, mid, right, temp); // 合并两个有序部分 } // 合并两个有序区间[left, mid] 和 [mid1, right] private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i left; // 左半部分指针 int j mid 1; // 右半部分指针 int t 0; // 辅助数组指针 // 两边都没取完时取较小者放入辅助数组 while (i mid j right) { if (arr[i] arr[j]) { temp[t] arr[i]; } else { temp[t] arr[j]; } } // 左边剩余元素拷贝 while (i mid) { temp[t] arr[i]; } // 右边剩余元素拷贝 while (j right) { temp[t] arr[j]; } // 将辅助数组中的有序结果复制回原数组 t 0; while (left right) { arr[left] temp[t]; } } // 测试 public static void main(String[] args) { int[] arr {8, 4, 5, 7, 1, 3, 6, 2}; mergeSort(arr); for (int num : arr) { System.out.print(num ); } } }代码中有几个细节需要特别说明。mid left (right - left) / 2这种写法可以有效防止left right在极端场景下整数溢出。merge方法中使用了辅助数组temp这是归并排序需要 O(n) 额外空间的原因。合并时使用而不是保证了值相等时左侧元素先被写入从而维持算法的稳定性。运行结果为1 2 3 4 5 6 7 83.2 Java 实现快速排序// 文件路径QuickSort.java public class QuickSort { // 对外暴露的排序入口 public static void quickSort(int[] arr) { if (arr null || arr.length 2) { return; } sort(arr, 0, arr.length - 1); } private static void sort(int[] arr, int left, int right) { if (left right) { return; } int pivotIndex partition(arr, left, right); sort(arr, left, pivotIndex - 1); // 左子数组排序 sort(arr, pivotIndex 1, right); // 右子数组排序 } // 分区操作将数组分为 pivot 和 pivot 两部分 private static int partition(int[] arr, int left, int right) { // 选最右边的元素作为基准值 int pivot arr[right]; int i left; // i 指向小于等于基准值区域的右边界 for (int j left; j right; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } // 将基准值放到正确位置 swap(arr, i, right); return i; } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } // 测试 public static void main(String[] args) { int[] arr {8, 4, 5, 7, 1, 3, 6, 2}; quickSort(arr); for (int num : arr) { System.out.print(num ); } } }上面的partition方法使用的是“单向扫描法”逻辑比较直观j指针负责扫描i指针维护“小于等于基准值”的区域边界。每发现一个不大于基准值的元素就把它与i位置的元素交换然后i后移一位。扫描结束后i位置就是基准值应该待的位置因为i左侧所有元素都不大于基准值。这种写法非常适合初学阶段理解快速排序的分区过程。后面在工程优化中还可以使用“双指针双向扫描法”、随机基准值、三数取中等方式来优化性能。3.3 C 实现两个排序C 实现与 Java 逻辑完全一致需要注意的地方是数组传递和引用方式。// 文件路径merge_sort.cpp #include iostream #include vector using namespace std; // 归并排序 void merge(vectorint arr, int left, int mid, int right) { vectorint temp(right - left 1); int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (int t 0; t temp.size(); t) { arr[left t] temp[t]; } } void mergeSort(vectorint 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); } int main() { vectorint arr {8, 4, 5, 7, 1, 3, 6, 2}; mergeSort(arr, 0, arr.size() - 1); for (int num : arr) { cout num ; } return 0; }// 文件路径quick_sort.cpp #include iostream #include vector using namespace std; void swap(int a, int b) { int temp a; a b; b temp; } int partition(vectorint arr, int left, int right) { int pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { swap(arr[i], arr[j]); i; } } swap(arr[i], arr[right]); return i; } void quickSort(vectorint arr, int left, int right) { if (left right) return; int pivotIndex partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } int main() { vectorint arr {8, 4, 5, 7, 1, 3, 6, 2}; quickSort(arr, 0, arr.size() - 1); for (int num : arr) { cout num ; } return 0; }这里使用vectorint传引用确保在函数内部修改的是原始数组。注意 C 的vector相比原生数组更安全也是现代 C 推荐的做法。4. 复杂度分析与稳定性4.1 时间复杂度对比快速排序和归并排序在时间复杂度上的表现是面试中的高频考点。排序算法最好情况平均情况最坏情况快速排序O(n log n)O(n log n)O(n²)归并排序O(n log n)O(n log n)O(n log n)归并排序的时间复杂度是严格的 O(n log n)因为它每次都从中间切分递归深度一定是 log n 层每层合并操作的代价是 O(n)。这意味着无论数据初始状态如何归并排序的表现都稳定在一个水平上。快速排序的时间复杂度取决于分区是否均衡。当基准值恰好是中位数时每次分区将数组从正中间分开递归深度是 log n总代价为 O(n log n)当基准值总是最小值或最大值时比如对一个已经有序的数组每次分区仅能将数组减少一个元素递归深度退化为 n总复杂度退化为 O(n²)。这也是快速排序最需要防范的场景。4.2 空间复杂度对比空间复杂度是两者差异最大的地方之一。归并排序需要额外的辅助数组来存储合并过程中的临时结果空间复杂度为 O(n)。如果使用递归实现还需要考虑递归调用栈的空间消耗总空间复杂度为 O(n log n)通常简化为 O(n)。快速排序是原地排序不需要额外的大块辅助空间。但因为递归调用需要栈空间最好情况下的递归深度为 log n空间复杂度为 O(log n)最坏情况下递归深度为 n空间复杂度退化为 O(n)。综合来看快速排序在平均情况下的空间效率远优于归并排序。4.3 稳定性对比“稳定性”是排序算法的一个重要指标指的是相等的元素在排序后是否保持它们原有的相对顺序。如果保持则该排序是稳定的如果不保持则是不稳定的。归并排序是稳定的因为合并过程中当两个元素值相等时代码会优先取左侧数组的元素arr[i] arr[j]时取左侧从而保证相等元素的原始顺序不被破坏。快速排序是不稳定的原因在于分区过程中的交换操作。比如数组中有两个相等的元素它们可能被交换到不同的位置相对顺序因此被打乱。在实际工程中如果需要对对象按照多个字段排序稳定性就变得非常重要。比如先按姓名排序再按年龄排序稳定的排序算法可以保证年龄相同时姓名顺序仍然是正确的而快速排序在这种情况下需要额外处理。5. 快速排序边界问题专项快速排序的边界问题是初学者最容易写错的地方网上也有大量关于“快速排序的几种边界怎么记”的讨论。本节专门梳理这个问题。5.1 为什么边界容易出错快速排序的边界问题主要集中在partition方法和递归调用的区间控制上。常见的错误包括递归调用时区间重叠或遗漏导致无限递归或元素漏排。左边子数组递归使用了(left, pivotIndex)而不是(left, pivotIndex - 1)导致基准值被重复处理。扫描指针越界比如j从left扫到right时不小心访问了right 1。当所有元素都小于基准值时i和j的移动逻辑错乱导致分区结果错误。这些问题的根源在于对“区间开闭”的理解不一致。不同实现的区间定义不同有的使用左闭右闭[left, right]有的使用左闭右开[left, right)。一旦混用就会出错。5.2 边界记忆方法这里提供一个稳定的记忆框架。使用统一的“左闭右闭”区间partition(arr, left, right)负责处理[left, right]区间最终返回基准值所在的下标pivotIndex。分区完成后基准值已经在它的正确位置不需要参与后续排序。递归调用应该写成quickSort(arr, left, pivotIndex - 1)和quickSort(arr, pivotIndex 1, right)。递归终止条件是left right而不是left right因为left right时区间中只有一个元素天然有序。再来看partition方法内部的边界选定arr[right]作为基准值也可以随机选择然后交换到右侧。扫描指针j的范围是[left, right - 1]不能取到right本身。交换完基准值后i的位置就是基准值的位置。只要统一使用这套左闭右闭框架边界问题就能大大减少。建议初学者把这段代码多写几遍直到形成肌肉记忆。5.3 随机基准与三数取中为了应对快速排序最坏情况退化为 O(n²) 的问题工程中有两种常见优化策略随机基准法每次从当前区间随机选一个下标作为基准值。这样即使原始数据是近似有序的也能以极高概率避免每次都选到最小或最大的元素。import java.util.Random; private static int randomPartition(int[] arr, int left, int right) { Random random new Random(); int randIndex left random.nextInt(right - left 1); swap(arr, randIndex, right); return partition(arr, left, right); }随机化后快速排序的时间复杂度最坏情况在概率意义上几乎不可能出现实际表现非常接近 O(n log n)。三数取中法从区间的左端、右端和中间位置选出三个元素取其中位数作为基准值。这种方法在某些工程库中被广泛使用比如 JDK 的DualPivotQuicksort。private static int medianOfThree(int[] arr, int left, int right) { int mid left (right - left) / 2; // 简单的三个数比较排序 if (arr[left] arr[mid]) swap(arr, left, mid); if (arr[left] arr[right]) swap(arr, left, right); if (arr[mid] arr[right]) swap(arr, mid, right); // 此时 arr[mid] 是中位数 swap(arr, mid, right); // 将中位数交换到最右边作为基准 return partition(arr, left, right); }三数取中比随机基准更稳定因为它保证基准值至少不是当前区间的最大值或最小值但计算代价稍高。在数据量较小时两种方法效果都很好选择哪种主要看具体场景。6. 用“重组蒙娜丽莎”做一个模拟实验6.1 思路像素灰度值排序把“重组蒙娜丽莎”这个场景落地为一次代码实验假设蒙娜丽莎被拆成了 8 块像素每块有一个灰度值。灰度值从 0 到 255数值越小表示颜色越暗数值越大表示颜色越亮。打乱后的像素块灰度如下原始灰度序列[128, 32, 200, 90, 45, 255, 12, 150]我们的目标是对这些灰度值从小到大排序。排序完成后这些像素按照由暗到亮的顺序重新排列。虽然不是真正还原图像但足以演示排序算法的核心流程。6.2 生成打乱数据在实际测试中我们可能面对几千、几万甚至百万级别的数据。为了验证排序算法的性能需要能自动生成随机数据。下面是 Java 中生成随机测试数组的代码// 文件路径SortTestUtil.java import java.util.Random; public class SortTestUtil { /** * 生成指定长度的随机数组 * param size 数组长度 * param bound 随机数上限不含 */ public static int[] generateRandomArray(int size, int bound) { Random random new Random(); int[] arr new int[size]; for (int i 0; i size; i) { arr[i] random.nextInt(bound); } return arr; } /** * 打印数组前 n 个元素 */ public static void printArray(int[] arr, int n) { for (int i 0; i Math.min(arr.length, n); i) { System.out.print(arr[i] ); } System.out.println(); } }对于“重组蒙娜丽莎”的场景我们也可以模拟一个“图像分块”的像素数组灰度值范围设为 0 到 255然后分别用快速排序和归并排序处理。6.3 排序与验证下面是验证排序是否正确的代码逻辑。排序完成后遍历数组检查是否满足arr[i] arr[i 1]如果发现反例说明排序逻辑有误。// 文件路径SortValidator.java public class SortValidator { /** * 验证数组是否真正升序 */ public static boolean isSorted(int[] arr) { for (int i 0; i arr.length - 1; i) { if (arr[i] arr[i 1]) { return false; } } return true; } public static void main(String[] args) { int[] pixels {128, 32, 200, 90, 45, 255, 12, 150}; int[] quickSorted pixels.clone(); int[] mergeSorted pixels.clone(); QuickSort.quickSort(quickSorted); MergeSort.mergeSort(mergeSorted); System.out.println(快速排序结果 (isSorted(quickSorted) ? 正确 : 错误)); System.out.println(归并排序结果 (isSorted(mergeSorted) ? 正确 : 错误)); System.out.print(排序后的像素序列); for (int pixel : mergeSorted) { System.out.print(pixel ); } } }理论上两种算法都会输出相同的有序结果排序后的像素序列12 32 45 90 128 150 200 255从“蒙娜丽莎”的视角看这组从暗到亮的像素块已经可以被整齐排列完成了一次“像素重组”。7. 性能对比与实测7.1 不同数据规模对比为了直观感受两个算法的差异可以设计一个简单的性能测试生成不同规模的随机数组分别用两个算法排序并记录耗时。测试代码思路如下// 文件路径PerformanceTest.java import java.util.Random; public class PerformanceTest { public static void main(String[] args) { int[] sizes {10_000, 100_000, 1_000_000}; for (int size : sizes) { int[] base new Random().ints(size, 0, 1_000_000).toArray(); int[] arr1 base.clone(); long start1 System.currentTimeMillis(); QuickSort.quickSort(arr1); long end1 System.currentTimeMillis(); int[] arr2 base.clone(); long start2 System.currentTimeMillis(); MergeSort.mergeSort(arr2); long end2 System.currentTimeMillis(); System.out.println(数据规模 size ); System.out.println( 快速排序耗时: (end1 - start1) ms); System.out.println( 归并排序耗时: (end2 - start2) ms); } } }在数据量较小时比如 1 万以内两个算法的耗时差异通常不明显因为系统调用和初始化开销占据了主要时间。当数据量增大到百万级别快速排序通常会略快于归并排序关键原因在于归并排序需要额外分配和拷贝辅助数组带来了更大的常数开销。不同 JDK 版本、不同机器环境下实测结果会有差异但整体趋势基本一致随机大数据场景下快速排序的“就地交换”优势明显。7.2 有序数据 vs 随机数据如果测试数据本身就是有序的情况就完全不同了。归并排序面对有序数组依然需要完整的合并过程时间复杂度仍然是 O(n log n)。快速排序如果使用固定的“最右边元素作为基准值”面对有序数组时每次都选到最大值分区极度不均衡时间复杂度退化为 O(n²)递归深度过大时甚至可能触发StackOverflowError。这就是为什么在生产环境中不能写死固定基准值。使用随机化基准或者三数取中后快速排序面对有序数组也能保持良好性能。因此在上述测试中如果没有对快速排序做随机化处理面对有序输入时会出现严重性能问题。这提醒我们任何排序算法都有适用场景不能盲目套用。7.3 结合场景选型实际项目中选型时可以参考以下建议对普通数组排序且对稳定性没有要求时优先选择快速排序。它的平均性能好就地排序节省空间Java 标准库的Arrays.sort()对基本类型就使用了双轴快速排序。需要对对象排序且要求保持稳定性时优先选择归并排序。Java 中对对象数组的排序比如Collections.sort()底层使用 TimSort它的核心思想正是归并排序的升级版。数据存储在链表中时归并排序更合适。因为链表不支持随机访问快速排序中的“选基准、交换元素”在链表上操作代价较高而归并排序只需要遍历和指针拼接反而实现简洁、效率不错。数据规模非常小时插入排序可能比快速排序和归并排序更快。工程实现中通常设置一个阈值比如长度小于 47 时改用插入排序。8. 常见问题与排查思路在学习过程中很多读者会遇到类似的问题这里整理一份高频问题排查表。问题现象常见原因解决思路递归调用栈溢出快速排序选到固定基准面对有序数据退化为 O(n²)递归深度过大使用随机基准法或三数取中法排序结果中有个别元素漏排递归边界写错漏掉了pivotIndex左侧或右侧的区间检查(left, pivotIndex - 1)和(pivotIndex 1, right)区间归并排序结果错误合并时指针越界或辅助数组拷贝范围错误检查while (i mid j right)循环条件数组越界异常partition中扫描指针进入right之外的区间确认j的范围是[left, right - 1]归并排序空间占用过大每次递归都创建新的辅助数组在递归外创建一次性辅助数组合并时重复使用相等元素顺序被打乱合并时使用了arr[i] arr[j]而不是合并时用保持稳定性排序结果正确但性能极慢递归中频繁创建对象或快速排序未优化考虑将快速排序的小区间改为插入排序减少递归开销数组已经有序但快速排序依然很慢固定基准值重复选到最值增加随机化或三数取中逻辑如果遇到问题可以从以下排查清单开始先用小规模数据比如 5 到 10 个元素手工推演一遍算法流程。使用print在关键节点输出数组状态观察分区是否均衡。验证基准值最终是否位于正确位置。将数组长度设为 0、1、2 等边界情况分别测试。检查递归终止条件是否覆盖了空区间和单元素区间。9. 最佳实践与工程建议9.1 通用排序工具类的最佳实践在真实的项目代码中我们不应该每次手写排序逻辑而应该使用语言标准库提供的排序方法。但理解算法原理能帮助你做出更合理的选型。在 Java 中// 对基本类型数组使用双轴快速排序 Arrays.sort(intArray); // 对对象列表使用 TimSort稳定排序 Collections.sort(objectList);在 C 中#include algorithm std::sort(vec.begin(), vec.end()); // 快速排序变体不稳定 std::stable_sort(vec.begin(), vec.end()); // 归并排序变体稳定开发者需要清楚这些内置排序的特性才能在有稳定性需求的场景下选择正确的方法。9.2 手写排序时的工程建议如果确实需要自己实现排序建议遵循以下原则统一区间定义。整个项目或代码模块中统一使用“左闭右闭”或“左闭右开”不要混用。这能极大减少边界错误。减少递归开销。在快速排序中当子数组长度小于某个阈值比如 10 到 16时可以改用插入排序避免过多的递归调用。private static final int INSERTION_SORT_THRESHOLD 10; private static void optimizedSort(int[] arr, int left, int right) { if (right - left 1 INSERTION_SORT_THRESHOLD) { insertionSort(arr, left, right); return; } // ... 正常快速排序逻辑 }防御性编程。排序函数入口处对null和空数组做判断避免空指针异常。数据安全与备份。在需要排序的数据涉及生产环境时务必先对原始数据备份。尤其是当排序逻辑随后会执行更新或删除操作时更应该先在小规模测试集上验证确保排序结果符合预期再处理全量数据。9.3 性能优化要点归并排序的性能优化重点在于减少辅助数组的创建和拷贝。可以在递归函数外创建一次辅助数组合并时复用还可以在合并时判断左半部分最大值是否已经小于右半部分最小值如果是则说明两部分已经有序可以直接跳过合并步骤。快速排序的性能优化重点在于基准值的选择和小区间处理。除了前面提到的随机化和三数取中还可以考虑在partition时将等于基准值的元素集中到中间从而减少重复值的交换次数这也是“三路快速排序”的核心思想在处理大量重复元素的数组时效果显著。10. 总结与下一步学习快速排序与归并排序是有互补关系的两个经典算法。归并排序以稳定的 O(n log n) 时间和稳定的排序性质换取 O(n) 的空间开销快速排序以极致的时间和空间效率换取理论上的最坏情况退化风险。理解了它们在分治策略、稳定性、空间开销上的差异才算真正掌握了这两个算法。建议你按照本文的代码在本地环境中亲自运行一遍修改注释中的参数观察结果变化。尤其建议把快速排序的边界问题多写几遍尝试使用“左闭右闭”和“左闭右开”两种方式分别实现一次体会它们之间的差异。后续可以继续学习堆排序、计数排序、基数排序并尝试分析 Java 标准库中DualPivotQuicksort和 TimSort 的实现思路。这些内容掌握后你对排序算法的理解会进入一个全新的层次。
返回列表