C语言快速排序算法详解：从核心原理到工程优化实践

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位置成为新坑 } } // 当low==high时，循环结束，此位置即为基准值的最终位置 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_index+1, high]中的所有元素都>=基准值集合。这样递归下去，最终也能使数组有序。千万不要把Hoare分区返回的索引当作基准值位置，然后去排[low, pivot_index-1]和[pivot_index+1, 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[gt+1..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[gt+1..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 标准库中的qsort

C语言标准库<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 调试与性能分析技巧

自己实现快速排序时，调试可能会有点棘手，因为递归和数组下标容易出错。

1. 打印日志法：在分区函数和递归函数的开头，打印当前的low,high,pivot值以及数组状态。这能帮你直观看到递归树和分区过程。
2. 单元测试：编写针对不同情况的测试用例：空数组、单元素数组、已排序数组、逆序数组、全等数组、随机大数组。确保你的算法都能正确处理。
3. 性能对比：使用clock()函数计算排序时间，与标准库的qsort进行对比。这不仅能验证正确性，还能直观感受优化带来的收益。
4. Valgrind检查：使用 Valgrind 等工具检查是否有数组越界访问，这对于处理边界条件的代码至关重要。

快速排序的优雅在于其思想，而它的实用价值则隐藏在无数的细节优化之中。从理解分区原理，到处理递归边界，再到引入各种优化策略对抗最坏情况，这个过程本身就是对编程思维和工程能力的一次绝佳训练。下次当你需要排序时，或许会直接调用qsort，但希望你能想起它背后这个精巧而强大的算法，以及为了让它稳定高效运行所付出的那些思考。