一、快速排序思想
快速排序的核心思想是分治策略，简单来说就是'分而治之'，它通过三步实现高效排序：
C算法
快速排序算法思想与多种实现方式
详细阐述了快速排序的分治思想，涵盖 Hoare 双指针、挖坑法、Lomuto 前后指针三种经典分区实现。内容包括时间复杂度分析、针对有序数组的优化策略（随机选基准、三数取中）、小区间插入排序优化及非递归迭代实现。此外还介绍了三路划分处理大量重复数据的方法，并对比了普通快排与三路划分的效率差异。
详细阐述了快速排序的分治思想，涵盖 Hoare 双指针、挖坑法、Lomuto 前后指针三种经典分区实现。内容包括时间复杂度分析、针对有序数组的优化策略（随机选基准、三数取中）、小区间插入排序优化及非递归迭代实现。此外还介绍了三路划分处理大量重复数据的方法，并对比了普通快排与三路划分的效率差异。
快速排序的核心思想是分治策略，简单来说就是'分而治之'，它通过三步实现高效排序：
思想本质
快速排序的高效性，正是源于「分区」这一步：它通过一次遍历就将一个大问题拆分成了两个规模更小的子问题，而子问题的排序可以独立进行，无需额外的合并操作。这种'拆分为小问题→独立解决→自然合并'的思路，是分治思想的典型体现。
Hoare 版本是快速排序的经典原地分区实现，由算法发明者 Tony Hoare 提出，核心是双指针相向遍历。
核心步骤：
针对升序排序：首先选取区间首元素作为基准值 key，然后右指针从右向左寻找首个小于 key 的元素，左指针再从左向右寻找首个大于 key 的元素，交换两指针指向的元素并重复此过程，直到两指针相遇，最后将基准值与相遇位置的元素交换，即可完成分区（分区后基准左侧均小于 key、右侧均大于 key）。
特点：原地分区、无额外空间开销，但需遵循「右指针先行」规则，否则会导致基准归位错误。
void QuickSort1(int* a, int left, int right) {
// 递归终止条件：区间元素个数≤1 时，无需排序直接返回
if (left >= right) {
return;
}
// 初始化指针：begin/end 遍历区间，keyi 标记基准值初始位置（选左端点为基准）
int begin = left;
int end = right;
int keyi = left;
// 双指针相向遍历，完成区间分区（升序排序）
while (begin < end) {
// 右指针从后往前找：第一个比基准值小的元素
while (begin < end && a[end] >= a[keyi]) {
end--;
}
// 左指针从前往后找：第一个比基准值大的元素
while (begin < end && a[begin] <= a[keyi]) {
begin++;
}
// 交换找到的两个元素，让小值到左、大值到右
swap(&a[begin], &a[end]);
}
// 指针相遇时，该位置就是基准值的最终位置，交换归位
swap(&a[keyi], &a[begin]);
keyi = begin;
// 递归处理基准值左右两侧的子区间，完成整体排序
QuickSort1(a, left, keyi - 1);
QuickSort1(a, keyi + 1, right);
}
**问题 1：**为什么 left 和 right 指定的数据和 key 值相等时不能交换？
这张图展示的是快速排序在最优情况下的时间复杂度推导：每次划分都能将数组均匀分成两部分，递归树会有 logN 层，且每一层都需要处理约 N 个元素，总的时间复杂度为 O(NlogN)。
有些同学可能会疑惑，为啥每层遍历的元素都是 N？实际上每层遍历的元素个数是 N 减去该层基准值的数量，但基准值数量相对于 N 是低阶项，在大 O 表示法中可以忽略不计，因此我们仍认为每层总遍历元素数约为 N。
那如果数组是有序的情况还能达到均分吗？显而易见，不能。
但是在实际中我们会对快排进行优化，让其能近似达到一个平衡二叉树的状态。
void QuickSort1(int* a, int left, int right) {
// 递归结束条件
// >：只有一个元素
// =：没有元素
if (left >= right) {
return;
}
int begin = left;
int end = right;
int keyi = left;
// 优化 1：随机选 keyi
int randi = left + rand() % (right - left + 1);
swap(&a[randi], &a[keyi]);
// 处理 [begin end] 区间
// 当 begin 和 end 指针相遇时，就找到了基准值 key 最终应该放置的位置
while (begin < end) {
// 右边找小：升序
while (begin < end && a[end] >= a[keyi]) {
end--;
}
// 左边找大：升序
while (begin < end && a[begin] <= a[keyi]) {
begin++;
}
// 找到后交换
swap(&a[begin], &a[end]);
}
// 走到这代表 begin 和 end 当前位置就是 key 的合适位置
swap(&a[keyi], &a[begin]);
keyi = begin;
// 递归子区间
// [left keyi - 1] keyi [keyi + 1 right]
QuickSort1(a, left, keyi - 1);
QuickSort1(a, keyi + 1, right);
}
即使输入是有序数组，随机选基准也能大概率避免'每次选到最左/最右元素'，让递归树尽可能平衡，将最坏时间复杂度 O(n^2) 优化为概率上的 O(nlogn)。
int GetMidNumi(int* a, int left, int right) {
int midi = (right + left) / 2;
if (a[left] < a[midi]) {
if (a[right] < a[left]) {
return left;
} else if (a[right] > a[midi]) {
return midi;
} else {
return right;
}
} else // a[left] > a[midi]
{
if (a[right] > a[left]) {
return left;
} else if (a[midi] > a[right]) {
return midi;
} else {
return right;
}
}
}
void QuickSort1(int* a, int left, int right) {
// 递归结束条件
// >：只有一个元素
// =：没有元素
if (left >= right) {
return;
}
int begin = left;
int end = right;
int keyi = left;
// 优化 2：三数取中
int midi = GetMidNumi(a, left, right);
swap(&a[midi], &a[keyi]);
// 处理 [begin end] 区间
// 当 begin 和 end 指针相遇时，就找到了基准值 key 最终应该放置的位置
while (begin < end) {
// 右边找小：升序
while (begin < end && a[end] >= a[keyi]) {
end--;
}
// 左边找大：升序
while (begin < end && a[begin] <= a[keyi]) {
begin++;
}
// 找到后交换
swap(&a[begin], &a[end]);
}
// 走到这代表 begin 和 end 当前位置就是 key 的合适位置
swap(&a[keyi], &a[begin]);
keyi = begin;
// 递归子区间
// [left keyi - 1] keyi [keyi + 1 right]
QuickSort1(a, left, keyi - 1);
QuickSort1(a, keyi + 1, right);
}
这段代码为快速排序实现了三数取中优化，核心是通过 GetMidNumi 函数从区间的左、中、右三个位置中选出数值居中的元素下标，将其交换到区间左端点作为基准值，以此避免在有序数组中选到极值导致的性能退化，让递归树更接近平衡，从而将时间复杂度稳定在 O(NlogN)。
随机选基准和三数取中可避免快排在有序数组下的性能退化，二选一即可；但面对大量重复数据时效率仍会下降，后续将介绍三路划分来解决这一问题。
由于快排在分区过程中会进行跨位置的交换操作（例如 swap(&a[cur], &a[prev])），这会打乱相等元素的相对位置，因此快速排序是不稳定的排序算法。
挖坑法快排（以升序为例）的核心思路是：先选一个基准值并把它的位置设为第一个'坑'，然后用右指针从后向前找比基准值小的元素填入左坑，左指针再从前向后找比基准值大的元素填入右坑，不断形成新坑，直到双指针相遇，最后把基准值填入最终的坑位完成分区，再递归排序左右子区间。
如果是降序排序，只需调整指针查找条件：右指针找比基准值大的元素，左指针找比基准值小的元素即可。
void QuickSort2(int* a, int left, int right) {
if (left >= right) {
return;
}
// 基准值
int key = a[left];
// 坑
int hole = left;
// 区间控制
int begin = left;
int end = right;
// 随机选 keyi 优化
int randi = left + (rand() % (right - left + 1));
swap(&a[randi], &a[hole]);
// 相等就表示已经为 Key 找到合适的坑位了
while (begin < end) {
// 右边先走，找小
while (begin < end && key <= a[end]) {
end--;
}
a[hole] = a[end];
hole = end;
// 左边后走，找大
while (begin < end && key >= a[begin]) {
begin++;
}
a[hole] = a[begin];
hole = begin;
}
// 让基准值入坑
a[hole] = key;
// [left hole - 1] hole [hole + 1 right]
// 递归子区间
QuickSort2(a, left, hole - 1);
QuickSort2(a, hole + 1, right);
}
Lomuto 前后指针版快排（以升序为例）的核心思路是：先选一个基准值，初始时 prev 和 cur 指向同一位置，然后用 cur 指针从左向右遍历，遇到比基准值小的元素时，prev 右移一位并交换二者位置；遇到比基准值大的元素时，cur 直接右移。遍历结束后，交换 prev 与基准值的位置完成分区，再递归排序左右子区间。
如果是降序排序，只需调整指针查找条件：cur 指针找比基准值大的元素即可。
void QuickSort3(int* a, int left, int right) {
if (left >= right) {
return;
}
int keyi = left;
// prev 从头开始的设计，是为了让遍历结束时，它刚好标记出基准值应处的位置
int prev = left;
int cur = left + 1;
int randi = left + (rand() % (right - left + 1));
swap(&a[randi], &a[keyi]);
while (cur <= right) {
// cur 找到了小于 key 的值
if (a[cur] < a[keyi]) {
prev++;
swap(&a[prev], &a[cur]);
cur++;
} else {
cur++;
}
}
swap(&a[prev], &a[keyi]);
keyi = prev;
// [left keyi - 1] keyi [keyi + 1 right]
QuickSort3(a, left, keyi - 1);
QuickSort3(a, keyi + 1, right);
}
在快速排序中，小区间优化是一种常见的优化策略。当递归到小区间时，继续使用快速排序可能会因为递归调用的开销而导致性能下降。此时采用插入排序等简单排序算法来处理小区间，能减少递归深度和调用次数，降低栈空间的使用，同时利用插入排序在小规模数据上的优势，从而提高快速排序的综合性能。
void InsertSort(int* a, int n) {
for (int i = 0; i < n - 1; i++) {
int end = i;
int tmp = a[i + 1];
while (end >= 0) {
if (a[end] > tmp) {
a[end + 1] = a[end];
end--;
} else {
break;
}
}
a[end + 1] = tmp;
}
}
void QuickSort3(int* a, int left, int right) {
if (left >= right) {
return;
}
// 小区间优化
if ((right - left + 1) < 15) {
InsertSort(a + left, right - left + 1);
return;
}
int keyi = left;
// prev 从头开始的设计，是为了让遍历结束时，它刚好标记出基准值应处的位置
int prev = left;
int cur = left + 1;
int randi = left + (rand() % (right - left + 1));
swap(&a[randi], &a[keyi]);
while (cur <= right) {
// cur 找到了小于 key 的值
if (a[cur] < a[keyi]) {
prev++;
swap(&a[prev], &a[cur]);
cur++;
} else {
cur++;
}
}
swap(&a[prev], &a[keyi]);
keyi = prev;
// [left keyi - 1] keyi [keyi + 1 right]
QuickSort3(a, left, keyi - 1);
QuickSort3(a, keyi + 1, right);
}
小区间优化的大小一般设置为 10~20（行业通用经验值，最常用的是 15）。
递归版快排虽逻辑清晰，但存在函数调用开销与递归深度过大导致的栈溢出风险；因此可通过手动维护栈来模拟递归调用，实现非递归版本，这也是快排非递归实现的主流方式。
非递归快排的核心思路：用栈模拟递归调用，先压入整个数组的边界，然后循环弹出边界、分区，再把左右子区间的边界压入栈，直到栈为空，排序完成。
void QuickSortNonR(int* a, int left, int right) {
stack st;
STInit(&st);
// 入 [left right] 区间
// 先入 right 是为了能正确取到 [left right] 区间
STPush(&st, right);
STPush(&st, left);
while (!STEmpty(&st)) {
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
// 小区间优化
if (end - begin + 1 < 15) {
InsertSort(a + begin, end - begin + 1);
continue;
}
// 随机选 keyi
int randi = begin + (rand() % (end - begin + 1));
swap(&a[randi], &a[begin]);
// 前后指针版本
int keyi = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end) {
if (a[cur] < a[keyi]) {
prev++;
swap(&a[cur], &a[prev]);
cur++;
} else {
cur++;
}
}
swap(&a[prev], &a[keyi]);
keyi = prev;
// 子区间处理
// [begin keyi - 1] keyi [keyi + 1 end]
if (begin < keyi - 1) {
STPush(&st, keyi - 1);
STPush(&st, begin);
}
if (keyi + 1 < end) {
STPush(&st, end);
STPush(&st, keyi + 1);
}
}
STDestroy(&st);
}
三路划分思想：把数组一次分成小于基准、等于基准、大于基准三部分，等于基准的元素直接就位不再递归，只递归左右两区，大量重复数据时效率极高，可直接替代普通快排。
void QuickSortT(int* a, int left, int right) {
if (left >= right) {
return;
}
// 小区间优化
if ((right - left + 1) < 15) {
InsertSort(a + left, right - left + 1);
return;
}
int begin = left;
int end = right;
int cur = left + 1;
// 随机选 keyi
int randi = left + (rand() % (right - left + 1));
swap(&a[randi], &a[left]);
int key = a[left];
while (cur <= end) {
if (a[cur] > key) {
swap(&a[cur], &a[end]);
end--;
// 不能直接++cur 是因为从尾部交换过来的值我们还没检查过
} else if (a[cur] < key) {
swap(&a[begin], &a[cur]);
begin++;
// cur 可以直接++是因为 begin 的值已经被我们检查过了
cur++;
} else {
cur++;
}
}
// [left begin - 1] [begin end] [end + 1 right]
QuickSortT(a, left, begin - 1);
QuickSortT(a, end + 1, right);
}
| 数据场景 | 三路划分时间复杂度 | 普通快排时间复杂度 |
|---|---|---|
| 全重复值（如全 2） | O(n) | O(n²) |
| 大量重复值（如 80% 是 2） | 接近 O(n) | O(nlogn)~O(n²) |
| 无重复值（随机数组） | O(nlogn) | O(nlogn) |
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online