1. 项目概述为什么快速排序是C程序员绕不开的坎如果你写过C或者正准备深入学习这门语言那么“快速排序”这个名字你肯定不陌生。它不仅仅是数据结构与算法课程里的一个必考知识点更是面试官手里的“常客”以及实际项目中处理大规模数据时一个高效且实用的工具。我见过太多新手一提到排序脑子里就只有std::sort这当然没问题标准库很强大。但当你被问到“std::sort底层可能用了什么”或者“手写一个O(n log n)的排序”时如果对快速排序的原理和实现一知半解场面就会很尴尬。快速排序的魅力在于它“分而治之”的智慧。它不像冒泡排序那样笨拙地两两比较也不像归并排序那样需要额外的存储空间。它的核心思想是在待排序的序列中挑选一个基准元素然后通过一趟操作将序列分成独立的两部分其中一部分的所有数据都比另一部分的所有数据要小。然后再递归地对这两部分数据分别进行快速排序整个排序过程递归进行最终使整个数据变成有序序列。这个过程听起来简单但实现起来尤其是用C这种贴近底层的语言来实现里面充满了细节和“坑”。比如基准元素怎么选递归的终止条件怎么写如何避免最坏情况下的O(n²)时间复杂度这些问题的答案直接决定了你写出来的快速排序是“玩具”还是“工业级”。所以今天我们不只满足于看懂一段代码而是要亲手用C从零实现一个健壮、高效的快速排序。我会带你拆解每一个步骤解释每一个设计决策背后的原因并分享我在实际编码和调试中积累的那些教科书上不会写的经验。无论你是正在准备面试还是想夯实自己的算法基础或者单纯想领略一下经典算法的精妙这篇内容都会让你有所收获。2. 快速排序的核心原理与设计思路拆解2.1 “分治”思想快速排序的灵魂所在快速排序的“快”根源在于它的“分治”策略。理解了这个策略就抓住了它的命脉。我们可以把排序一个长数组的任务分解成排序两个更短的子数组的任务。具体来说整个过程分为三步分解从数组中选择一个元素作为“基准”。以这个基准为界重新排列数组使得所有比基准小的元素都移到基准的左边所有比基准大的元素都移到基准的右边。这个操作结束后基准元素就处于它最终应该在的位置上。这个操作通常被称为“分区”。解决递归地对基准左边和右边的两个子数组重复进行快速排序。合并因为基准已经在正确的位置且左子数组都小于基准右子数组都大于基准所以当左右子数组都排好序后整个数组自然就有序了。这一步在快速排序中不需要任何额外的合并操作这是它比归并排序更节省空间的关键。这个递归过程会一直进行直到子数组的长度为0或1即已经有序递归才会开始返回。这种策略的效率非常高因为在理想情况下每次分区都能将数组大致平分成两半递归树的深度就是log₂n而每层需要处理的元素总数是n所以平均时间复杂度是O(n log n)。2.2 关键设计决策基准选择与分区算法原理听起来很清晰但一到实现就有两个核心问题需要决策基准怎么选分区怎么做基准选择这是影响算法性能的关键。一个糟糕的基准可能导致分区极度不平衡从而退化成O(n²)的时间复杂度。固定选择比如总是选第一个或最后一个元素。这是最朴素的方法但存在致命缺陷如果输入数组已经有序或逆序那么每次分区都只能分出一个元素基准本身算法就退化成了冒泡排序。这是新手最容易踩的坑。随机选择在待排序区间内随机选择一个元素作为基准。这种方法能有效避免因输入数据特定顺序导致的最坏情况。在数学期望上它能保证算法的平均性能。这是工程实践中最常用、也最推荐的方法。三数取中法取待排序区间头、尾、中间三个元素将其中值大小居中的那个作为基准。这是一种对“随机选择”的确定性模拟也能较好地避免最坏情况且不需要生成随机数。在我们的C实现中为了兼顾简单性和鲁棒性我会采用“随机选择”作为基准策略。分区算法这是快速排序的“发动机”负责完成重新排列的核心工作。最经典、也最易懂的是Lomuto分区方案和Hoare分区方案。Lomuto分区法思路直观代码简洁。它维护一个“小于基准”的边界索引遍历数组将小于基准的元素交换到这个边界之前。但它在大数据量下交换次数可能较多且对于所有元素都相等的数组性能会退化为O(n²)。Hoare分区法由快速排序的发明者Tony Hoare提出。它使用两个指针分别从数组两端向中间扫描交换不符合条件的元素。通常比Lomuto法更高效交换次数更少但理解和实现的细节稍微复杂一点特别是边界条件的处理。为了让第一次实现更容易理解我们先从Lomuto分区法入手因为它清晰地体现了“划分区域”的思想。在掌握了核心逻辑后我们再探讨如何优化到Hoare分区法。3. C实现快速排序的详细步骤3.1 基础框架与递归函数设计我们先搭建起快速排序的递归骨架。这个函数需要知道要对数组的哪一部分进行排序所以我们传入数组的引用以及左右边界索引左闭右闭区间。#include iostream #include vector #include cstdlib // 用于 rand() #include ctime // 用于 time() // 快速排序的递归驱动函数 void quickSort(std::vectorint arr, int left, int right) { // 递归终止条件当子数组只有一个或没有元素时无需排序 if (left right) { return; } // 关键步骤1进行分区操作并获取基准元素的最终位置 int pivotIndex partition(arr, left, right); // 关键步骤2递归排序基准左边的子数组 quickSort(arr, left, pivotIndex - 1); // 关键步骤3递归排序基准右边的子数组 quickSort(arr, pivotIndex 1, right); } // 对外提供的排序接口简化调用 void quickSort(std::vectorint arr) { if (arr.empty()) return; // 初始化随机数种子用于后续随机选择基准 std::srand(static_castunsigned int(std::time(nullptr))); quickSort(arr, 0, arr.size() - 1); }代码解析与注意事项递归终止条件if (left right)这是递归的“安全阀”。当left right时区间只有一个元素当left right时区间为空比如基准是第一个元素那么左子区间的left, pivotIndex-1就会变成0, -1。没有这个条件递归将无限进行下去。随机数种子初始化我们在公开接口quickSort(arr)中初始化随机种子。切忌在递归函数quickSort(arr, left, right)内部每次调用都初始化种子这不仅没必要而且如果基于时间播种在极短时间内连续调用rand()可能会得到相同或相近的随机数序列。函数重载我们提供了两个quickSort函数。一个是对外的简单接口另一个是内部递归函数。这是一种清晰的封装方式。3.2 Lomuto分区法的实现与逐行解析现在我们来实现最核心的partition函数。这里我们采用随机选择基准的Lomuto分区法。// Lomuto分区方案 int partition(std::vectorint arr, int left, int right) { // 1. 随机选择基准元素并将其交换到当前区间的末尾right位置 // 生成一个在[left, right]范围内的随机索引 int randomIndex left std::rand() % (right - left 1); // 将随机选中的基准值交换到最右边方便后续操作 std::swap(arr[randomIndex], arr[right]); int pivot arr[right]; // 现在基准值在arr[right] // 2. 初始化“小于基准区域”的边界。i指向这个区域最后一个元素的下一个位置。 // 初始时这个区域为空所以i从left开始。 int i left; // 3. 遍历数组从left到right-1因为right是基准 for (int j left; j right; j) { // 如果当前元素arr[j]小于基准值pivot if (arr[j] pivot) { // 将arr[j]这个小于基准的元素交换到“小于基准区域”的末尾i的位置 std::swap(arr[i], arr[j]); // 将“小于基准区域”的边界向右移动一位 i; } // 如果arr[j] pivot则不做任何操作j继续向后走。 // 这些大于等于基准的元素自然就被留在了后面。 } // 4. 循环结束后所有小于pivot的元素都在区间[left, i-1]中。 // 所有大于等于pivot的元素都在区间[i, right-1]中。 // 此时arr[right]仍然是基准值pivot。 // 我们需要将基准值交换到它正确的位置也就是i的位置。 // 因为arr[i]是第一个大于等于pivot的元素或者iright交换后 // arr[i]现在的基准值左边的都小于它右边的都大于等于它。 std::swap(arr[i], arr[right]); // 5. 返回基准值的最终位置i return i; }分区过程可视化举例 假设数组arr [3, 7, 8, 5, 2, 1, 9, 4]left0,right7。随机选择基准假设选中arr[2]8将其与arr[7]4交换。数组变为[3, 7, 4, 5, 2, 1, 9, 8]pivot8。初始化i0j从0开始遍历到6。j0:arr[0]3 8交换arr[i]和arr[j]自己和自己交换i-i1。数组不变。j1:arr[1]7 8交换arr[1]和arr[1]i-i2。j2:arr[2]4 8交换arr[2]和arr[2]i-i3。j3:arr[3]5 8交换arr[3]和arr[3]i-i4。j4:arr[4]2 8交换arr[4]和arr[4]i-i5。j5:arr[5]1 8交换arr[5]和arr[5]i-i6。j6:arr[6]9 8不做任何操作。循环结束。此时i6。交换arr[i]和arr[right]即交换arr[6]9和arr[7]8。数组变为[3, 7, 4, 5, 2, 1, 8, 9]。返回pivotIndex i 6。可以看到arr[6]8左边的元素都小于8右边的元素arr[7]9大于8。注意Lomuto分区法的潜在问题当数组中存在大量与基准值相等的元素时if (arr[j] pivot)这个条件会导致这些相等元素都被划到右边大于等于区域。如果基准值恰好选到了这些重复值中的一个可能会导致分区不平衡。一个改进方法是使用“三路快速排序”将数组分为“小于”、“等于”、“大于”三部分这对于包含大量重复元素的数组效率更高。3.3 优化方向Hoare分区法与工程实践技巧掌握了基础的Lomuto分区法后我们可以看看更高效的Hoare分区法并了解一些工程上的优化技巧。Hoare分区法实现// Hoare分区方案 int partitionHoare(std::vectorint arr, int left, int right) { // 随机选择基准并交换到左边也可以不交换这里选择交换到左边作为初始基准值 int randomIndex left std::rand() % (right - left 1); std::swap(arr[randomIndex], arr[left]); int pivot arr[left]; int i left - 1; // 左指针从最左边前一位开始 int j right 1; // 右指针从最右边后一位开始 while (true) { // 从左向右找到第一个大于等于pivot的元素 do { i; } while (arr[i] pivot); // 注意这里用 不是 // 从右向左找到第一个小于等于pivot的元素 do { --j; } while (arr[j] pivot); // 注意这里用 不是 // 如果左右指针相遇或交错说明分区完成 if (i j) { return j; // 注意返回的是 j不是 i这是Hoare分区法的关键。 } // 交换这两个不符合各自区域条件的元素 std::swap(arr[i], arr[j]); // 交换后arr[i] pivot, arr[j] pivot循环继续 } } // 对应的递归函数需要稍作调整 void quickSortHoare(std::vectorint arr, int left, int right) { if (left right) return; int p partitionHoare(arr, left, right); // 注意区间划分 [left, p] 和 [p1, right] quickSortHoare(arr, left, p); quickSortHoare(arr, p 1, right); }Hoare分区法要点它返回的索引j通常不是基准值的最终位置而是分区后左子数组的右边界。基准值可能在左子数组的末尾也可能在右子数组的开头但整个数组已经被正确划分。循环内部的while条件用的是和而不是和这避免了在元素相等时的无意义交换和指针停滞但也意味着等于基准的元素也会被交换这有助于在重复元素多时平衡分区。Hoare法通常比Lomuto法执行更少的交换操作因此性能稍好。工程优化技巧小数组切换插入排序当递归到子数组规模很小比如长度小于10时快速排序的递归开销可能比排序本身还大。一个常见的优化是当right - left 某个阈值时改用简单的插入排序来处理这个小片段。插入排序对小规模、近乎有序的数据效率很高。尾递归优化观察递归调用quickSort(arr, pivotIndex 1, right)这是函数最后一步操作称为尾递归。编译器可以对其进行优化使其不增加新的调用栈深度从而避免在极端情况下如不平衡分区的栈溢出风险。我们可以手动优化先对较短的子数组进行递归较长的子数组通过循环迭代来处理。void quickSortTailOpt(std::vectorint arr, int left, int right) { while (left right) { // 用循环代替一部分递归 int pivotIndex partition(arr, left, right); // 先递归排序较短的那部分 if (pivotIndex - left right - pivotIndex) { quickSortTailOpt(arr, left, pivotIndex - 1); left pivotIndex 1; // 更新左边界循环处理长的那部分 } else { quickSortTailOpt(arr, pivotIndex 1, right); right pivotIndex - 1; // 更新右边界循环处理长的那部分 } } }三数取中法选择基准为了避免随机数生成的性能开销虽然很小可以使用确定性的“三数取中法”来选取基准通常也能获得很好的效果。4. 测试、常见问题与性能分析4.1 如何全面测试你的快速排序实现写完代码只是第一步严谨的测试才能保证其正确性和鲁棒性。你需要构建一个全面的测试集#include iostream #include vector #include algorithm // 用于 std::is_sorted 和 std::sort #include cassert void testQuickSort() { // 测试用例集合 std::vectorstd::vectorint testCases { {}, // 空数组 {1}, // 单元素数组 {2, 1}, // 两个元素逆序 {1, 2, 3, 4, 5}, // 已排序数组 {5, 4, 3, 2, 1}, // 逆序数组 {3, 1, 4, 1, 5, 9, 2, 6}, // 典型无序数组 {5, 5, 5, 5, 5}, // 所有元素相同 {-10, 0, 100, -5, 7}, // 包含负数和零 // 可以添加更大规模的随机数组测试 }; for (auto testArr : testCases) { std::vectorint arrCopy testArr; // 拷贝一份用于我们的排序 std::vectorint expected testArr; // 拷贝一份用于标准库排序 // 使用标准库排序得到正确结果 std::sort(expected.begin(), expected.end()); // 使用我们实现的快速排序 quickSort(arrCopy); // 验证结果 if (arrCopy ! expected) { std::cerr 测试失败输入; for (int num : testArr) std::cerr num ; std::cerr \n期望; for (int num : expected) std::cerr num ; std::cerr \n实际; for (int num : arrCopy) std::cerr num ; std::cerr std::endl; assert(false); // 触发断言方便调试 } else { // 也可以使用 std::is_sorted 检查 assert(std::is_sorted(arrCopy.begin(), arrCopy.end())); } } std::cout 所有基础测试用例通过 std::endl; // 压力测试大规模随机数组 const int SIZE 10000; std::vectorint largeArr(SIZE); for (int num : largeArr) { num std::rand() % 100000; } std::vectorint largeArrCopy largeArr; std::sort(largeArr.begin(), largeArr.end()); quickSort(largeArrCopy); assert(largeArr largeArrCopy); std::cout 大规模随机测试 SIZE 个元素通过 std::endl; } int main() { std::srand(static_castunsigned int(std::time(nullptr))); testQuickSort(); return 0; }4.2 常见问题与调试技巧实录在实现快速排序时以下几个问题非常常见栈溢出如果数组非常大且分区极度不平衡例如总是选到最小或最大的元素作为基准递归深度可能达到n导致调用栈溢出。解决方案使用随机化基准选择或采用尾递归优化、小数组切换插入排序等策略。死循环在分区函数中指针移动的逻辑错误可能导致无限循环。特别是在Hoare分区法中do...while循环的边界条件和终止条件i j必须非常小心。调试技巧在分区函数内打印left,right,i,j和数组状态观察指针移动是否符合预期。对于小数组如3个元素进行单步调试非常有效。排序结果不正确通常是分区后递归区间划分错误。Lomuto法递归区间应为[left, pivotIndex-1]和[pivotIndex1, right]。pivotIndex是基准的最终位置它已经排好不应再参与递归。Hoare法递归区间应为[left, p]和[p1, right]。注意返回的p不是基准位置而是分区边界。一个经典的错误是误以为p是基准位置而错误划分区间导致元素丢失或重复排序。对重复元素处理不佳如前所述基础的Lomuto法在重复元素多时性能下降。解决方案考虑实现“三路快速排序”它将数组分为“小于基准”、“等于基准”、“大于基准”三部分递归时只对“小于”和“大于”部分进行能高效处理重复元素。随机数种子问题如果在递归函数内频繁调用srand(time(nullptr))由于time函数秒级精度在同一秒内产生的随机数序列可能相同导致基准选择不“随机”。正确做法在整个排序过程开始前只初始化一次随机种子。4.3 性能分析与对比我们来简单分析一下我们实现的快速排序的性能时间复杂度平均情况 O(n log n)每次分区大致将数组平分递归树深度为log n每层处理O(n)个元素。最坏情况 O(n²)每次分区都极度不平衡例如数组已有序且总选到最值作为基准。通过随机化基准可以将最坏情况出现的概率降到极低从“必然”变为“偶然”这是随机化算法的一大优势。最好情况 O(n log n)每次分区都完美平分。空间复杂度主要消耗在递归调用栈。平均情况下深度为O(log n)因此平均空间复杂度为O(log n)。最坏情况下深度为O(n)。我们的实现是“原地排序”除了递归栈和少量临时变量不需要额外的、与n成比例的存储空间。稳定性快速排序不是稳定的排序算法。在分区过程中相等的元素可能会因为交换而改变相对次序。如果需要稳定性应考虑归并排序。与std::sort的对比 C标准库的std::sort是一个混合排序算法通常基于IntroSort内省排序。它结合了快速排序、堆排序和插入排序的优点主体使用快速排序。当递归深度超过一定阈值约为2*log₂n时可能意味着遇到了接近最坏情况此时切换到堆排序保证O(n log n)最坏时间复杂度。当子数组规模很小时切换为插入排序常数因子小。 因此std::sort在绝大多数情况下都非常高效且鲁棒是我们日常编程的首选。我们手写快速排序的目的是为了深入理解算法原理锻炼编码和调试能力而不是为了替代标准库。5. 从理论到实践一个完整的可运行示例最后让我们将所有代码整合在一起形成一个完整的、带有详细注释和测试的C文件。你可以直接复制这段代码到你的IDE如VS Code、CLion等中编译运行观察结果。#include iostream #include vector #include cstdlib #include ctime #include algorithm #include cassert // 使用随机基准的Lomuto分区法 int partition(std::vectorint arr, int left, int right) { // 1. 随机选择基准并交换到末尾 int randomIndex left std::rand() % (right - left 1); std::swap(arr[randomIndex], arr[right]); int pivot arr[right]; // 2. 初始化小于基准区域的边界 int i left; // i 指向小于基准区域的末尾的下一个位置 // 3. 遍历数组不包括基准 for (int j left; j right; j) { if (arr[j] pivot) { std::swap(arr[i], arr[j]); i; // 扩大小于基准的区域 } } // 4. 将基准放到正确位置 std::swap(arr[i], arr[right]); // 5. 返回基准的最终索引 return i; } // 递归的快速排序函数 void quickSortRecursive(std::vectorint arr, int left, int right) { // 递归基区间内元素少于等于1个 if (left right) { return; } // 分区并获取基准位置 int pivotIndex partition(arr, left, right); // 递归排序基准左右两侧的子数组 quickSortRecursive(arr, left, pivotIndex - 1); quickSortRecursive(arr, pivotIndex 1, right); } // 对外的排序接口 void quickSort(std::vectorint arr) { if (arr.size() 1) return; // 空或单元素数组无需排序 // 初始化随机数种子整个排序过程一次即可 static bool seeded false; if (!seeded) { std::srand(static_castunsigned int(std::time(nullptr))); seeded true; } quickSortRecursive(arr, 0, arr.size() - 1); } // 测试函数 void runTests() { std::cout 开始测试快速排序实现...\n std::endl; std::vectorstd::vectorint tests { {}, {1}, {2, 1}, {1, 2}, {3, 3, 3}, {5, 2, 8, 1, 9}, {9, 8, 7, 6, 5, 4, 3, 2, 1}, {1, 2, 3, 4, 5}, {-5, 10, 0, -3, 8}, }; for (size_t i 0; i tests.size(); i) { std::vectorint original tests[i]; std::vectorint sortedByStd tests[i]; std::vectorint sortedByUs tests[i]; std::sort(sortedByStd.begin(), sortedByStd.end()); quickSort(sortedByUs); bool passed (sortedByUs sortedByStd); std::cout 测试用例 i 1 : [; for (size_t j 0; j original.size(); j) { std::cout original[j]; if (j ! original.size() - 1) std::cout , ; } std::cout ] ; if (passed) { std::cout 通过; } else { std::cout 失败; std::cout \n 期望: [; for (int num : sortedByStd) std::cout num ; std::cout ]; std::cout \n 实际: [; for (int num : sortedByUs) std::cout num ; std::cout ]; } std::cout std::endl; assert(passed); } // 大规模随机测试 std::cout \n进行大规模随机测试10000个元素... std::endl; const int N 10000; std::vectorint bigArray(N); for (int val : bigArray) { val std::rand() % 100000; } std::vectorint copyForStd bigArray; std::vectorint copyForUs bigArray; std::sort(copyForStd.begin(), copyForStd.end()); quickSort(copyForUs); assert(copyForStd copyForUs); std::cout 大规模测试通过 std::endl; std::cout \n所有测试均已通过快速排序实现正确。 std::endl; } int main() { runTests(); return 0; }把这个程序跑起来看到所有测试通过你才算真正完成了“C实现快速排序”这个项目。这个过程里最重要的不是背下代码而是理解每个变量为什么这么定义每个判断条件为什么这么写以及当结果不对时应该如何一步步去调试和推理。算法实现的能力就是在这样一次次“踩坑”和“填坑”中积累起来的。下次面试官让你手写快排你完全可以自信地从基准选择开始讲到分区细节再谈到优化策略这远比单纯默写一段代码要深刻得多。 C++快速排序实现详解：从原理到工程实践
1. 项目概述为什么快速排序是C程序员绕不开的坎如果你写过C或者正准备深入学习这门语言那么“快速排序”这个名字你肯定不陌生。它不仅仅是数据结构与算法课程里的一个必考知识点更是面试官手里的“常客”以及实际项目中处理大规模数据时一个高效且实用的工具。我见过太多新手一提到排序脑子里就只有std::sort这当然没问题标准库很强大。但当你被问到“std::sort底层可能用了什么”或者“手写一个O(n log n)的排序”时如果对快速排序的原理和实现一知半解场面就会很尴尬。快速排序的魅力在于它“分而治之”的智慧。它不像冒泡排序那样笨拙地两两比较也不像归并排序那样需要额外的存储空间。它的核心思想是在待排序的序列中挑选一个基准元素然后通过一趟操作将序列分成独立的两部分其中一部分的所有数据都比另一部分的所有数据要小。然后再递归地对这两部分数据分别进行快速排序整个排序过程递归进行最终使整个数据变成有序序列。这个过程听起来简单但实现起来尤其是用C这种贴近底层的语言来实现里面充满了细节和“坑”。比如基准元素怎么选递归的终止条件怎么写如何避免最坏情况下的O(n²)时间复杂度这些问题的答案直接决定了你写出来的快速排序是“玩具”还是“工业级”。所以今天我们不只满足于看懂一段代码而是要亲手用C从零实现一个健壮、高效的快速排序。我会带你拆解每一个步骤解释每一个设计决策背后的原因并分享我在实际编码和调试中积累的那些教科书上不会写的经验。无论你是正在准备面试还是想夯实自己的算法基础或者单纯想领略一下经典算法的精妙这篇内容都会让你有所收获。2. 快速排序的核心原理与设计思路拆解2.1 “分治”思想快速排序的灵魂所在快速排序的“快”根源在于它的“分治”策略。理解了这个策略就抓住了它的命脉。我们可以把排序一个长数组的任务分解成排序两个更短的子数组的任务。具体来说整个过程分为三步分解从数组中选择一个元素作为“基准”。以这个基准为界重新排列数组使得所有比基准小的元素都移到基准的左边所有比基准大的元素都移到基准的右边。这个操作结束后基准元素就处于它最终应该在的位置上。这个操作通常被称为“分区”。解决递归地对基准左边和右边的两个子数组重复进行快速排序。合并因为基准已经在正确的位置且左子数组都小于基准右子数组都大于基准所以当左右子数组都排好序后整个数组自然就有序了。这一步在快速排序中不需要任何额外的合并操作这是它比归并排序更节省空间的关键。这个递归过程会一直进行直到子数组的长度为0或1即已经有序递归才会开始返回。这种策略的效率非常高因为在理想情况下每次分区都能将数组大致平分成两半递归树的深度就是log₂n而每层需要处理的元素总数是n所以平均时间复杂度是O(n log n)。2.2 关键设计决策基准选择与分区算法原理听起来很清晰但一到实现就有两个核心问题需要决策基准怎么选分区怎么做基准选择这是影响算法性能的关键。一个糟糕的基准可能导致分区极度不平衡从而退化成O(n²)的时间复杂度。固定选择比如总是选第一个或最后一个元素。这是最朴素的方法但存在致命缺陷如果输入数组已经有序或逆序那么每次分区都只能分出一个元素基准本身算法就退化成了冒泡排序。这是新手最容易踩的坑。随机选择在待排序区间内随机选择一个元素作为基准。这种方法能有效避免因输入数据特定顺序导致的最坏情况。在数学期望上它能保证算法的平均性能。这是工程实践中最常用、也最推荐的方法。三数取中法取待排序区间头、尾、中间三个元素将其中值大小居中的那个作为基准。这是一种对“随机选择”的确定性模拟也能较好地避免最坏情况且不需要生成随机数。在我们的C实现中为了兼顾简单性和鲁棒性我会采用“随机选择”作为基准策略。分区算法这是快速排序的“发动机”负责完成重新排列的核心工作。最经典、也最易懂的是Lomuto分区方案和Hoare分区方案。Lomuto分区法思路直观代码简洁。它维护一个“小于基准”的边界索引遍历数组将小于基准的元素交换到这个边界之前。但它在大数据量下交换次数可能较多且对于所有元素都相等的数组性能会退化为O(n²)。Hoare分区法由快速排序的发明者Tony Hoare提出。它使用两个指针分别从数组两端向中间扫描交换不符合条件的元素。通常比Lomuto法更高效交换次数更少但理解和实现的细节稍微复杂一点特别是边界条件的处理。为了让第一次实现更容易理解我们先从Lomuto分区法入手因为它清晰地体现了“划分区域”的思想。在掌握了核心逻辑后我们再探讨如何优化到Hoare分区法。3. C实现快速排序的详细步骤3.1 基础框架与递归函数设计我们先搭建起快速排序的递归骨架。这个函数需要知道要对数组的哪一部分进行排序所以我们传入数组的引用以及左右边界索引左闭右闭区间。#include iostream #include vector #include cstdlib // 用于 rand() #include ctime // 用于 time() // 快速排序的递归驱动函数 void quickSort(std::vectorint arr, int left, int right) { // 递归终止条件当子数组只有一个或没有元素时无需排序 if (left right) { return; } // 关键步骤1进行分区操作并获取基准元素的最终位置 int pivotIndex partition(arr, left, right); // 关键步骤2递归排序基准左边的子数组 quickSort(arr, left, pivotIndex - 1); // 关键步骤3递归排序基准右边的子数组 quickSort(arr, pivotIndex 1, right); } // 对外提供的排序接口简化调用 void quickSort(std::vectorint arr) { if (arr.empty()) return; // 初始化随机数种子用于后续随机选择基准 std::srand(static_castunsigned int(std::time(nullptr))); quickSort(arr, 0, arr.size() - 1); }代码解析与注意事项递归终止条件if (left right)这是递归的“安全阀”。当left right时区间只有一个元素当left right时区间为空比如基准是第一个元素那么左子区间的left, pivotIndex-1就会变成0, -1。没有这个条件递归将无限进行下去。随机数种子初始化我们在公开接口quickSort(arr)中初始化随机种子。切忌在递归函数quickSort(arr, left, right)内部每次调用都初始化种子这不仅没必要而且如果基于时间播种在极短时间内连续调用rand()可能会得到相同或相近的随机数序列。函数重载我们提供了两个quickSort函数。一个是对外的简单接口另一个是内部递归函数。这是一种清晰的封装方式。3.2 Lomuto分区法的实现与逐行解析现在我们来实现最核心的partition函数。这里我们采用随机选择基准的Lomuto分区法。// Lomuto分区方案 int partition(std::vectorint arr, int left, int right) { // 1. 随机选择基准元素并将其交换到当前区间的末尾right位置 // 生成一个在[left, right]范围内的随机索引 int randomIndex left std::rand() % (right - left 1); // 将随机选中的基准值交换到最右边方便后续操作 std::swap(arr[randomIndex], arr[right]); int pivot arr[right]; // 现在基准值在arr[right] // 2. 初始化“小于基准区域”的边界。i指向这个区域最后一个元素的下一个位置。 // 初始时这个区域为空所以i从left开始。 int i left; // 3. 遍历数组从left到right-1因为right是基准 for (int j left; j right; j) { // 如果当前元素arr[j]小于基准值pivot if (arr[j] pivot) { // 将arr[j]这个小于基准的元素交换到“小于基准区域”的末尾i的位置 std::swap(arr[i], arr[j]); // 将“小于基准区域”的边界向右移动一位 i; } // 如果arr[j] pivot则不做任何操作j继续向后走。 // 这些大于等于基准的元素自然就被留在了后面。 } // 4. 循环结束后所有小于pivot的元素都在区间[left, i-1]中。 // 所有大于等于pivot的元素都在区间[i, right-1]中。 // 此时arr[right]仍然是基准值pivot。 // 我们需要将基准值交换到它正确的位置也就是i的位置。 // 因为arr[i]是第一个大于等于pivot的元素或者iright交换后 // arr[i]现在的基准值左边的都小于它右边的都大于等于它。 std::swap(arr[i], arr[right]); // 5. 返回基准值的最终位置i return i; }分区过程可视化举例 假设数组arr [3, 7, 8, 5, 2, 1, 9, 4]left0,right7。随机选择基准假设选中arr[2]8将其与arr[7]4交换。数组变为[3, 7, 4, 5, 2, 1, 9, 8]pivot8。初始化i0j从0开始遍历到6。j0:arr[0]3 8交换arr[i]和arr[j]自己和自己交换i-i1。数组不变。j1:arr[1]7 8交换arr[1]和arr[1]i-i2。j2:arr[2]4 8交换arr[2]和arr[2]i-i3。j3:arr[3]5 8交换arr[3]和arr[3]i-i4。j4:arr[4]2 8交换arr[4]和arr[4]i-i5。j5:arr[5]1 8交换arr[5]和arr[5]i-i6。j6:arr[6]9 8不做任何操作。循环结束。此时i6。交换arr[i]和arr[right]即交换arr[6]9和arr[7]8。数组变为[3, 7, 4, 5, 2, 1, 8, 9]。返回pivotIndex i 6。可以看到arr[6]8左边的元素都小于8右边的元素arr[7]9大于8。注意Lomuto分区法的潜在问题当数组中存在大量与基准值相等的元素时if (arr[j] pivot)这个条件会导致这些相等元素都被划到右边大于等于区域。如果基准值恰好选到了这些重复值中的一个可能会导致分区不平衡。一个改进方法是使用“三路快速排序”将数组分为“小于”、“等于”、“大于”三部分这对于包含大量重复元素的数组效率更高。3.3 优化方向Hoare分区法与工程实践技巧掌握了基础的Lomuto分区法后我们可以看看更高效的Hoare分区法并了解一些工程上的优化技巧。Hoare分区法实现// Hoare分区方案 int partitionHoare(std::vectorint arr, int left, int right) { // 随机选择基准并交换到左边也可以不交换这里选择交换到左边作为初始基准值 int randomIndex left std::rand() % (right - left 1); std::swap(arr[randomIndex], arr[left]); int pivot arr[left]; int i left - 1; // 左指针从最左边前一位开始 int j right 1; // 右指针从最右边后一位开始 while (true) { // 从左向右找到第一个大于等于pivot的元素 do { i; } while (arr[i] pivot); // 注意这里用 不是 // 从右向左找到第一个小于等于pivot的元素 do { --j; } while (arr[j] pivot); // 注意这里用 不是 // 如果左右指针相遇或交错说明分区完成 if (i j) { return j; // 注意返回的是 j不是 i这是Hoare分区法的关键。 } // 交换这两个不符合各自区域条件的元素 std::swap(arr[i], arr[j]); // 交换后arr[i] pivot, arr[j] pivot循环继续 } } // 对应的递归函数需要稍作调整 void quickSortHoare(std::vectorint arr, int left, int right) { if (left right) return; int p partitionHoare(arr, left, right); // 注意区间划分 [left, p] 和 [p1, right] quickSortHoare(arr, left, p); quickSortHoare(arr, p 1, right); }Hoare分区法要点它返回的索引j通常不是基准值的最终位置而是分区后左子数组的右边界。基准值可能在左子数组的末尾也可能在右子数组的开头但整个数组已经被正确划分。循环内部的while条件用的是和而不是和这避免了在元素相等时的无意义交换和指针停滞但也意味着等于基准的元素也会被交换这有助于在重复元素多时平衡分区。Hoare法通常比Lomuto法执行更少的交换操作因此性能稍好。工程优化技巧小数组切换插入排序当递归到子数组规模很小比如长度小于10时快速排序的递归开销可能比排序本身还大。一个常见的优化是当right - left 某个阈值时改用简单的插入排序来处理这个小片段。插入排序对小规模、近乎有序的数据效率很高。尾递归优化观察递归调用quickSort(arr, pivotIndex 1, right)这是函数最后一步操作称为尾递归。编译器可以对其进行优化使其不增加新的调用栈深度从而避免在极端情况下如不平衡分区的栈溢出风险。我们可以手动优化先对较短的子数组进行递归较长的子数组通过循环迭代来处理。void quickSortTailOpt(std::vectorint arr, int left, int right) { while (left right) { // 用循环代替一部分递归 int pivotIndex partition(arr, left, right); // 先递归排序较短的那部分 if (pivotIndex - left right - pivotIndex) { quickSortTailOpt(arr, left, pivotIndex - 1); left pivotIndex 1; // 更新左边界循环处理长的那部分 } else { quickSortTailOpt(arr, pivotIndex 1, right); right pivotIndex - 1; // 更新右边界循环处理长的那部分 } } }三数取中法选择基准为了避免随机数生成的性能开销虽然很小可以使用确定性的“三数取中法”来选取基准通常也能获得很好的效果。4. 测试、常见问题与性能分析4.1 如何全面测试你的快速排序实现写完代码只是第一步严谨的测试才能保证其正确性和鲁棒性。你需要构建一个全面的测试集#include iostream #include vector #include algorithm // 用于 std::is_sorted 和 std::sort #include cassert void testQuickSort() { // 测试用例集合 std::vectorstd::vectorint testCases { {}, // 空数组 {1}, // 单元素数组 {2, 1}, // 两个元素逆序 {1, 2, 3, 4, 5}, // 已排序数组 {5, 4, 3, 2, 1}, // 逆序数组 {3, 1, 4, 1, 5, 9, 2, 6}, // 典型无序数组 {5, 5, 5, 5, 5}, // 所有元素相同 {-10, 0, 100, -5, 7}, // 包含负数和零 // 可以添加更大规模的随机数组测试 }; for (auto testArr : testCases) { std::vectorint arrCopy testArr; // 拷贝一份用于我们的排序 std::vectorint expected testArr; // 拷贝一份用于标准库排序 // 使用标准库排序得到正确结果 std::sort(expected.begin(), expected.end()); // 使用我们实现的快速排序 quickSort(arrCopy); // 验证结果 if (arrCopy ! expected) { std::cerr 测试失败输入; for (int num : testArr) std::cerr num ; std::cerr \n期望; for (int num : expected) std::cerr num ; std::cerr \n实际; for (int num : arrCopy) std::cerr num ; std::cerr std::endl; assert(false); // 触发断言方便调试 } else { // 也可以使用 std::is_sorted 检查 assert(std::is_sorted(arrCopy.begin(), arrCopy.end())); } } std::cout 所有基础测试用例通过 std::endl; // 压力测试大规模随机数组 const int SIZE 10000; std::vectorint largeArr(SIZE); for (int num : largeArr) { num std::rand() % 100000; } std::vectorint largeArrCopy largeArr; std::sort(largeArr.begin(), largeArr.end()); quickSort(largeArrCopy); assert(largeArr largeArrCopy); std::cout 大规模随机测试 SIZE 个元素通过 std::endl; } int main() { std::srand(static_castunsigned int(std::time(nullptr))); testQuickSort(); return 0; }4.2 常见问题与调试技巧实录在实现快速排序时以下几个问题非常常见栈溢出如果数组非常大且分区极度不平衡例如总是选到最小或最大的元素作为基准递归深度可能达到n导致调用栈溢出。解决方案使用随机化基准选择或采用尾递归优化、小数组切换插入排序等策略。死循环在分区函数中指针移动的逻辑错误可能导致无限循环。特别是在Hoare分区法中do...while循环的边界条件和终止条件i j必须非常小心。调试技巧在分区函数内打印left,right,i,j和数组状态观察指针移动是否符合预期。对于小数组如3个元素进行单步调试非常有效。排序结果不正确通常是分区后递归区间划分错误。Lomuto法递归区间应为[left, pivotIndex-1]和[pivotIndex1, right]。pivotIndex是基准的最终位置它已经排好不应再参与递归。Hoare法递归区间应为[left, p]和[p1, right]。注意返回的p不是基准位置而是分区边界。一个经典的错误是误以为p是基准位置而错误划分区间导致元素丢失或重复排序。对重复元素处理不佳如前所述基础的Lomuto法在重复元素多时性能下降。解决方案考虑实现“三路快速排序”它将数组分为“小于基准”、“等于基准”、“大于基准”三部分递归时只对“小于”和“大于”部分进行能高效处理重复元素。随机数种子问题如果在递归函数内频繁调用srand(time(nullptr))由于time函数秒级精度在同一秒内产生的随机数序列可能相同导致基准选择不“随机”。正确做法在整个排序过程开始前只初始化一次随机种子。4.3 性能分析与对比我们来简单分析一下我们实现的快速排序的性能时间复杂度平均情况 O(n log n)每次分区大致将数组平分递归树深度为log n每层处理O(n)个元素。最坏情况 O(n²)每次分区都极度不平衡例如数组已有序且总选到最值作为基准。通过随机化基准可以将最坏情况出现的概率降到极低从“必然”变为“偶然”这是随机化算法的一大优势。最好情况 O(n log n)每次分区都完美平分。空间复杂度主要消耗在递归调用栈。平均情况下深度为O(log n)因此平均空间复杂度为O(log n)。最坏情况下深度为O(n)。我们的实现是“原地排序”除了递归栈和少量临时变量不需要额外的、与n成比例的存储空间。稳定性快速排序不是稳定的排序算法。在分区过程中相等的元素可能会因为交换而改变相对次序。如果需要稳定性应考虑归并排序。与std::sort的对比 C标准库的std::sort是一个混合排序算法通常基于IntroSort内省排序。它结合了快速排序、堆排序和插入排序的优点主体使用快速排序。当递归深度超过一定阈值约为2*log₂n时可能意味着遇到了接近最坏情况此时切换到堆排序保证O(n log n)最坏时间复杂度。当子数组规模很小时切换为插入排序常数因子小。 因此std::sort在绝大多数情况下都非常高效且鲁棒是我们日常编程的首选。我们手写快速排序的目的是为了深入理解算法原理锻炼编码和调试能力而不是为了替代标准库。5. 从理论到实践一个完整的可运行示例最后让我们将所有代码整合在一起形成一个完整的、带有详细注释和测试的C文件。你可以直接复制这段代码到你的IDE如VS Code、CLion等中编译运行观察结果。#include iostream #include vector #include cstdlib #include ctime #include algorithm #include cassert // 使用随机基准的Lomuto分区法 int partition(std::vectorint arr, int left, int right) { // 1. 随机选择基准并交换到末尾 int randomIndex left std::rand() % (right - left 1); std::swap(arr[randomIndex], arr[right]); int pivot arr[right]; // 2. 初始化小于基准区域的边界 int i left; // i 指向小于基准区域的末尾的下一个位置 // 3. 遍历数组不包括基准 for (int j left; j right; j) { if (arr[j] pivot) { std::swap(arr[i], arr[j]); i; // 扩大小于基准的区域 } } // 4. 将基准放到正确位置 std::swap(arr[i], arr[right]); // 5. 返回基准的最终索引 return i; } // 递归的快速排序函数 void quickSortRecursive(std::vectorint arr, int left, int right) { // 递归基区间内元素少于等于1个 if (left right) { return; } // 分区并获取基准位置 int pivotIndex partition(arr, left, right); // 递归排序基准左右两侧的子数组 quickSortRecursive(arr, left, pivotIndex - 1); quickSortRecursive(arr, pivotIndex 1, right); } // 对外的排序接口 void quickSort(std::vectorint arr) { if (arr.size() 1) return; // 空或单元素数组无需排序 // 初始化随机数种子整个排序过程一次即可 static bool seeded false; if (!seeded) { std::srand(static_castunsigned int(std::time(nullptr))); seeded true; } quickSortRecursive(arr, 0, arr.size() - 1); } // 测试函数 void runTests() { std::cout 开始测试快速排序实现...\n std::endl; std::vectorstd::vectorint tests { {}, {1}, {2, 1}, {1, 2}, {3, 3, 3}, {5, 2, 8, 1, 9}, {9, 8, 7, 6, 5, 4, 3, 2, 1}, {1, 2, 3, 4, 5}, {-5, 10, 0, -3, 8}, }; for (size_t i 0; i tests.size(); i) { std::vectorint original tests[i]; std::vectorint sortedByStd tests[i]; std::vectorint sortedByUs tests[i]; std::sort(sortedByStd.begin(), sortedByStd.end()); quickSort(sortedByUs); bool passed (sortedByUs sortedByStd); std::cout 测试用例 i 1 : [; for (size_t j 0; j original.size(); j) { std::cout original[j]; if (j ! original.size() - 1) std::cout , ; } std::cout ] ; if (passed) { std::cout 通过; } else { std::cout 失败; std::cout \n 期望: [; for (int num : sortedByStd) std::cout num ; std::cout ]; std::cout \n 实际: [; for (int num : sortedByUs) std::cout num ; std::cout ]; } std::cout std::endl; assert(passed); } // 大规模随机测试 std::cout \n进行大规模随机测试10000个元素... std::endl; const int N 10000; std::vectorint bigArray(N); for (int val : bigArray) { val std::rand() % 100000; } std::vectorint copyForStd bigArray; std::vectorint copyForUs bigArray; std::sort(copyForStd.begin(), copyForStd.end()); quickSort(copyForUs); assert(copyForStd copyForUs); std::cout 大规模测试通过 std::endl; std::cout \n所有测试均已通过快速排序实现正确。 std::endl; } int main() { runTests(); return 0; }把这个程序跑起来看到所有测试通过你才算真正完成了“C实现快速排序”这个项目。这个过程里最重要的不是背下代码而是理解每个变量为什么这么定义每个判断条件为什么这么写以及当结果不对时应该如何一步步去调试和推理。算法实现的能力就是在这样一次次“踩坑”和“填坑”中积累起来的。下次面试官让你手写快排你完全可以自信地从基准选择开始讲到分区细节再谈到优化策略这远比单纯默写一段代码要深刻得多。