1. 快速排序为什么它这么快如果你刚开始学算法可能会觉得排序是个挺枯燥的事。但相信我快速排序绝对是个例外。我第一次接触它的时候感觉就像第一次看到魔术表演——明明是一堆乱序的数字经过几轮“分分合合”瞬间就变得整整齐齐。它不像冒泡排序那样慢吞吞地一个个比较也不像插入排序那样小心翼翼。快速排序人如其名主打一个“快”字而且它的思想非常巧妙理解了之后你会觉得编程真有意思。那么它到底快在哪里呢核心秘密就在于“分治法”。你可以把它想象成处理一个超级混乱的衣柜。冒泡排序的做法是你站在衣柜前把第一件衣服和第二件比如果顺序不对就交换然后第二件和第三件比……这样从头到尾比一遍可能只把最大的一件衣服挪到了最后。效率很低对吧快速排序的做法就聪明多了它直接从衣柜里拎出一件衣服比如一件T恤作为“基准”然后把所有比这件T恤薄的衣服扔到左边所有比它厚的衣服扔到右边。一下子整个衣柜就被分成了“薄衣服区”和“厚衣服区”。接下来它再对左边这堆“薄衣服”和右边这堆“厚衣服”分别重复这个操作——各自再拎出一件基准衣服再分区。就这样一层层分下去直到每一堆里只剩下一件或没有衣服整个衣柜自然就整理好了。这种“分而治之”的策略让快速排序在大多数情况下效率极高平均时间复杂度能达到O(n log n)。这意味着如果给100个数排序它大概只需要进行几百次操作而冒泡排序在最坏情况下可能需要近万次。当然它也不是完美的如果你每次都特别倒霉选到的“基准”恰好是当前数列里最大或最小的那个比如你想整理夏天的T恤却拎出了一件羽绒服当基准那它的效率就会退化成O(n²)和冒泡排序一样慢了。不过别担心后面我们会聊到怎么避免这种“倒霉”情况。简单来说快速排序就是一个不断“选基准、分左右、递归处理”的过程。它优雅、高效是面试中的常客也是实际开发中应用最广泛的排序算法之一。接下来我们就一层层剥开它的外壳看看这个“魔术”到底是怎么变的。2. 庖丁解牛快速排序的核心原理与分治策略理解了快速排序像整理衣柜的比喻后我们得深入它的内部看看这个“分治”策略在代码世界里具体是怎么运作的。这就像你知道了魔术的大概手法现在要拆解每一个步骤。2.1 分治思想的精妙之处“分治”这个词听起来高大上其实很简单就是“分而治之”。把一个复杂的大问题拆分成若干个规模较小、结构相似的子问题然后分别解决这些子问题最后把子问题的解合并起来就得到了大问题的解。在快速排序里这个大问题就是“给整个数列排序”。我们怎么拆呢第一步“分”我们不是直接去排序而是先做一次“分区”操作。从数列中挑出一个元素基准数然后重新排列数列让所有比基准数小的元素都摆到它左边所有比基准数大的元素都摆到它右边。经过这一趟操作基准数本身就找到了它在最终有序序列中正确的位置也就是说经过一次分区我们至少搞定了一个元素的最终位置并且把原问题划分成了“左半区排序”和“右半区排序”两个子问题。这两个子问题比原问题规模更小而且互不干扰。第二步“治”对于划分出来的左半区和右半区我们分别递归地调用快速排序函数本身。因为左半区的所有数都比基准数小右半区的所有数都比基准数大所以当左、右两个子序列都排好序后整个序列自然就有序了。递归的终止条件就是子序列里只剩一个元素或者没有元素left right这时候它本身就是有序的无需再排。这个递归过程就像一棵倒着的树。树根是第一次分区然后生出两个树枝左子序列和右子序列每个树枝再继续分叉直到叶子节点单个元素。这种结构正是其高效的原因因为它避免了大量不必要的比较。2.2 一趟排序分区的详细拆解分区是快速排序的灵魂也是最需要理解的一步。我们以原始文章中的代码为例详细走一遍这个过程。假设我们有一个数组[5, 3, 8, 4, 2]我们要对它进行升序排序。初始化left 0,right 4。我们选择最左边的元素arr[left]也就是5作为基准数pos。同时设置两个“指针”i left,j right。i从左往右找j从右往左找。从右往左扫描while (i j arr[j] pos) j--;。j从位置4开始值是22 5所以循环条件arr[j] pos不成立j停在4。然后执行arr[i] arr[j];即把arr[4]的2赋值给arr[0]。此时数组变为[2, 3, 8, 4, 2]。注意原arr[0]的值5我们已经保存在pos里了所以覆盖掉没关系。从左往右扫描while (i j arr[i] pos) i;。i从位置0开始值是22 5所以i变成1位置1的值是33 5i变成2位置2的值是88 5循环停止i停在2。然后执行arr[j] arr[i];即把arr[2]的8赋值给arr[4]。数组变为[2, 3, 8, 4, 8]。重复步骤2和3此时i2,j4i j仍然成立。再次从右扫描j从4开始值是88 5所以j--变成3位置3的值是44 5停止j停在3。执行arr[i] arr[j]即把4赋值给arr[2]。数组变为[2, 3, 4, 4, 8]。再次从左扫描i从2开始值是44 5所以i变成3位置3的值是44 5i变成4。此时i变成了4不再小于j(3)循环停止。放置基准数大循环while (ij)结束此时i和j相遇在位置3实际上i4,j3但退出时i可能大于j通常我们以i或j的最终位置作为基准点代码里用i。执行arr[i] pos;但这里有个细节原代码在循环外用arr[i] pos。更常见的写法是在循环结束后将基准数放入arr[i]或arr[j]的位置。在我们的推演中循环结束时i4我们把基准数5放入arr[4]。最终数组为[2, 3, 4, 5, 8]。看一趟操作下来基准数5已经稳稳地坐在了它最终的位置索引3。左边的[2,3,4]全部小于5右边的[8]大于5。接下来我们只需要递归地对[2,3,4]和[8]分别进行同样的快速排序即可。这个过程清晰展示了如何通过“挖坑填数”的方式完成分区而不需要额外的存储空间原地排序。3. 一图胜千言用流程图看清算法脉络文字描述和代码推演虽然详细但对于理解算法整体的控制流和递归结构一张清晰的流程图往往更直观。它能帮你在大脑中建立起算法的“骨架”以后无论遇到什么变体你都能迅速抓住核心。下面我们就来绘制并解析快速排序的流程图。流程图的核心是展示两个层面的逻辑一是单次分区操作的微观步骤二是递归调用的宏观结构。我们可以从主函数main()的入口开始。首先主函数负责输入待排序的数组并计算其长度sz。然后它调用快速排序的核心函数qSort(left, right, arr)传入数组的左右边界。从这里开始流程图分支出两条主线。第一条主线是qSort函数的内部逻辑分区过程。这是一个判断和循环交织的过程。流程图的第一步是一个菱形判断框left right?。这是递归的终止条件如果当前子数组没有元素或只有一个元素直接返回这是保证递归能结束的关键。如果不满足终止条件则进入分区操作初始化指针i和j选取基准数pos。接着是一个大的循环判断while (i j)。在这个循环内嵌套着两个小的循环从右向左扫描的循环while (i j arr[j] pos) j--;找到第一个小于pos的数。执行赋值arr[i] arr[j]。从左向右扫描的循环while (i j arr[i] pos) i;找到第一个大于pos的数。执行赋值arr[j] arr[i]。 这个大的while循环会一直进行直到i和j相遇。退出循环后将基准数pos放入相遇的位置arr[i]。至此一趟分区完成基准数归位。第二条主线是递归调用的展开。在分区操作完成后流程图不会直接结束而是会分出两个新的箭头分别指向两个新的qSort函数调用qSort(left, i-1, arr)和qSort(i1, right, arr)。这两个箭头代表了递归的深入它们会各自开启一个全新的、但规模更小的流程图副本处理左半区和右半区。每个副本内部又会重复上述的分区判断、循环和可能产生的更深层递归调用。整个流程图像一棵自上而下生长的树。主函数是树根第一次qSort调用是主干它产生两个分支左递归和右递归每个分支又可能继续分叉直到遇到叶子节点终止条件。通过这样的图示你可以非常清晰地看到算法是如何通过不断地“分”来缩小问题规模又通过递归调用自身来“治”理这些子问题的。当所有分支都到达叶子节点并返回时这棵树就从叶子到根完成了整个排序过程。把这张图印在脑子里再去看任何快速排序的代码你都会觉得脉络分明不再是一团乱麻。4. 从理论到实践手把手实现完整代码看懂了原理和流程图是时候动手把代码写出来了。纸上得来终觉浅绝知此事要躬行。我会带你一步步写出清晰、健壮且高效的快速排序代码并解释每一个关键细节。我们使用 C 语言来实现因为它足够底层能让我们看清所有的操作。4.1 核心递归函数 qSort 的实现我们先聚焦于最核心的排序函数。这里我提供一个比原始文章更清晰、注释更详细的版本并解释一些容易踩坑的地方。/** * 快速排序递归函数 * param left 当前待排序子数组的左边界索引 * param right 当前待排序子数组的右边界索引 * param arr 待排序的数组 */ void quickSort(int left, int right, int arr[]) { // 1. 递归终止条件子数组长度为0或1 if (left right) { return; } // 2. 初始化指针和基准数 int i left; // 左指针向右扫描 int j right; // 右指针向左扫描 int pivot arr[left]; // 选择最左边的元素作为基准数 // 3. 核心分区操作 while (i j) { // 3.1 先从右往左找找到第一个小于pivot的数 // 注意这里的判断条件必须是 arr[j] pivot等于的情况也要跳过 // 如果写成 arr[j] pivot当遇到等于pivot的值时指针会错误地停下 while (i j arr[j] pivot) { j--; } // 找到后将其放到左边i的位置可以理解为填上左边的“坑” if (i j) { arr[i] arr[j]; i; // 左指针位置已被填充可以向右移动一位准备从左边开始找 } // 3.2 再从左往右找找到第一个大于pivot的数 while (i j arr[i] pivot) { i; } // 找到后将其放到右边j的位置填上右边的“坑” if (i j) { arr[j] arr[i]; j--; // 右指针位置已被填充可以向左移动一位 } } // 结束大循环此时 i j这就是基准数该放的位置 // 4. 基准数归位 arr[i] pivot; // 5. 递归排序左右子数组 // 注意边界左子数组是 [left, i-1]右子数组是 [i1, right] quickSort(left, i - 1, arr); quickSort(i 1, right, arr); }几个关键点解释基准数选择这里简单选择了最左边的元素 (arr[left])。这是最简单的方式但在数组已经有序或逆序时会导致最坏情况O(n²)。在实际应用中通常会采用“三数取中”法取左端、中间、右端三个数的中值或随机选择来避免这个问题。“挖坑填数”代码中arr[i] arr[j]和arr[j] arr[i]的操作形象地称为挖坑填数。我们先把基准数pivot挖出来保存起来这样arr[i]的位置就空出来了一个坑。然后从右找小数填到左边的坑这时右边arr[j]又空出一个坑再从左找大数填到右边的坑……如此交替直到指针相遇最后把基准数填到最后的坑里。循环条件中的等号arr[j] pivot和arr[i] pivot中的等号 (,) 至关重要。它确保了在遇到与基准数相等的元素时指针会继续移动而不是停下来交换。这能让相等的元素相对均匀地分布在分区两侧对于包含大量重复元素的数组能避免递归深度变得极端是一种简单的优化。4.2 主函数与测试用例核心函数写好了我们需要一个main函数来驱动它并测试各种情况。#include stdio.h #include stdlib.h // 为了使用 rand() 和 srand() #include time.h // 为了使用 time() // 这里插入上面的 quickSort 函数 int main() { int arr1[] {5, 3, 8, 4, 2, 7, 1, 10}; int n1 sizeof(arr1) / sizeof(arr1[0]); printf(原始数组1: ); for (int i 0; i n1; i) printf(%d , arr1[i]); printf(\n); quickSort(0, n1 - 1, arr1); printf(排序后数组1: ); for (int i 0; i n1; i) printf(%d , arr1[i]); printf(\n\n); // 测试已排序数组 int arr2[] {1, 2, 3, 4, 5}; int n2 sizeof(arr2) / sizeof(arr2[0]); printf(原始数组2 (已排序): ); for (int i 0; i n2; i) printf(%d , arr2[i]); printf(\n); quickSort(0, n2 - 1, arr2); printf(排序后数组2: ); for (int i 0; i n2; i) printf(%d , arr2[i]); printf(\n\n); // 测试逆序数组 int arr3[] {10, 8, 6, 4, 2}; int n3 sizeof(arr3) / sizeof(arr3[0]); printf(原始数组3 (逆序): ); for (int i 0; i n3; i) printf(%d , arr3[i]); printf(\n); quickSort(0, n3 - 1, arr3); printf(排序后数组3: ); for (int i 0; i n3; i) printf(%d , arr3[i]); printf(\n\n); // 测试随机大数据观察效率 srand(time(NULL)); // 设置随机种子 int size 20; int arr4[size]; printf(原始数组4 (随机%d个数): , size); for (int i 0; i size; i) { arr4[i] rand() % 100; // 生成0-99的随机数 printf(%d , arr4[i]); } printf(\n); quickSort(0, size - 1, arr4); printf(排序后数组4: ); for (int i 0; i size; i) printf(%d , arr4[i]); printf(\n); return 0; }这个测试用例覆盖了几种典型情况普通乱序数组、已排序数组测试最坏情况、逆序数组测试另一种最坏情况以及随机生成的大数组。运行这段代码你可以直观地看到快速排序的效果并观察在不同数据特征下的表现。对于已排序和逆序数组由于我们固定选择最左元素为基准递归树会退化成一条链你可以尝试修改quickSort函数加入随机选择基准的逻辑对比一下性能差异这会让你对算法的理解更深一层。5. 避坑指南与实战优化代码跑起来结果正确是不是就万事大吉了别急在实际项目和面试中快速排序还有很多细节和优化点需要考虑。这些才是区分“会用”和“精通”的关键。我在这里分享几个我踩过的坑和常用的优化技巧。第一个大坑递归深度与栈溢出。这是我们上面提到的最坏情况导致的。当数组已经有序升序或降序时如果你总是选择第一个或最后一个元素作为基准那么每次分区都极不平衡递归树的高度会达到n递归调用需要压栈n层。对于大的n比如10万这很可能导致程序栈溢出。解决方案就是优化基准数的选择。一个简单有效的方法是“三数取中法”。在分区开始前我们取arr[left]、arr[mid](mid (leftright)/2)、arr[right]这三个数将大小居中的那个与arr[left]交换然后再以arr[left]作为基准。这样能大概率避免选取到极端值。第二个坑重复元素导致的性能下降。如果数组中有大量重复元素我们之前写的代码遇到等于基准的数也移动指针表现尚可。但有一种经典的优化叫“三路快速排序”它专门处理重复元素。它将数组分成三部分小于基准、等于基准、大于基准。这样一次分区后所有等于基准的元素都就位了递归时只需要处理小于和大于的部分效率更高。在处理包含大量重复数据的场景时比如按性别排序这个优化效果显著。第三个是工程实践中的优化小数组切换为插入排序。快速排序的递归在小数组上开销相对较大而插入排序在小数组上非常高效且稳定。一个常见的优化是在quickSort函数开始时判断如果(right - left 1) 某个阈值比如10或20就不继续递归了直接对这个小子数组调用插入排序。这个技巧被广泛应用在标准库如C的std::sort的实现中。第四个是关于稳定性的理解。快速排序是一个不稳定的排序算法。稳定性的意思是如果两个元素值相等排序后它们的相对位置不会改变。在快速排序的分区交换过程中相等的元素可能会被交换到另一边从而打乱原有的相对顺序。如果你需要稳定性应该选择归并排序。在面试中被问到“快速排序的优缺点”时不稳定是一个必须提到的点。最后一定要自己手动模拟。找一张纸写下一组数据按照代码逻辑一步步去推演i和j的移动、数组的变化。这个过程看似笨拙却是理解算法最扎实的方法。我当年就是这么干的推演了几遍之后整个分区过程就像刻在脑子里一样清晰再也不会写错循环条件。理解了这些坑和优化你不仅掌握了快速排序的“形”更把握了它的“神”无论是应对面试还是解决实际问题都能更加从容。
快速排序实战：从算法原理到代码实现（含流程图解析）
1. 快速排序为什么它这么快如果你刚开始学算法可能会觉得排序是个挺枯燥的事。但相信我快速排序绝对是个例外。我第一次接触它的时候感觉就像第一次看到魔术表演——明明是一堆乱序的数字经过几轮“分分合合”瞬间就变得整整齐齐。它不像冒泡排序那样慢吞吞地一个个比较也不像插入排序那样小心翼翼。快速排序人如其名主打一个“快”字而且它的思想非常巧妙理解了之后你会觉得编程真有意思。那么它到底快在哪里呢核心秘密就在于“分治法”。你可以把它想象成处理一个超级混乱的衣柜。冒泡排序的做法是你站在衣柜前把第一件衣服和第二件比如果顺序不对就交换然后第二件和第三件比……这样从头到尾比一遍可能只把最大的一件衣服挪到了最后。效率很低对吧快速排序的做法就聪明多了它直接从衣柜里拎出一件衣服比如一件T恤作为“基准”然后把所有比这件T恤薄的衣服扔到左边所有比它厚的衣服扔到右边。一下子整个衣柜就被分成了“薄衣服区”和“厚衣服区”。接下来它再对左边这堆“薄衣服”和右边这堆“厚衣服”分别重复这个操作——各自再拎出一件基准衣服再分区。就这样一层层分下去直到每一堆里只剩下一件或没有衣服整个衣柜自然就整理好了。这种“分而治之”的策略让快速排序在大多数情况下效率极高平均时间复杂度能达到O(n log n)。这意味着如果给100个数排序它大概只需要进行几百次操作而冒泡排序在最坏情况下可能需要近万次。当然它也不是完美的如果你每次都特别倒霉选到的“基准”恰好是当前数列里最大或最小的那个比如你想整理夏天的T恤却拎出了一件羽绒服当基准那它的效率就会退化成O(n²)和冒泡排序一样慢了。不过别担心后面我们会聊到怎么避免这种“倒霉”情况。简单来说快速排序就是一个不断“选基准、分左右、递归处理”的过程。它优雅、高效是面试中的常客也是实际开发中应用最广泛的排序算法之一。接下来我们就一层层剥开它的外壳看看这个“魔术”到底是怎么变的。2. 庖丁解牛快速排序的核心原理与分治策略理解了快速排序像整理衣柜的比喻后我们得深入它的内部看看这个“分治”策略在代码世界里具体是怎么运作的。这就像你知道了魔术的大概手法现在要拆解每一个步骤。2.1 分治思想的精妙之处“分治”这个词听起来高大上其实很简单就是“分而治之”。把一个复杂的大问题拆分成若干个规模较小、结构相似的子问题然后分别解决这些子问题最后把子问题的解合并起来就得到了大问题的解。在快速排序里这个大问题就是“给整个数列排序”。我们怎么拆呢第一步“分”我们不是直接去排序而是先做一次“分区”操作。从数列中挑出一个元素基准数然后重新排列数列让所有比基准数小的元素都摆到它左边所有比基准数大的元素都摆到它右边。经过这一趟操作基准数本身就找到了它在最终有序序列中正确的位置也就是说经过一次分区我们至少搞定了一个元素的最终位置并且把原问题划分成了“左半区排序”和“右半区排序”两个子问题。这两个子问题比原问题规模更小而且互不干扰。第二步“治”对于划分出来的左半区和右半区我们分别递归地调用快速排序函数本身。因为左半区的所有数都比基准数小右半区的所有数都比基准数大所以当左、右两个子序列都排好序后整个序列自然就有序了。递归的终止条件就是子序列里只剩一个元素或者没有元素left right这时候它本身就是有序的无需再排。这个递归过程就像一棵倒着的树。树根是第一次分区然后生出两个树枝左子序列和右子序列每个树枝再继续分叉直到叶子节点单个元素。这种结构正是其高效的原因因为它避免了大量不必要的比较。2.2 一趟排序分区的详细拆解分区是快速排序的灵魂也是最需要理解的一步。我们以原始文章中的代码为例详细走一遍这个过程。假设我们有一个数组[5, 3, 8, 4, 2]我们要对它进行升序排序。初始化left 0,right 4。我们选择最左边的元素arr[left]也就是5作为基准数pos。同时设置两个“指针”i left,j right。i从左往右找j从右往左找。从右往左扫描while (i j arr[j] pos) j--;。j从位置4开始值是22 5所以循环条件arr[j] pos不成立j停在4。然后执行arr[i] arr[j];即把arr[4]的2赋值给arr[0]。此时数组变为[2, 3, 8, 4, 2]。注意原arr[0]的值5我们已经保存在pos里了所以覆盖掉没关系。从左往右扫描while (i j arr[i] pos) i;。i从位置0开始值是22 5所以i变成1位置1的值是33 5i变成2位置2的值是88 5循环停止i停在2。然后执行arr[j] arr[i];即把arr[2]的8赋值给arr[4]。数组变为[2, 3, 8, 4, 8]。重复步骤2和3此时i2,j4i j仍然成立。再次从右扫描j从4开始值是88 5所以j--变成3位置3的值是44 5停止j停在3。执行arr[i] arr[j]即把4赋值给arr[2]。数组变为[2, 3, 4, 4, 8]。再次从左扫描i从2开始值是44 5所以i变成3位置3的值是44 5i变成4。此时i变成了4不再小于j(3)循环停止。放置基准数大循环while (ij)结束此时i和j相遇在位置3实际上i4,j3但退出时i可能大于j通常我们以i或j的最终位置作为基准点代码里用i。执行arr[i] pos;但这里有个细节原代码在循环外用arr[i] pos。更常见的写法是在循环结束后将基准数放入arr[i]或arr[j]的位置。在我们的推演中循环结束时i4我们把基准数5放入arr[4]。最终数组为[2, 3, 4, 5, 8]。看一趟操作下来基准数5已经稳稳地坐在了它最终的位置索引3。左边的[2,3,4]全部小于5右边的[8]大于5。接下来我们只需要递归地对[2,3,4]和[8]分别进行同样的快速排序即可。这个过程清晰展示了如何通过“挖坑填数”的方式完成分区而不需要额外的存储空间原地排序。3. 一图胜千言用流程图看清算法脉络文字描述和代码推演虽然详细但对于理解算法整体的控制流和递归结构一张清晰的流程图往往更直观。它能帮你在大脑中建立起算法的“骨架”以后无论遇到什么变体你都能迅速抓住核心。下面我们就来绘制并解析快速排序的流程图。流程图的核心是展示两个层面的逻辑一是单次分区操作的微观步骤二是递归调用的宏观结构。我们可以从主函数main()的入口开始。首先主函数负责输入待排序的数组并计算其长度sz。然后它调用快速排序的核心函数qSort(left, right, arr)传入数组的左右边界。从这里开始流程图分支出两条主线。第一条主线是qSort函数的内部逻辑分区过程。这是一个判断和循环交织的过程。流程图的第一步是一个菱形判断框left right?。这是递归的终止条件如果当前子数组没有元素或只有一个元素直接返回这是保证递归能结束的关键。如果不满足终止条件则进入分区操作初始化指针i和j选取基准数pos。接着是一个大的循环判断while (i j)。在这个循环内嵌套着两个小的循环从右向左扫描的循环while (i j arr[j] pos) j--;找到第一个小于pos的数。执行赋值arr[i] arr[j]。从左向右扫描的循环while (i j arr[i] pos) i;找到第一个大于pos的数。执行赋值arr[j] arr[i]。 这个大的while循环会一直进行直到i和j相遇。退出循环后将基准数pos放入相遇的位置arr[i]。至此一趟分区完成基准数归位。第二条主线是递归调用的展开。在分区操作完成后流程图不会直接结束而是会分出两个新的箭头分别指向两个新的qSort函数调用qSort(left, i-1, arr)和qSort(i1, right, arr)。这两个箭头代表了递归的深入它们会各自开启一个全新的、但规模更小的流程图副本处理左半区和右半区。每个副本内部又会重复上述的分区判断、循环和可能产生的更深层递归调用。整个流程图像一棵自上而下生长的树。主函数是树根第一次qSort调用是主干它产生两个分支左递归和右递归每个分支又可能继续分叉直到遇到叶子节点终止条件。通过这样的图示你可以非常清晰地看到算法是如何通过不断地“分”来缩小问题规模又通过递归调用自身来“治”理这些子问题的。当所有分支都到达叶子节点并返回时这棵树就从叶子到根完成了整个排序过程。把这张图印在脑子里再去看任何快速排序的代码你都会觉得脉络分明不再是一团乱麻。4. 从理论到实践手把手实现完整代码看懂了原理和流程图是时候动手把代码写出来了。纸上得来终觉浅绝知此事要躬行。我会带你一步步写出清晰、健壮且高效的快速排序代码并解释每一个关键细节。我们使用 C 语言来实现因为它足够底层能让我们看清所有的操作。4.1 核心递归函数 qSort 的实现我们先聚焦于最核心的排序函数。这里我提供一个比原始文章更清晰、注释更详细的版本并解释一些容易踩坑的地方。/** * 快速排序递归函数 * param left 当前待排序子数组的左边界索引 * param right 当前待排序子数组的右边界索引 * param arr 待排序的数组 */ void quickSort(int left, int right, int arr[]) { // 1. 递归终止条件子数组长度为0或1 if (left right) { return; } // 2. 初始化指针和基准数 int i left; // 左指针向右扫描 int j right; // 右指针向左扫描 int pivot arr[left]; // 选择最左边的元素作为基准数 // 3. 核心分区操作 while (i j) { // 3.1 先从右往左找找到第一个小于pivot的数 // 注意这里的判断条件必须是 arr[j] pivot等于的情况也要跳过 // 如果写成 arr[j] pivot当遇到等于pivot的值时指针会错误地停下 while (i j arr[j] pivot) { j--; } // 找到后将其放到左边i的位置可以理解为填上左边的“坑” if (i j) { arr[i] arr[j]; i; // 左指针位置已被填充可以向右移动一位准备从左边开始找 } // 3.2 再从左往右找找到第一个大于pivot的数 while (i j arr[i] pivot) { i; } // 找到后将其放到右边j的位置填上右边的“坑” if (i j) { arr[j] arr[i]; j--; // 右指针位置已被填充可以向左移动一位 } } // 结束大循环此时 i j这就是基准数该放的位置 // 4. 基准数归位 arr[i] pivot; // 5. 递归排序左右子数组 // 注意边界左子数组是 [left, i-1]右子数组是 [i1, right] quickSort(left, i - 1, arr); quickSort(i 1, right, arr); }几个关键点解释基准数选择这里简单选择了最左边的元素 (arr[left])。这是最简单的方式但在数组已经有序或逆序时会导致最坏情况O(n²)。在实际应用中通常会采用“三数取中”法取左端、中间、右端三个数的中值或随机选择来避免这个问题。“挖坑填数”代码中arr[i] arr[j]和arr[j] arr[i]的操作形象地称为挖坑填数。我们先把基准数pivot挖出来保存起来这样arr[i]的位置就空出来了一个坑。然后从右找小数填到左边的坑这时右边arr[j]又空出一个坑再从左找大数填到右边的坑……如此交替直到指针相遇最后把基准数填到最后的坑里。循环条件中的等号arr[j] pivot和arr[i] pivot中的等号 (,) 至关重要。它确保了在遇到与基准数相等的元素时指针会继续移动而不是停下来交换。这能让相等的元素相对均匀地分布在分区两侧对于包含大量重复元素的数组能避免递归深度变得极端是一种简单的优化。4.2 主函数与测试用例核心函数写好了我们需要一个main函数来驱动它并测试各种情况。#include stdio.h #include stdlib.h // 为了使用 rand() 和 srand() #include time.h // 为了使用 time() // 这里插入上面的 quickSort 函数 int main() { int arr1[] {5, 3, 8, 4, 2, 7, 1, 10}; int n1 sizeof(arr1) / sizeof(arr1[0]); printf(原始数组1: ); for (int i 0; i n1; i) printf(%d , arr1[i]); printf(\n); quickSort(0, n1 - 1, arr1); printf(排序后数组1: ); for (int i 0; i n1; i) printf(%d , arr1[i]); printf(\n\n); // 测试已排序数组 int arr2[] {1, 2, 3, 4, 5}; int n2 sizeof(arr2) / sizeof(arr2[0]); printf(原始数组2 (已排序): ); for (int i 0; i n2; i) printf(%d , arr2[i]); printf(\n); quickSort(0, n2 - 1, arr2); printf(排序后数组2: ); for (int i 0; i n2; i) printf(%d , arr2[i]); printf(\n\n); // 测试逆序数组 int arr3[] {10, 8, 6, 4, 2}; int n3 sizeof(arr3) / sizeof(arr3[0]); printf(原始数组3 (逆序): ); for (int i 0; i n3; i) printf(%d , arr3[i]); printf(\n); quickSort(0, n3 - 1, arr3); printf(排序后数组3: ); for (int i 0; i n3; i) printf(%d , arr3[i]); printf(\n\n); // 测试随机大数据观察效率 srand(time(NULL)); // 设置随机种子 int size 20; int arr4[size]; printf(原始数组4 (随机%d个数): , size); for (int i 0; i size; i) { arr4[i] rand() % 100; // 生成0-99的随机数 printf(%d , arr4[i]); } printf(\n); quickSort(0, size - 1, arr4); printf(排序后数组4: ); for (int i 0; i size; i) printf(%d , arr4[i]); printf(\n); return 0; }这个测试用例覆盖了几种典型情况普通乱序数组、已排序数组测试最坏情况、逆序数组测试另一种最坏情况以及随机生成的大数组。运行这段代码你可以直观地看到快速排序的效果并观察在不同数据特征下的表现。对于已排序和逆序数组由于我们固定选择最左元素为基准递归树会退化成一条链你可以尝试修改quickSort函数加入随机选择基准的逻辑对比一下性能差异这会让你对算法的理解更深一层。5. 避坑指南与实战优化代码跑起来结果正确是不是就万事大吉了别急在实际项目和面试中快速排序还有很多细节和优化点需要考虑。这些才是区分“会用”和“精通”的关键。我在这里分享几个我踩过的坑和常用的优化技巧。第一个大坑递归深度与栈溢出。这是我们上面提到的最坏情况导致的。当数组已经有序升序或降序时如果你总是选择第一个或最后一个元素作为基准那么每次分区都极不平衡递归树的高度会达到n递归调用需要压栈n层。对于大的n比如10万这很可能导致程序栈溢出。解决方案就是优化基准数的选择。一个简单有效的方法是“三数取中法”。在分区开始前我们取arr[left]、arr[mid](mid (leftright)/2)、arr[right]这三个数将大小居中的那个与arr[left]交换然后再以arr[left]作为基准。这样能大概率避免选取到极端值。第二个坑重复元素导致的性能下降。如果数组中有大量重复元素我们之前写的代码遇到等于基准的数也移动指针表现尚可。但有一种经典的优化叫“三路快速排序”它专门处理重复元素。它将数组分成三部分小于基准、等于基准、大于基准。这样一次分区后所有等于基准的元素都就位了递归时只需要处理小于和大于的部分效率更高。在处理包含大量重复数据的场景时比如按性别排序这个优化效果显著。第三个是工程实践中的优化小数组切换为插入排序。快速排序的递归在小数组上开销相对较大而插入排序在小数组上非常高效且稳定。一个常见的优化是在quickSort函数开始时判断如果(right - left 1) 某个阈值比如10或20就不继续递归了直接对这个小子数组调用插入排序。这个技巧被广泛应用在标准库如C的std::sort的实现中。第四个是关于稳定性的理解。快速排序是一个不稳定的排序算法。稳定性的意思是如果两个元素值相等排序后它们的相对位置不会改变。在快速排序的分区交换过程中相等的元素可能会被交换到另一边从而打乱原有的相对顺序。如果你需要稳定性应该选择归并排序。在面试中被问到“快速排序的优缺点”时不稳定是一个必须提到的点。最后一定要自己手动模拟。找一张纸写下一组数据按照代码逻辑一步步去推演i和j的移动、数组的变化。这个过程看似笨拙却是理解算法最扎实的方法。我当年就是这么干的推演了几遍之后整个分区过程就像刻在脑子里一样清晰再也不会写错循环条件。理解了这些坑和优化你不仅掌握了快速排序的“形”更把握了它的“神”无论是应对面试还是解决实际问题都能更加从容。
