企业官网建设流程全解析

快速排序如果限定“以第一个元素为枢轴”，基本就是数据结构课里最经典的教科书版快排。很多同学第一次写快排，要么分区完成后枢轴没有回到正确位置，要么递归边界写错直接爆栈，要么排序一个已经排好序的数组，性能慢到让人怀疑人生。这篇文章我打算把“以第一个元素为枢轴”的C语言实现从头到尾拆开讲一遍——从分区的设计逻辑、完整可运行的代码、手把手模拟一次分区过程，到已排序数组为什么会退化到 O(n²)，再到怎么在不改变“第一元素”这个命题的前提下做低成本优化。如果你正在学排序算法，或者写作业时被这个版本卡住，这篇内容应该能让你一次搞明白。

1. 快速排序的分治思路：三个关键步骤

1.1 分治三步为什么在快排里看起来只有两步

快速排序用的核心思想是分治：把一个大的排序任务拆成若干小的子任务，子任务解决后，大任务自然就完成了。

通常分治算法是三步：分解、求解、合并。比如归并排序，先裂成两半，分别排好，再合并，所以它的合并步骤很重。快速排序不太一样，它的“合并”几乎是隐式的。快排的套路是这样的：

1. 从数组里挑一个值当枢轴（本文按照约定，直接拿第一个元素 arr[low] 当枢轴）。
2. 把整个数组整理成“左边全部小于等于枢轴，右边全部大于等于枢轴”的样子，这个动作叫分区。
3. 对枢轴左边和右边的两个子数组，分别递归执行同样的操作。

如果你只盯着递归函数看，会觉得“这不是只有分解和求解吗”？其实分区的瞬间，枢轴已经被放到了最终位置上。也就是说，分区动作既完成了分解，又完成了一部分“合并”，等到左右两个子数组各自有序时，整个数组自然就有序了。

这里有一个非常容易被忽略的点：快排的核心复杂度不在递归，在于那个分区函数写得对不对。分区函数一旦返回了错误的枢轴位置，后面的递归全盘皆错，甚至陷入无限递归。

1.2 枢轴选择对“分治”结构的决定性作用

为什么谈快排一定要先谈枢轴？因为枢轴决定了左右两个子数组的规模。理想情况下，枢轴刚好是中位数，左右两边各占一半，递归树是一棵匀称的二叉树，树高是 log₂n，每层处理 n 个元素，总复杂度 O(n log n)。

但“以第一个元素为枢轴”这个选择，只保证了“枢轴是数组里的某个元素”，完全不保证大小位置。如果运气好，第一个元素正好是中位数，性能漂亮；如果第一个元素是最大值或最小值，比如对 [2, 1, 3] 取第一个元素 2，它比左边的大，比右边的小，还算凑合；但对 [3, 2, 1] 取第一个元素 3，这意味着左边子数组存在，右边子数组不存在，每一轮只消掉一个元素，复杂度立刻往 O(n²) 崩。

所以理解枢轴，是理解快排一切行为的关键。后面第 2 章我会专门分析第一个元素当枢轴时最典型的灾难场景。

2. 为什么默认选第一个元素：教学的便利与隐藏的坑

2.1 从实现角度讲：取第一个元素是“零成本”的选择

如果你自己设计快排，选一个“好的枢轴”其实需要额外计算。比如从数组里找中位数，本身就要花时间；比如随机选一个位置，再把这个位置的值换到开头，或者换到末尾，至少要多写一个交换逻辑。

而取第一个元素，代码上只有一个动作：int pivot = arr[low];。不需要交换，不需要额外变量，不需要处理枢轴不在边界的情况，分区结束后直接和边界处元素交换即可。这对初学者的心智负担最小，也方便老师讲清楚分区的流程。所以绝大多数教材、网课和期末试卷里，讲到最基础的快排时，都会默认“取第一个元素作为枢轴”。

但是请注意：方便理解，不代表方便性能。这里埋着快排最著名的雷：输入恰好有序时，性能会退化到冒泡排序的水平。

2.2 最坏情况：对已排序数组排序的灾难现场

假设数组是 [1, 2, 3, 4, 5, 6, 7, 8]，用第一个元素 1 当枢轴：

• 分区后，1 回到位置 0，右边是 [2, 3, 4, 5, 6, 7, 8]，左边为空。
• 对右边再次递归，取 2 当枢轴，2 回到位置 1，右边剩下 [3, 4, 5, 6, 7, 8]。
• 如此往复，每一轮只确定一个元素的位置，划分出来的两个子数组一个长度为 0，一个长度为 n-1。

这相当于把问题规模从 n 减少到 n-1，而不是减半。递归深度变成 n，总时间 T(n) = T(n-1) + O(n)，展开后就是一个等差数列求和，复杂度是 O(n²)。

同样的道理，对降序数组 [8, 7, 6, 5, 4, 3, 2, 1] 取第一个元素 8，右边子数组是空，左边是 [7, 6, 5, 4, 3, 2, 1]，情况一样糟糕。有趣的是，现实工作中“数据接近有序”是很常见的场景。比如日志文件按时间排好序后，你再按时间排序；或者数据库里某个字段基本有序。这时候用“固定取第一个元素”的快排，实际表现可能连插入排序都不如。

2.3 复杂度推导与递归树视角

从递归树看，均衡划分的树高是 log₂n，包括 n 个叶节点，每层总处理量是 n，所以总时间 O(n log n)。不均衡划分的树高变成 n，虽然每层处理量仍然是 n 减去已经固定的元素，但累计起来是 n + (n-1) + (n-2) + ... + 1 = O(n²)。

很多教材直接给结论“快排平均 O(n log n)，最坏 O(n²)”，但不讲清楚最坏从哪来。理解了这个推导，你就明白：

• 对老师布置的“第一个元素为枢轴”版本，提交前一定要想清楚测试数据是否有序。
• 对真实项目里要使用的快排，光“第一个元素”是不够的，需要加一点优化，我后面第 6 章会讲。

3. 完整 C 语言实现：单指针分区法

3.1 分区函数核心代码逐行拆解

在介绍代码之前，先明确一点：快速排序最常见的两种分区写法，一种是单指针扫描法，也叫 Lomuto 分区；另一种是双指针相向扫描法，也叫 Hoare 分区。教学题目默认“第一个元素为枢轴”时，绝大多数指代的是单指针分区法，因为它最好写、最好解释。

单指针分区的思路是：用变量 i 维护“已经确定为小于枢轴的元素区间的右边界”，用变量 j 从第二个元素开始往右扫描，凡是遇到比枢轴小的元素，就先扩大 i，再交换 arr[i] 和 arr[j]。扫描结束后，把枢轴从 arr[low] 换到 arr[i]，此时 arr[i] 左边全部小于等于枢轴，右边全部大于等于枢轴。

代码如下：

// 单指针分区法：取第一个元素 arr[low] 作为枢轴 int partition(int arr[], int low, int high) { int pivot = arr[low]; // 直接拿第一个元素当枢轴 int i = low; // i 指向枢轴最终存放位置的前一个边界 int j; for (j = low + 1; j <= high; j++) { if (arr[j] < pivot) { // 发现一个比枢轴小的元素 i++; // 边界右移 swap(&arr[i], &arr[j]); // 把它换到左侧区域 } } // 把枢轴从 low 位置挪到 i 位置，完成归位 swap(&arr[low], &arr[i]); return i; // 返回枢轴最终位置 }

我强调几个细节：

• i 的初始值是 low，不是 low - 1。因为枢轴本身还在 arr[low]，i 指向的是枢轴“应该去的位置”的候选。我第一次写这个算法时，把 i 初始化成 low - 1，结果分区完枢轴位置差了 1，整个排序完全乱掉。
• 循环从 low + 1 开始，因为 arr[low] 是枢轴，不需要也绝对不能让它参与扫描，否则可能把枢轴换走。
• 只有当 arr[j] < pivot 时才交换。如果是 arr[j] <= pivot，会让相等的元素也跑到左边去。这个差别在普通场景无所谓，但在处理大量重复元素时会影响均衡性，后文会提。
• 交换函数必须通过指针修改数组元素，直接传值修改不了，这个是 C 语言新手最常见的错误。

3.2 手把手模拟一次完整分区

光看代码有点抽象，我拿一组不会产生歧义的数据来走一遍。

假设数组 arr = {6, 2, 8, 5, 1, 9, 4, 7, 3}，low = 0，high = 8。

初始状态：

• pivot = arr[0] = 6
• i = 0
• j 从 1 开始扫描

逐步过程：

• j = 1，arr[1] = 2 < 6，i 变成 1，交换 arr[1] 和 arr[1]，数组不变，此时 i = 1 表示下标 1 及左边都是小于 6 的值。
• j = 2，arr[2] = 8 不小于 6，不处理。
• j = 3，arr[3] = 5 < 6，i 变成 2，交换 arr[2] 和 arr[3]，数组变成 {6, 2, 5, 8, 1, 9, 4, 7, 3}。
• j = 4，arr[4] = 1 < 6，i 变成 3，交换 arr[3] 和 arr[4]，数组变成 {6, 2, 5, 1, 8, 9, 4, 7, 3}。
• j = 5，arr[5] = 9 不小于 6，不处理。
• j = 6，arr[6] = 4 < 6，i 变成 4，交换 arr[4] 和 arr[6]，数组变成 {6, 2, 5, 1, 4, 9, 8, 7, 3}。
• j = 7，arr[7] = 7 不小于 6，不处理。
• j = 8，arr[8] = 3 < 6，i 变成 5，交换 arr[5] 和 arr[8]，数组变成 {6, 2, 5, 1, 4, 3, 8, 7, 9}。

最后跳出循环，i = 5，执行 swap(&arr[0], &arr[5])，数组变成 {3, 2, 5, 1, 4, 6, 8, 7, 9}。

此时可以看到，6 的下标是 5，它左边 {3, 2, 5, 1, 4} 都小于等于 6，右边 {8, 7, 9} 都大于等于 6。分区成功，函数返回 5。

整个过程理解透了以后，你会发现在 j 扫描时，i 其实始终指向“最后一个小于枢轴的已发现元素”。这也就是为什么最后可以把枢轴换到 i 的位置——因为 arr[i+1] 到 arr[high] 全都不小于枢轴。

3.3 完整可运行程序示例

以下是一份完整程序，包含排序函数、分区函数、交换函数、打印函数，以及 main 里的多组测试用例。你可以直接复制编译运行，也可以把注释去掉观察过程。

#include <stdio.h> void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } // 单指针分区法：取第一个元素作为枢轴 int partition(int arr[], int low, int high) { int pivot = arr[low]; int i = low; int j; for (j = low + 1; j <= high; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[low], &arr[i]); return i; } // 快速排序：以第一个元素为枢轴 void quickSort(int arr[], int low, int high) { if (low < high) { // 递归终止条件：子数组至少有两个元素 int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); // 排序枢轴左边 quickSort(arr, pi + 1, high); // 排序枢轴右边 } } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr1[] = {6, 2, 8, 5, 1, 9, 4, 7, 3}; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("排序前: "); printArray(arr1, n1); quickSort(arr1, 0, n1 - 1); printf("排序后: "); printArray(arr1, n1); // 测试空数组和单元素数组 int arr2[] = {42}; int n2 = 1; quickSort(arr2, 0, n2 - 1); printf("单元素: "); printArray(arr2, n2); // 测试一个有序数组，观察递归深度大的情况 int arr3[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int n3 = 10; quickSort(arr3, 0, n3 - 1); printf("有序输入: "); printArray(arr3, n3); return 0; }

运行结果：

排序前: 6 2 8 5 1 9 4 7 3 排序后: 1 2 3 4 5 6 7 8 9 单元素: 42 有序输入: 1 2 3 4 5 6 7 8 9 10

注意那个有序输入测试，虽然排序结果正确，但实际执行时每一轮都会出现一个空子数组，10 个元素就要递归 10 层。如果把这个 n 加到 10 万，程序会非常慢，甚至栈溢出。这是“固定第一个元素”这个版本最大的现实问题。

3.4 递归终止条件为什么必须是 low < high

quickSort函数里的递归终止条件是if (low < high)，意思是有两个及以上元素才需要排序。如果写成low <= high，当子数组只有一个元素时还会继续调用一次，而那次调用里 partition 会原样返回，白白增加一次调用栈，数据一大很容易爆栈。

还有一种写法是if (low >= high) return;，效果相同。我建议初学者养成习惯：分区返回的 pi 一定在 [low, high] 范围内，递归调用时左边到 pi-1，右边从 pi+1 开始。如果你把右边写成从 pi 开始，而 pi 位置的元素已经归位，相当于每次递归都会把这个元素再扫一遍，虽然结果不一定错，但会产生多余的比较和递归层级。

4. 另一种实现：双指针相向分区法的异同

4.1 双指针分区的思路

单指针分区法实现简单，但有一个特点：它把所有小于枢轴的元素先集中到左边，再通过一次交换把枢轴归位。这会导致一个明显问题：即使某个元素在分区过程中位置本来就是对的，也可能被反复交换多次。比如很大一批小于枢轴的元素本来就在左边，j 扫描到它们时仍可能触发多余的交换。

双指针相向分区法试图减少交换次数。思路是：

• 用两个指针 left 和 right，left 从 low + 1 向右走，right 从 high 向左走。
• left 负责找第一个大于等于枢轴的元素，right 负责找第一个小于等于枢轴的元素。
• 找到后两者交换，直到 left 和 right 相遇。
• 最后把枢轴换到相遇位置，或者返回相遇点作为分割边界。

双指针分区的典型实现如下：

int partition_two(int arr[], int low, int high) { int pivot = arr[low]; int left = low; int right = high; while (left < right) { // 让 right 向左移动，直到找到小于等于 pivot 的元素 while (left < right && arr[right] >= pivot) { right--; } // 把这个小的元素放到 left 的位置 arr[left] = arr[right]; // 让 left 向右移动，直到找到大于 pivot 的元素 while (left < right && arr[left] <= pivot) { left++; } // 把这个大的元素放到 right 的位置 arr[right] = arr[left]; } // left 和 right 相遇的位置就是枢轴最终位置 arr[left] = pivot; return left; }

这种写法的好处是分区一趟下来，大于和小于枢轴的元素各自待在最终位置附近，交换次数通常少于单指针扫描法。对于以随机数组为输入的排序，双指针分区法的常数因子更小。

但它对实现细节的敏感度更高。如果一个不小心，left 或 right 越界，或者空数组传入，程序直接崩溃。这也是为什么教学题“用第一个元素做枢轴”通常不要求采用双指针版本，因为对初学者来说，单指针版本更不容易写错。

4.2 两种方案对比

无论选哪种分区法，只要枢轴固定取第一个元素，最坏情况 O(n²) 都躲不掉。因为问题本质是“枢轴选择策略过于确定”，与分区写法无关。

4.3 实操建议

如果你在写作业或做练习，我建议先用单指针分区法把逻辑跑通，再尝试改写为双指针分区法。因为面试或进阶场景里，不少考察点就是双指针分区法能不能在十分钟内无 bug 写出来。

如果你打算把双指针版本用到自己的工具库中，请注意处理重复元素。上面的示例代码用了arr[right] >= pivot和arr[left] <= pivot，遇到大量重复元素时会尽量让左右区域相对均衡。如果你用严格大于和严格小于，遇到全相同元素的数组，left 和 right 可能不会正常相遇，导致无限循环。

5. 实操中必踩的坑与快速排查

5.1 分区后枢轴没有归位的典型症状

很多初学者写完快排一运行，发现结果差不多是对的，但个别元素错位，或者某些元素根本没参与排序。这种问题通常指向分区函数返回的位置不正确。

排查思路是：单独测试 partition 函数，打印分区完的数组以及返回的下标，人工检查返回位置左边是否都小于等于枢轴、右边是否都大于等于枢轴。如果不符合，问题就在分区函数本身。常见的错误有三个：

• 循环里写成for (j = low; j <= high; j++)，把枢轴自己也拿去比较了，等于把自己当作“比枢轴小的元素”换走。
• i 初始值写错，直接导致枢轴最终位置偏差。
• 最后忘记调用swap(&arr[low], &arr[i])，导致枢轴一直留在原位置，整个分区相当于白做。

5.2 无限递归或递归栈溢出

无限递归通常发生在递归调用边界写错时。假设分区返回位置为 pi，如果你调用quickSort(arr, low, pi)而不是quickSort(arr, low, pi - 1)，那么当 pi == low 时，左边子数组还是原来的 low 到 low，虽然只有一个元素，但在某些条件下递归不会停止。

比如已经有序的数组，第一次分区返回 pi = low，然后你调用quickSort(arr, low, pi)，这等于继续处理low到low这个区间，虽然里面只有一个元素，但如果终止条件写得不够严格，就会反复递归。

另一种栈溢出场景是输入数组非常大且接近有序。比如 20 万个元素的升序数组，固定取第一个元素，递归深度达到 20 万层。默认调用栈根本扛不住，程序直接段错误崩溃。你可以把递归函数里的终止条件打印到屏幕上，或者用全局计数器观察递归深度，通常会得到“深度爆炸”的结论。

5.3 重复元素带来的死循环

以单指针分区法为例，如果把 if 判断写成arr[j] <= pivot，那么所有等于枢轴的元素都会集中到左侧。对于 [1, 1, 1, 1, 1] 这种全相同数组，每次分区后，枢轴归位到一个位置，右边剩下 n-1 个相同元素，继续递归，不会死循环，但复杂度变成了 O(n²)。

双指针分区法中，如果 left 和 right 的移动条件写成了严格大于和严格小于，遇到全部相同元素时，left 找不到大于枢轴的值，right 找不到小于枢轴的值，指针碰面后返回的位置有问题，可能死循环。

处理大量重复元素时，常用的思路是在分区时让相等元素均匀分到两边，或者把相等元素单独放到数组中部。但作为以教学为主的“第一个元素为枢轴”版本，我建议你在分区判断上写成严格小于，不做特殊处理；如果实际数据里重复元素特别多，再考虑三路快排。

5.4 常见问题速查表

这个速查表我建议你保存下来，因为这些问题不仅出现在这次作业里，几乎每个人学习快排都会踩中其中几个。

6. 在“第一个元素”基础上做的低成本优化

6.1 三数取中选枢轴：只加三行代码

三数取中的思路是：不要直接拿 arr[low] 当枢轴，而是从 arr[low]、arr[high]、arr[(low+high)/2] 三个位置中选一个中位数当枢轴。选出来之后，把它交换到 arr[low]，这样后面的分区代码完全不用改。

这种做法保留了“分区前枢轴在 low 的位置”这一习惯，让之前所有的实现逻辑继续成立，同时又打破了“输入有序导致最坏”的尴尬。因为对一个已排序数组，三数取中选择的中位数基本就是数组的中间值，每轮划分能大致对半开。

示例代码：

int medianOfThree(int arr[], int low, int high) { int mid = low + (high - low) / 2; // 找到三个位置中的中位数下标 if ((arr[low] - arr[mid]) * (arr[low] - arr[high]) <= 0) { return low; } else if ((arr[mid] - arr[low]) * (arr[mid] - arr[high]) <= 0) { return mid; } else { return high; } } int partition_opt(int arr[], int low, int high) { int medianIdx = medianOfThree(arr, low, high); swap(&arr[low], &arr[medianIdx]); // 让中位数成为新的“第一个元素” int pivot = arr[low]; // 后面的逻辑和之前完全一样 }

这种方式对数组的适应性大幅提高，虽然理论上仍存在某种构造出的最坏输入，但日常使用几乎很难遇到。这也是很多工业级排序库采用的基础策略之一。

6.2 小区间改用插入排序

快速排序在递归到很小规模的子数组时，函数调用开销、分区交换开销占比越来越大。比如一个长度只有 8 的数组，也去走一趟分区流程，显然不如直接插入排序划算。实际工程里，可以在递归中加一个判断：

void quickSort_hybrid(int arr[], int low, int high) { if (high - low < 16) { insertionSort(arr, low, high); return; } int pi = partition_opt(arr, low, high); quickSort_hybrid(arr, low, pi - 1); quickSort_hybrid(arr, pi + 1, high); }

这个阈值取 16 或 32 都可以，可以根据实际数据规模测试调整。插入排序虽然最坏也是 O(n²)，但在小区间内“几乎有序”的可能性大，真实跑起来通常非常快。这种混合策略在真实项目里很常见，且和“第一个元素为枢轴”并不冲突，因为优化后的函数在真正递归时，仍然通过 swap 把选定的枢轴挪到了第一个位置。

6.3 随机化枢轴：用概率消灭最坏情况

随机化方案的思路是：在 [low, high] 范围内随机挑一个下标，把该元素交换到 low，再沿用“第一个元素”的分区逻辑。这样一来，即便输入是有序的，枢轴理论上也能随到接近中位数的位置，把确定性的最坏 O(n²) 变成概率极低的期望 O(n log n)。

#include <stdlib.h> #include <time.h> int partition_random(int arr[], int low, int high) { int randomIdx = low + rand() % (high - low + 1); swap(&arr[low], &randomIdx); // 把随机选中的元素放到第一个位置 int pivot = arr[low]; // 后面继续用单指针分区法 }

在 main 函数开头调用srand(time(NULL))。每次排序选取随机下标，对某种特定恶意输入就不再有稳定被击穿的可能。

不过要注意：随机化带来的是一个期望复杂度，不是绝对的最坏保证。如果想要“绝对不超过 O(n log n)”的排序，就应该考虑堆排序或归并排序。快排在工程里的定位是“通常情况下最快”，前提是配合这些优化手段使用。

6.4 一次综合优化后的完整核心代码

把三数取中、小区间插入排序组合起来，你可以得到一段性价比很高的快排实现：

void insertionSort(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 quickSort_final(int arr[], int low, int high) { if (low >= high) return; if (high - low < 16) { insertionSort(arr, low, high); return; } int mid = low + (high - low) / 2; if ((arr[low] - arr[mid]) * (arr[low] - arr[high]) > 0) { swap(&arr[low], &arr[mid]); } if ((arr[low] - arr[mid]) * (arr[low] - arr[high]) > 0) { swap(&arr[low], &arr[high]); } if ((arr[mid] - arr[high]) > 0) { swap(&arr[mid], &arr[high]); } swap(&arr[low], &arr[mid]); int pivot = arr[low]; int i = low; for (int j = low + 1; j <= high; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[low], &arr[i]); quickSort_final(arr, low, i - 1); quickSort_final(arr, i + 1, high); }

这段代码仍然以“第一个元素”作为分区时的枢轴位置，但在真正分区前把更合适的元素换到了第一个位置。实测中，它面对随机数组、有序数组、大量重复数组，性能都比裸的“第一个元素”版本稳定得多。如果你只是应付作业，用第 3 章的版本就够了；如果你打算把这个排序用到自己的工具代码里，我建议直接采用 6.4 的版本。

我在实际调试快排时最深的体会是：算法本身不难，难的是分区边界那一两个下标。很多人写不出来、调不通，不是因为不懂分治，而是因为不够认真地模拟“某个指针现在指向哪里”。建议你把第 3.2 节那种手推模拟自己画一遍，用笔在纸上写下每次 i 和 j 的变化。这个动作看起来笨，但对理解整个算法有奇效。最后再分享一个小技巧：如果你担心自己的代码在边界条件下出错，就在分区函数里临时加打印，输出 low、high、pivot、i、j 以及当前数组，跑一组小数据观察。一次打印胜过十次猜测。