企业官网建设流程全解析

快速排序是我在数据结构课上第一次真正“看懂”的排序算法，当时用的就是最朴素的版本——把区间里第一个元素拿出来当枢轴。这一个看似随意的选择，后来反复出现在各种习题、面试题和比赛模板里。以第一个元素为枢轴的优点是代码结构直观、手算方便，缺点是当输入恰好有序或逆序时，性能会跌落到平方级，严重的直接栈溢出崩掉。这篇文章不是搬运教材，而是我把这个经典实现从头到尾写了一遍之后的完整记录：partition 里每个条件为什么这样写、边界怎么卡、实测中踩到哪些坑，以及在不推翻原有逻辑的前提下有哪些立竿见影的改良手段。无论你是刚接触快排的初学者，还是想把排序打牢再准备面试的人，这篇都值得从头看一遍。

1. 拿第一个元素当枢轴，到底图什么——选型逻辑与最坏情况预警

1.1 分治思想的一行话版本：选定枢轴，分割数组

快速排序本质上是一种分治算法，核心逻辑可以归纳成三步：

1. 在待排序区间里挑一个元素当枢轴（pivot），标题场景下就是直接取arr[low]；
2. 把区间内所有比枢轴小的元素挪到它左边，所有大于等于它的元素挪到右边，这一步称为分区（partition）；
3. 对枢轴左右两个子区间递归重复上述过程，直到每个区间只剩一个元素。

分治思想用生活类比最好懂：整理一摞扑克牌时，先抽第一张牌当基准，把比它小的牌放左边，比它大的牌放右边，然后分别把左右两堆继续按同样规则整理。快速排序值钱的地方在于所有移动都在原数组上就地完成，不需要额外申请一整块和原数组等大的空间。这一点在数据量上来之后差距非常明显。

1.2 第一个元素当枢轴的三个理由

市面上绝大多数教材讲快排时，都会从“第一个元素作为枢轴”入手，这确实有它的道理：

• 实现门槛最低：不需要生成随机数，不需要计算中间位置，拿arr[low]直接开干，少一层出错可能。
• 和经典“挖坑法”天然契合：先把arr[low]的值保存到pivot，这个位置就变成一个“坑”，等右边扫描到的小数填进来；随后右边又出现新坑，等左边扫描到的大数填进去。整个过程思路清晰，手算演算也很直观。
• 便于观察分区本质：当枢轴落在两端之一时，反而更容易让人理解“为什么分区会让数组局部有序”。

但也必须把话挑明：第一个元素当枢轴等于把性能命脉交给了输入数据的顺序。如果待排序数组已经升序或降序排列，每一轮分区后枢轴都待在端点附近，左右两个子区间极度不平衡（一个接近 n-1，另一个为 0），递归树退化成一条长链，时间复杂度直接变成 O(n²)。这个问题不是理论恐吓，后面第 4 章我会用实测数据给你看它到底有多严重。

1.3 常见教学实现路线怎么选

围绕“第一个元素作为枢轴”这个题目，实际存在几种不同风格的分区写法，初学者经常被网上各种版本搞混。我先把主流三种列出来：

本文主线选择挖坑法，因为“以第一个元素为枢轴”这个命题下，挖坑法是最贴合题目语义、也最容易一次性写对的版本。Lomuto 和 Hoare 的代码我会在后面的对比里适当提到，但完整流程重点讲挖坑法。

2. 挖坑法partition手写实录：指针移动顺序一个都不能错

2.1 挖坑法的核心循环：右找小、左找大、填进去

直接看代码，这是整个算法的灵魂：

int partition(int arr[], int low, int high) { int pivot = arr[low]; while (low < high) { // 从右向左找第一个小于 pivot 的元素 while (low < high && arr[high] >= pivot) { high--; } // 把它填到左边的坑里，high 位置变成新坑 arr[low] = arr[high]; // 从左向右找第一个大于 pivot 的元素 while (low < high && arr[low] <= pivot) { low++; } // 把它填到右边的坑里，low 位置又变成新坑 arr[high] = arr[low]; } // low == high 时，这个位置就是 pivot 的最终归属 arr[low] = pivot; return low; }

我建议你不要死记代码，而是理解这个过程：先把第一个位置的数抽走，此时low就是一个坑；右侧指针high向左扫，遇到比 pivot 小的数就把它搬到坑里；随后左侧指针low向右扫，遇到比 pivot 大的数就搬到右侧新坑；两侧反复交替，直到两个指针碰头，把保存在pivot里的值放到碰头位置。每个数最多被搬动一次，分区这一步整体是 O(n)。

2.2 三个边界条件的具体含义

这一段是手写快排最容易翻车的地方，我拆开讲：

• 外层while (low < high)：保证左右指针没有交叉，一旦碰头就停止扫描。少了这个条件，low和high互相越界是板上钉钉的事。
• 右扫描arr[high] >= pivot：这里必须用“大于等于”。含义是只要当前元素不小于 pivot，就继续向左挪，直到碰到第一个严格小于 pivot 的元素才停。如果你图省事写成>，那么遇到和 pivot 相等的元素时high会停下来，把等于 pivot 的值也当作“小数”填进左边坑里，分区逻辑瞬间错乱。
• 左扫描arr[low] <= pivot：同理，必须用“小于等于”，跳过所有和 pivot 相等的元素，只找严格大于 pivot 的大数。
• 内层扫描也要带low < high：这一点特别容易被忽略。比如整个区间全是大于 pivot 的元素时，右扫描如果没有low < high保护，high会一路降到-1，直接访问数组越界内存，程序行为立刻变得不可预测。

我见过很多人粘了模板代码能跑，但一上手自己写就挂，挂的位置十有八九就是这三处条件。记住一个口诀：右扫停小，左扫停大，等于全跳过，碰头即停手。

2.3 等值元素的处理策略：加不加等号的分水岭

等值元素是快排的经典杀手。一个全为相同数字的数组，是检验分区写法是否严谨的试金石。

假设数组是[5, 5, 5, 5]，如果右扫描条件写成arr[high] > pivot，那么第一次扫描时arr[3] = 5并不大于 5，high直接停住，然后执行arr[low] = arr[high]，把这个 5 搬到左边坑；紧接着左扫描同样因为arr[low]不是严格大于 5 而立刻停住，又把同一个 5 搬回右边。两个指针在同一个位置反复交换，永远无法收敛，这就是死循环的根源。

如果按我上面写的>=和<=，全相同数组会怎样？右扫描一路跳过所有等于 pivot 的元素，high最终走到与low相同的位置，外层循环退出，pivot 原地落位。虽然它在全相同数组下仍然会退化成 O(n²) 的分区次数，但至少逻辑是收敛的，不会卡死。这个区别在实战中就是“程序崩溃”和“程序能跑但慢”的本质差异。

3. 完整C代码与测试验证：从能编译到确认排序正确

3.1 模块划分与完整代码清单

完整实现应该拆成几个功能单一的模块：交换函数、分区函数、递归排序函数、验证函数、打印函数。下面是一份可以直接复制到本地编译运行的完整代码：

#include <stdio.h> #include <stdlib.h> #include <time.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]; while (low < high) { while (low < high && arr[high] >= pivot) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { low++; } arr[high] = arr[low]; } arr[low] = pivot; return low; } void quickSort(int arr[], int low, int high) { if (low < high) { int pos = partition(arr, low, high); quickSort(arr, low, pos - 1); quickSort(arr, pos + 1, high); } } int isSorted(int arr[], int n) { for (int i = 1; i < n; i++) { if (arr[i - 1] > arr[i]) { return 0; } } return 1; } void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main(void) { srand((unsigned)time(NULL)); int demo[] = {6, 1, 8, 3, 5, 9, 2, 7, 4}; int n = sizeof(demo) / sizeof(demo[0]); printf("排序前："); printArray(demo, n); quickSort(demo, 0, n - 1); printf("排序后："); printArray(demo, n); printf("结果验证：%s\n", isSorted(demo, n) ? "通过" : "失败"); int n2 = 10000; int *arr2 = (int *)malloc(n2 * sizeof(int)); for (int i = 0; i < n2; i++) { arr2[i] = rand() % 10000; } clock_t start = clock(); quickSort(arr2, 0, n2 - 1); clock_t end = clock(); printf("n=%d 随机数组，耗时：%.3f 秒，排序结果：%s\n", n2, (double)(end - start) / CLOCKS_PER_SEC, isSorted(arr2, n2) ? "通过" : "失败"); free(arr2); return 0; }

这份代码只依赖标准库，没有额外配置，任何带 C 编译环境的地方都能直接跑通。

3.2 测试用例设计：覆盖五类输入

很多人写完排序只拿一组随机数测一下就宣告完事，这远远不够。我的经验是至少覆盖五类输入：

空数组和单元素数组在quickSort里直接走if (low < high)这个保护，什么都不用做，这正好验证了递归出口写的对不对。两个元素的数组则能快速暴露 partition 交换逻辑里“枢轴最终位置偏移一位”这种经典错误。

3.3 断言验证与输出结果

isSorted函数承担最终裁判角色：从第二个元素开始，只要发现前一个大于后一个就返回 0。用断言而不是肉眼观察，是测试自动化最基本的一步，尤其后面数据量上来后，肉眼基本没法判断排序是否正确。

我在本地跑上面代码时，小数组的输出长这样：

排序前：6 1 8 3 5 9 2 7 4 排序后：1 2 3 4 5 6 7 8 9 结果验证：通过

n=10000 随机数组那行会显示一个很小的耗时数字，同时结果验证为“通过”。这只能证明“随机数据下算法是对的”，离“算法在任何输入下都可靠”还差得很远——这正是下一章要实测的内容。

4. 实测暴击：当输入变得“刁钻”，第一个元素枢轴的表现

4.1 有序数组与逆序数组的退化实验

把数组预先构造成严格升序，然后扔给这份代码排序。你会发现一个非常反直觉的现象：居然比随机数组慢得多，甚至根本跑不完。

原因要从递归结构上解释。升序数组里第一个元素是全局最小值，分区后 pivot 回到索引 0 的位置，右侧剩下 n-1 个元素继续递归；下一轮又取这 n-1 个元素里的第一个作为 pivot，它又是当前区间的最小值。递归树就此长成一条单链表，每一层只减少一个元素，总比较次数变成n + (n-1) + (n-2) + ... + 1 ≈ n²/2。降序数组同理，只不过 pivot 变成每次区间的最大值，退化的方式一模一样。

我在自己的测试机上试过：n=50000 的升序数组，栈直接爆掉，程序段错误退出；而 n=50000 的随机数组，排序耗时在几十毫秒级别，肉眼感知不到任何压力。同一份代码，换一种输入就是“能用”和“崩溃”的两极。这就是输入敏感性的真实代价。

4.2 全相同数组：无限递归风险的现场实测

全相同数组是另一个高频雷区。如果分区扫描条件里的等号写错，程序会陷入死循环；即使像我上面那样把等号写对，它也并不会因为“所有元素相等所以无需排序”而快速结束。分区结果始终是 pivot 原地落位，左侧区间为空，右侧区间长度减一，递归照样退化成 O(n²)。全相同数组的排序时间同样会从“毫秒”变成“肉眼可见的慢”。

但这里有一个很微妙的区别：扫描条件写对，全相同数组只是慢，不会死循环；扫描条件写错，则是 CPU 占用直接拉满，程序永远不会返回。这在调试时是两种截然不同的症状。先确认你写的是>=和<=，再谈性能优化，顺序不能反。

4.3 性能数据记录：n=10000 与 n=50000 的对比

为了把退化程度量化，我做了一组简单对照实验。三个数组都是同样的长度，分别填充随机数、升序数、全相同数，用同样的clock()计时：

第 1.2 节里说的“最坏情况”，在这一组数据里已经完整兑现。升序数组和全相同数组在 n=50000 时就因为递归调用层数过深，把默认栈空间耗尽。这还不是算法逻辑本身的极限，而是 C 运行时栈帧大小给递归实现的硬限制。

5. 三个升级方向：从入门实现到能抗住压的工程实现

5.1 策略一：随机化枢轴

随机化枢轴几乎是性价比最高的单行优化。思路很简单：在区间内随机选一个位置，把该位置的元素和arr[low]交换，然后继续走挖坑法。这样无论输入是升序、降序还是全相同，每次枢轴落位在哪个位置都变成随机事件，坏情况的出现概率被压到极低。

int randomIndex = low + rand() % (high - low + 1); swap(&arr[low], &arr[randomIndex]); int pivot = arr[low];

我测试下来，随机化后升序输入不再崩溃，排序时间回到“毫秒级”，因为每次枢轴平均落在区间中部附近，递归深度从 n 降到 log n 级别。代价仅仅是每次分区生成一个随机数，几乎可以忽略。需要注意rand() % 区间长度在区间长度特别大时有轻微不均匀性，但对快排这种对均匀性要求不高的场景完全够用。

5.2 策略二：三数取中

三数取中比随机化更稳，因为它刻意避免最坏情况。取区间左端、右端、中点三个位置的元素，把这三者的中位数换到第一个位置当枢轴。这样即使输入是升序或降序，枢轴也会落在整个区间的中位数附近，递归树天然平衡。

经典的三数取中比较交换套路是这样：

int mid = low + (high - low) / 2; if (arr[mid] < arr[low]) swap(&arr[mid], &arr[low]); if (arr[high] < arr[low]) swap(&arr[high], &arr[low]); if (arr[high] < arr[mid]) swap(&arr[high], &arr[mid]); swap(&arr[mid], &arr[low]);

三次比较加三次可能的交换，把三个数中从小到大排一遍，取出中间值。三数取中对近乎有序的数据效果立竿见影，而且不需要引入随机数，行为可复现，调试时比随机化更友好。代价是每次分区多几次比较，常数略有上升，但换来的是最坏情况被大幅稀释，这笔交易非常划算。

5.3 策略三：小数组插入排序

快速排序在区间很小的时候，递归和分区调用的开销开始超过排序本身的开销。工程实现里常见的做法是：当区间长度小于某个阈值（比如 16）时，不再递归，而是直接用插入排序收尾。

void quickSort(int arr[], int low, int high) { if (high - low + 1 <= 16) { insertionSort(arr, low, high); return; } int pos = partition(arr, low, high); quickSort(arr, low, pos - 1); quickSort(arr, pos + 1, high); }

插入排序在 n 很小的时候虽然也是 O(n²)，但常数极小，而且对缓存友好，实际速度往往不输继续做几层快排递归。这个小优化也是把递归深度再压低一层，让栈溢出风险进一步下降。阈值选 16 还是 32，取决于机器，我习惯用 16，效果已经很稳。

6. 踩坑复盘：从栈溢出到结果错乱，我的一份排错索引

6.1 症状一：递归没有出口导致栈溢出

如果你发现程序跑小数组正常，跑大数组直接死掉或段错误，第一步先检查quickSort的递归调用区间是否真的在变小。一个常见的低级错误是把右半区间写成quickSort(arr, low, pos)，而不是quickSort(arr, low, pos - 1)。当pos == low时，右半区间变成quickSort(arr, low, low)，区间没有缩小，如果这时low < high的判断又恰好成立，就会无限递归。

排查方法很简单：在quickSort开头加一行打印当前low、high、pos，跑一个升序小数组。一旦发现某次递归的参数跟上一层完全一样，立刻就能锁定问题。

6.2 症状二：排序结果仍有未排序区间

这种问题最隐蔽。以arr = [4, 2, 6, 1, 3]为例，我手动走一遍正确的挖坑法：

• 第一轮 partition 后数组变成[3, 2, 1, 4, 6]，返回 3，枢轴 4 到达最终位置；
• 左区间[3, 2, 1]继续排序，右区间[6]只剩一个元素，自然有序。

如果你发现结果里出现“局部有序但没排全”的现象，多半是分区返回的位置不是 pivot 实际落位，而是偏移了一个单位，导致左右区间的切分点覆盖了正确位置。这时候不要瞎猜，把 partition 返回值和每次分区后的数组打印出来，和手算结果对照，通常一眼就能看出偏移。

6.3 症状三：性能忽快忽慢

如果你觉得代码没问题但性能时好时坏，先检查是不是输入数据本身在变化。第一个元素当枢轴的实现，性能曲线完全看输入脸色：随机数据秒完，有序数据卡死，全相同数据爆炸。这种“忽快忽慢”不是玄学，而是算法输入敏感性的直接体现。解决办法不外乎第 5 章那三招——随机化、三数取中、小数据切插入排序。我个人的偏好是“三数取中 + 阈值插入排序”的组合，既保留了可复现性，又把最坏情况的概率压到工程可接受范围。

我在实际手写排序算法时的体会是：用第一个元素当枢轴做练习，最大的价值不是写出一个多快的排序，而是把分区、边界、递归、退化这些底层机制彻底暴露在你面前。它让你在踩过坑之后真正理解，为什么工业级排序实现里从来看不到这种朴素写法，也让你面对“为什么快排不如宣传的那么快”这类问题时，能给出有实验支撑的答案，而不是背课本结论。这个打法，值得每个学排序的人从头走一遍。