1. 从“分而治之”到“原地排序”快速排序的核心思想如果你写过C语言排序算法是绕不开的一道坎。冒泡排序简单但慢归并排序稳定但需要额外空间。有没有一种算法既能在平均情况下跑得飞快又能像冒泡排序一样“原地”操作不占用太多额外内存呢这就是我们今天要拆解的快速排序。它不是什么新潮的技术但绝对是每个C程序员工具箱里最锋利、最常用的一把刀。我见过太多新手一上来就被它的“递归”和“分区”吓退或者写出来的代码在特定数据下性能暴跌。这篇文章我就结合自己十多年写C、调性能的经验把快速排序从原理到代码再到那些教科书上不会写的“坑”和“优化技巧”给你掰开揉碎了讲清楚。简单说快速排序干的就是一件事在一个无序数组中选一个基准值然后把所有比它小的扔到它左边所有比它大的扔到它右边。这个过程完成后这个基准值就处在了它最终排序后应该在的正确位置。然后对它的左半部分和右半部分递归地重复这个过程直到每个部分只剩下一个元素整个数组自然就有序了。这个“选基准、分区、递归”的思路就是“分而治之”策略的经典体现。它的平均时间复杂度是 O(n log n)最坏情况比如数组已经有序会退化到 O(n²)但通过一些技巧可以极大避免。更重要的是它是一种原地排序算法空间复杂度主要来自递归调用栈理想情况下是 O(log n)。2. 庖丁解牛分区过程的三种主流实现理解了核心思想最关键、也最考验编程功力的部分就是“分区”了。怎么高效地把数组分成“小值区”和“大值区”这里我介绍三种最经典的分区方法每一种都有其适用场景和微妙的细节。2.1 Lomuto分区法最直观易懂的实现Lomuto分区法可能是教科书上最常见的一种思路非常直白。我们通常选择数组最右边的元素作为基准值pivot。然后维护一个索引i它指向“小于基准值区域”的末尾。接着我们用另一个索引j从左到右遍历数组除了最后一个基准值。遍历过程中如果arr[j]小于基准值我们就交换arr[i]和arr[j]然后让i向后移动一位。这样i左边的所有元素都保证小于基准值。遍历完成后i的位置就是基准值最终应该待的地方因为i左边都小右边都大或等于所以我们交换arr[i]和最右边的基准值。最后返回i这个分区点。// Lomuto 分区函数 int partition_lomuto(int arr[], int low, int high) { int pivot arr[high]; // 选择最右侧元素作为基准 int i low - 1; // 小于pivot区域的边界 for (int j low; j high; j) { // 如果当前元素小于等于基准将其交换到小值区 if (arr[j] pivot) { i; // 交换 arr[i] 和 arr[j] int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } // 将基准值放到正确位置 int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1; // 返回基准值的最终位置 }注意Lomuto法的代码简洁容易理解这是它的最大优点。但它有一个明显的缺点当数组中存在大量与基准值相等的元素时它仍然会进行交换导致不必要的操作。并且它通常需要更多的交换次数。2.2 Hoare分区法原始且更高效的选择这是快速排序发明者Tony Hoare最初提出的方法通常比Lomuto法更快因为它进行的交换次数更少。它的思路是从数组的两头向中间扫描。我们选择数组中间的元素作为基准值当然也可以选第一个。然后设置两个指针left指向起始前一位right指向末尾后一位。在一个无限循环中我们让left向右移动直到找到一个大于等于基准值的元素再让right向左移动直到找到一个小于等于基准值的元素。如果此时两个指针相遇或交错就跳出循环否则交换这两个元素继续循环。循环结束后返回right指针的位置作为分区点。// Hoare 分区函数 int partition_hoare(int arr[], int low, int high) { int pivot arr[(low high) / 2]; // 选择中间元素作为基准 int left low - 1; int right high 1; while (1) { // 从左向右找第一个大于等于pivot的元素 do { left; } while (arr[left] pivot); // 从右向左找第一个小于等于pivot的元素 do { right--; } while (arr[right] pivot); // 如果指针相遇或交错分区结束 if (left right) { return right; // 注意这里返回的是right不是left } // 交换左右指针所指向的不合规元素 int temp arr[left]; arr[left] arr[right]; arr[right] temp; } }关键点Hoare分区法返回的right索引其左边的元素都小于等于基准值右边的元素都大于等于基准值。但请注意这个right位置上的元素并不一定是基准值本身基准值可能位于分区的任何位置。这是与Lomuto法一个重要的概念区别也影响了递归调用的边界。2.3 双指针挖坑法另一种直观的原地操作这种方法在国内的教程里也很常见形象地称为“挖坑填数”。它同样选择第一个元素作为基准值挖一个“坑”然后从数组两端开始遍历。具体步骤是首先保存基准值pivot arr[low]此时low位置就是一个“坑”。然后从high指针开始向左移动找到第一个小于pivot的数将其填入low指向的“坑”此时high位置变成新“坑”。接着从low指针开始向右移动找到第一个大于pivot的数将其填入high指向的“坑”此时low位置又变成新“坑”。如此交替进行直到low和high指针相遇相遇点就是一个“坑”最后将最初的pivot值填入这个坑中。相遇点就是分区位置。// 挖坑法分区函数 int partition_hole(int arr[], int low, int high) { int pivot arr[low]; // 挖第一个坑 while (low high) { // 从右向左找小于pivot的数来填low位置的坑 while (low high arr[high] pivot) { high--; } if (low high) { arr[low] arr[high]; // 将high的值填到low的坑 low; // low向右移此时high位置成为新坑 } // 从左向右找大于pivot的数来填high位置的坑 while (low high arr[low] pivot) { low; } if (low high) { arr[high] arr[low]; // 将low的值填到high的坑 high--; // high向左移此时low位置成为新坑 } } // 当lowhigh时循环结束此位置即为基准值的最终位置 arr[low] pivot; return low; }这种方法代码也相对清晰并且是严格的原地交换通过赋值而非三次交换。它和Hoare法一样在处理重复元素时效率较高。3. 递归的骨架与边界陷阱写出健壮的快速排序有了分区函数递归主体就相对简单了。但这里恰恰是新手最容易出错的地方——递归边界。处理不好就是无限递归或者栈溢出。3.1 基于Lomuto分区的递归实现我们先看配合Lomuto分区的递归怎么写。因为Lomuto分区返回的pivot_index是基准值的确切位置这个位置上的元素已经排好所以递归时应该排除它。void quick_sort_lomuto(int arr[], int low, int high) { // 递归终止条件子数组只有一个或零个元素 if (low high) { // 对数组进行分区获取基准位置 int pivot_index partition_lomuto(arr, low, high); // 递归排序基准左侧和右侧的子数组 // 注意基准元素本身pivot_index不再参与排序 quick_sort_lomuto(arr, low, pivot_index - 1); quick_sort_lomuto(arr, pivot_index 1, high); } }这里的边界条件if (low high)是精髓。当low high时意味着当前区间没有元素low high或只有一个元素low high这两种情况都不需要排序直接返回。这是保证递归能够正确结束的关键。3.2 基于Hoare分区的递归实现边界处理的差异由于Hoare分区返回的right索引我们记为pivot_index并不一定是基准值的位置其左侧是 pivot的区域右侧是 pivot的区域。因此递归的划分方式有所不同。一种常见且正确的做法是将数组划分为[low, pivot_index]和[pivot_index 1, high]两部分。注意第一部分包含了pivot_index这个位置。void quick_sort_hoare(int arr[], int low, int high) { if (low high) { int pivot_index partition_hoare(arr, low, high); // 递归排序左半部分 [low, pivot_index] quick_sort_hoare(arr, low, pivot_index); // 递归排序右半部分 [pivot_index 1, high] quick_sort_hoare(arr, pivot_index 1, high); } }为什么可以这样划分因为partition_hoare结束后我们能保证[low, pivot_index]中的所有元素都基准值集合[pivot_index1, high]中的所有元素都基准值集合。这样递归下去最终也能使数组有序。千万不要把Hoare分区返回的索引当作基准值位置然后去排[low, pivot_index-1]和[pivot_index1, high]这很可能导致错误或无限递归。3.3 递归深度与栈溢出风险快速排序的递归调用栈深度在平均情况下是 O(log n)但在最坏情况下比如数组已有序且总是选择最边上的元素作为基准会达到 O(n)。对于一个百万级别的数组这可能导致栈溢出。一个实用的缓解策略是尾递归优化。观察递归代码两次递归调用是顺序执行的。我们可以对其中一部分进行尾递归优化编译器可能会将其转化为循环减少一层栈帧的使用。// 使用尾递归优化的快速排序 (以Lomuto为例) void quick_sort_tail_recursion(int arr[], int low, int high) { while (low high) { int pivot_index partition_lomuto(arr, low, high); // 总是先递归处理较短的那部分 if (pivot_index - low high - pivot_index) { quick_sort_tail_recursion(arr, low, pivot_index - 1); low pivot_index 1; // 更新low将大区间转为循环处理 } else { quick_sort_tail_recursion(arr, pivot_index 1, high); high pivot_index - 1; // 更新high将大区间转为循环处理 } } }这个技巧的核心是总是先对较小的子数组进行递归调用然后通过更新参数low或high将较大的子数组交给下一次循环迭代处理。这保证了递归栈的深度最多为 O(log n)有效避免了最坏情况下的栈溢出风险。在实际生产代码中这是一个非常值得采用的优化。4. 性能调优与实战避坑指南理论上的平均 O(n log n) 很美但掉到最坏 O(n²) 的坑里也很惨。下面这些技巧能帮你把快速排序的性能稳定在高效区间。4.1 基准值选择的艺术三数取中法选择第一个或最后一个元素作为基准在面对已排序或逆序数组时会创造最坏情况。随机选择基准是一个好方法但C语言标准库的rand()函数本身也有开销。一个简单而高效的折中方案是三数取中法。它的思想是取数组头、尾、中间三个元素将这三个元素的中位数作为基准值。这样选出来的基准值大概率能避免极端情况将数组划分得比较均衡。// 三数取中法选择基准值索引 int median_of_three(int arr[], int low, int high) { int mid low (high - low) / 2; // 对arr[low], arr[mid], arr[high]进行排序取中间值 if (arr[low] arr[mid]) { int temp arr[low]; arr[low] arr[mid]; arr[mid] temp; } if (arr[low] arr[high]) { int temp arr[low]; arr[low] arr[high]; arr[high] temp; } if (arr[mid] arr[high]) { int temp arr[mid]; arr[mid] arr[high]; arr[high] temp; } // 此时 arr[low] arr[mid] arr[high] // 我们将中位数 arr[mid] 交换到 high-1 的位置对于Lomuto法或直接作为基准 int temp arr[mid]; arr[mid] arr[high-1]; arr[high-1] temp; return high-1; // 返回中位数的索引 } // 使用三数取中法的Lomuto分区 int partition_lomuto_median(int arr[], int low, int high) { // 获取中位数索引并将其交换到high位置Lomuto法要求基准在high int median_idx median_of_three(arr, low, high); int temp arr[median_idx]; arr[median_idx] arr[high]; arr[high] temp; // 剩下的部分与标准Lomuto分区相同 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; } } temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1; }这个小技巧能极大地提升算法对有序、逆序、或部分有序数据的处理性能成本却很低。4.2 处理小数组切换到插入排序递归是有开销的。当子数组变得很小时比如长度小于10快速排序递归调用的开销可能比排序本身还大。一个经典的优化是当区间长度小于某个阈值时切换到插入排序。因为插入排序在小规模数据上非常高效且是稳定排序。#define INSERTION_SORT_THRESHOLD 10 void insertion_sort(int arr[], int low, int high) { for (int i low 1; i high; i) { int key arr[i]; int j i - 1; while (j low arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } } void quick_sort_optimized(int arr[], int low, int high) { // 如果区间长度小于阈值使用插入排序 if (high - low 1 INSERTION_SORT_THRESHOLD) { insertion_sort(arr, low, high); return; } // 否则使用快速排序 if (low high) { int pivot_index partition_lomuto_median(arr, low, high); // 使用优化后的分区 quick_sort_optimized(arr, low, pivot_index - 1); quick_sort_optimized(arr, pivot_index 1, high); } }这个INSERTION_SORT_THRESHOLD值通常在7到50之间可以通过测试确定一个对当前环境最优的值。这个优化通常能带来10%-20%的整体性能提升。4.3 处理大量重复元素三路划分标准的快速排序包括上述所有方法在遇到大量重复元素时性能会下降因为重复元素会被无谓地来回交换或导致分区不平衡。三路快速排序专门解决这个问题。它将数组划分为三部分[小于pivot][等于pivot][大于pivot]。这样所有等于基准值的元素在一次分区后就全部就位后续递归只处理小于和大于的部分效率更高。// 三路划分的快速排序 void quick_sort_three_way(int arr[], int low, int high) { if (low high) return; // 初始化三个指针 // lt: 小于pivot区域的右边界 (arr[low..lt-1] pivot) // gt: 大于pivot区域的左边界 (arr[gt1..high] pivot) // i: 当前遍历的指针 int pivot arr[low]; // 可以选择更优的基准选择策略 int lt low; int gt high; int i low 1; while (i gt) { if (arr[i] pivot) { // 当前元素小于pivot交换到lt区域 int temp arr[lt]; arr[lt] arr[i]; arr[i] temp; lt; i; } else if (arr[i] pivot) { // 当前元素大于pivot交换到gt区域 int temp arr[i]; arr[i] arr[gt]; arr[gt] temp; gt--; // 注意这里i不递增因为从gt交换过来的元素还未检查 } else { // 当前元素等于pivot直接跳过 i; } } // 循环结束后数组被划分为三部分 // arr[low..lt-1] pivot // arr[lt..gt] pivot (已就位) // arr[gt1..high] pivot // 递归排序小于和大于的部分 quick_sort_three_way(arr, low, lt - 1); quick_sort_three_way(arr, gt 1, high); }如果你的数据中重复项很多三路划分是必须考虑的优化。它也是许多语言标准库如Java的Arrays.sort()对于基本类型内部采用的策略。5. 完整可运行的代码示例与测试纸上得来终觉浅我们把这些知识点整合成一个完整的、经过优化的C语言快速排序实现并附上测试用例。#include stdio.h #include stdlib.h #include time.h #define INSERTION_SORT_THRESHOLD 10 #define ARRAY_SIZE 20 // 插入排序 (用于小数组优化) void insertion_sort(int arr[], int low, int high) { for (int i low 1; i high; i) { int key arr[i]; int j i - 1; while (j low arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } } // 三数取中法并将中位数交换到high位置 int median_of_three(int arr[], int low, int high) { int mid low (high - low) / 2; // 排序 arr[low], arr[mid], arr[high] if (arr[low] arr[mid]) { int temp arr[low]; arr[low] arr[mid]; arr[mid] temp; } if (arr[low] arr[high]) { int temp arr[low]; arr[low] arr[high]; arr[high] temp; } if (arr[mid] arr[high]) { int temp arr[mid]; arr[mid] arr[high]; arr[high] temp; } // 将中位数 arr[mid] 交换到 high-1 位置为Lomuto分区准备 int temp arr[mid]; arr[mid] arr[high-1]; arr[high-1] temp; return high-1; } // 优化的Lomuto分区函数使用三数取中 int partition_optimized(int arr[], int low, int high) { // 对于小数组三数取中可能不适用这里加个判断 if (high - low 1) { int median_idx median_of_three(arr, low, high); // 将中位数交换到high位置Lomuto分区要求基准在末尾 int temp arr[median_idx]; arr[median_idx] arr[high]; arr[high] temp; } int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1; } // 最终的优化版快速排序 void quick_sort_final(int arr[], int low, int high) { // 使用尾递归优化的结构 while (low high) { // 小数组优化 if (high - low 1 INSERTION_SORT_THRESHOLD) { insertion_sort(arr, low, high); break; // 排序完成退出循环 } int pivot_index partition_optimized(arr, low, high); // 尾递归优化先处理较短的子数组 if (pivot_index - low high - pivot_index) { quick_sort_final(arr, low, pivot_index - 1); low pivot_index 1; // 将长区间留给下一次循环迭代 } else { quick_sort_final(arr, pivot_index 1, high); high pivot_index - 1; } } } // 打印数组 void print_array(int arr[], int size) { for (int i 0; i size; i) { printf(%d , arr[i]); } printf(\n); } // 测试函数 int main() { // 设置随机种子 srand(time(NULL)); int arr[ARRAY_SIZE]; printf(原始数组: ); for (int i 0; i ARRAY_SIZE; i) { arr[i] rand() % 100; // 生成0-99的随机数 printf(%d , arr[i]); } printf(\n); // 测试优化后的快速排序 quick_sort_final(arr, 0, ARRAY_SIZE - 1); printf(排序后数组: ); print_array(arr, ARRAY_SIZE); // 验证排序结果 int sorted 1; for (int i 1; i ARRAY_SIZE; i) { if (arr[i] arr[i - 1]) { sorted 0; break; } } if (sorted) { printf(排序验证成功\n); } else { printf(排序验证失败\n); } // 额外测试大量重复元素 printf(\n--- 测试大量重复元素 ---\n); int arr_dup[] {5, 3, 5, 1, 5, 8, 5, 2, 5, 7}; int size_dup sizeof(arr_dup) / sizeof(arr_dup[0]); printf(原始数组: ); print_array(arr_dup, size_dup); quick_sort_final(arr_dup, 0, size_dup - 1); printf(排序后数组: ); print_array(arr_dup, size_dup); return 0; }把这段代码复制到你的编译器里运行一下看看效果。它集成了我们讨论的多个优化点三数取中法选择基准、小数组切换插入排序、尾递归优化。虽然代码比最基础的版本长但在处理各种真实数据时其稳定性和效率要高得多。6. 快速排序的变体与工程实践思考在实际的工程开发中我们很少需要从零开始手写一个排序算法因为标准库如C的qsort已经经过了千锤百炼的优化。但理解快速排序绝不仅仅是为了应付面试或作业。6.1 标准库中的qsortC语言标准库stdlib.h中的qsort函数就是一个基于快速排序的实现虽然标准并未规定其具体实现但主流实现都是快速排序的变体。它的原型是void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));base: 指向待排序数组的指针。nitems: 数组中元素的个数。size: 每个元素的大小字节数。compar: 比较函数指针用于定义排序规则。qsort的强大之处在于它的通用性通过void*指针和用户自定义的比较函数可以对任何类型的数据进行排序。其内部实现通常包含了我们上面讨论的所有优化随机化基准、小数组切换插入排序、三数取中等。自己手写快速排序的练习能让你在使用qsort时更加得心应手尤其是在编写自定义比较函数时能深刻理解其回调机制。6.2 何时选择或不选择快速排序虽然快速排序综合性能优秀但它并非银弹。选择排序算法时需要考虑数据规模对于非常小的数组如10个元素简单的插入排序或选择排序可能更快。数据状态如果数据基本有序使用随机化或三数取中优化的快速排序仍然很快。但如果完全有序且使用最左/最右为基准的朴素版本性能会灾难性下降。如果数据中重复项极多三路快速排序是更好的选择。稳定性要求快速排序是不稳定排序即相等元素的相对位置可能改变。如果业务逻辑要求排序稳定应选择归并排序。内存限制快速排序是原地排序空间复杂度O(log n)。而归并排序需要O(n)的额外空间。在内存极度受限的嵌入式环境中这一点至关重要。最坏情况保证快速排序无法保证最坏情况时间复杂度。如果系统要求绝对的时间上限实时系统堆排序O(n log n)最坏情况或归并排序可能更合适。6.3 调试与性能分析技巧自己实现快速排序时调试可能会有点棘手因为递归和数组下标容易出错。打印日志法在分区函数和递归函数的开头打印当前的low,high,pivot值以及数组状态。这能帮你直观看到递归树和分区过程。单元测试编写针对不同情况的测试用例空数组、单元素数组、已排序数组、逆序数组、全等数组、随机大数组。确保你的算法都能正确处理。性能对比使用clock()函数计算排序时间与标准库的qsort进行对比。这不仅能验证正确性还能直观感受优化带来的收益。Valgrind检查使用 Valgrind 等工具检查是否有数组越界访问这对于处理边界条件的代码至关重要。快速排序的优雅在于其思想而它的实用价值则隐藏在无数的细节优化之中。从理解分区原理到处理递归边界再到引入各种优化策略对抗最坏情况这个过程本身就是对编程思维和工程能力的一次绝佳训练。下次当你需要排序时或许会直接调用qsort但希望你能想起它背后这个精巧而强大的算法以及为了让它稳定高效运行所付出的那些思考。
![[GESP202606 四级] 扫雷](http://pic.xiahunao.cn/yaotu/[GESP202606 四级] 扫雷)
