C算法
快速排序原理与实现详解
快速排序是一种基于分治思想的高效排序算法。核心步骤包括选择基准值、分区操作及递归处理子区间。常见划分方式有 Hoare 版本、挖坑法和前后指针法。优化手段包含三数取中法避免最坏情况、小区间切换插入排序提升效率以及三路划分处理重复元素。时间复杂度平均为 O(N log N)，最坏 O(N^2)，空间复杂度 O(log N)。该算法不稳定，支持递归与非递归实现。
快速排序是一种基于分治思想的高效排序算法。核心步骤包括选择基准值、分区操作及递归处理子区间。常见划分方式有 Hoare 版本、挖坑法和前后指针法。优化手段包含三数取中法避免最坏情况、小区间切换插入排序提升效率以及三路划分处理重复元素。时间复杂度平均为 O(N log N)，最坏 O(N^2)，空间复杂度 O(log N)。该算法不稳定，支持递归与非递归实现。
- 在数组中选择一个基准值（key）；
- 将数组划分为两部分：左边比 key 小，右边比 key 大；
- 递归排序左右两部分；
- 最终合并得到有序序列。
在这里，最重要的就是将数组划分为两部分：左边比 key 小，右边比 key 大。 对于将数组划分为两部分的方法有三种，本质思想都是一样的，但实现的方法却有点不同，我们来看一下：
以下面一组数据为例，我们假设 key 的值是最左边的值。
看了这个动图之后，可知，它是定义了两个下标（L 与 R），分别从两侧开始找，R 先走，找到比 key 小的值，停下来；L 开始走，找到比 key 大的值，停下来，交换对应的值即可，然后继续重复，直到两者相遇，交换相遇点与 key 的值即可，这就是 Hoare 的思想。还是很好理解的，但是这个方法会导致很多人有疑问？我也重点标记了。
答疑解惑：为什么两者相遇，交换相遇点与 key 的值？那万一此时的值比 key 大呢？
在这里我们就要明白一个点，两者会以什么方式相遇，简单，要么 L 在移动的时候遇到了 R，要么 R 在移动的时候遇到了 L。
L 在移动的时候遇到了 R 的情况： 由于是R 先走的缘故，所以 R 此时指向的是比 key 小的值，此时 L 遇到了 R，相遇点即为比 key 小的值。
R 在移动的时候遇到了 L 的情况： 此时 L 停留在上次交换的位置，上次交换的是比 key 小的值，即相遇点为比 key 小的值，也有可能 L 停留在 key 的位置。结果都是一样。
为什么 R 先走？ 其实，上面的解释已经有了答案。我们也可以看看如果 L 先走的话，会发生什么情况：
我们会发现，当 L 先走时，可以把 key 设在右边。
那现在我们来进行代码的完成。
int _QuickSort(int* a, int left, int right) {
int key = left; // 选择最左边为基准
while (left < right) {
while (left < right && a[right] >= a[key]) right--;
while (left < right && a[left] <= a[key]) left++;
Swap(&a[right], &a[left]);
}
Swap(&a[left], &a[key]); // 将基准值放到正确位置
return left; // 返回基准值最终位置
}
现在我们完成了快速排序中的单次划分，上面我们说过，递归排序左右两部分，怎么完成呢，来分析：
也就是说，左右两部分和首次排序的思想是一样的，然后，左右两部分的左右两部分又相同，所以对于递归已经发现清楚了，下面来完成代码吧：
void QuickSort(int* a, int left, int right) {
if (left >= right) // 递归终止条件：区间只有一个元素或为空
return;
int mid = _QuickSort(a, left, right); // 划分操作，返回基准值的最终位置
QuickSort(a, left, mid - 1); // 递归排序左半部分
QuickSort(a, mid + 1, right); // 递归排序右半部分
}
至此，快排的基本框架完成，为什么说基本框架，因为快排后序会有多种优化，后面会说。下面这两种方法我们可以来看一下思想，代码很简单。
这两个我们了解一下思想即可。霍尔法虽然在实现上稍复杂，但其优异的性能表现使其成为大多数标准库实现的选择。
对于我们实现的快排，问题在于 key 的取值，如果 key 的取值大多数接近数组最小值，极端一点，就会导致性能下降。 所以我们使得 key 的取值尽量靠近中间值。便有了三数取中法选择基准值。
三数取中法，顾名思义，选择三个数的中间值，看代码
int GetMidi(int* a, int left, int right) {
int midi = right + (left - right) / 2;
if (a[midi] > a[left]) {
if (a[midi] < a[right])
return midi;
else if (a[left] < a[right]) // a[midi] >= a[right]
return right;
else
return left;
} else // a[midi] <= a[left] {
if (a[left] < a[right])
return left;
else if (a[midi] < a[right]) // a[left] >= a[right]
return right;
else
return midi;
}
}
对于快排来说，在数据量较小时，就没有使用的必要了，所以在数据量较小时选择插入排序即可。代码实现
void QuickSort(int* a, int left, int right) {
if (left >= right) // 递归终止条件：区间只有一个元素或为空
return;
if (right - left + 1 <= 10) // 数据量较小时用插入排序
{
InsertSort(a + left, right - left + 1);
return;
}
int mid = _QuickSort(a, left, right); // 划分操作，返回基准值的最终位置
QuickSort(a, left, mid - 1); // 递归排序左半部分
QuickSort(a, mid + 1, right); // 递归排序右半部分
}
对于快排，我们还需要会用非递归实现。
这个时候，思想还是递归的思想，只是，我们要用到栈了：对于快排的递归来说，每次转入的都是 left 和 right。那我们对于非递归来说，每次把 left 和 right 都传入栈中，每次当 left 和 right 出栈进行操作后，把划分后的区间又入栈，即可。
停止条件：'递归终止条件：区间只有一个元素或为空'，那我们非递归对于 left >= right 是不入栈即可或者出栈后不进行操作即可。
代码完成：
void QuickSortNonR(int* a, int left, int right) {
Stack st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (StackEmpty(&st) != 0) {
right = StackTop(&st);
StackPop(&st);
left = StackTop(&st);
StackPop(&st);
if (right <= left) continue;
int mid = _QuickSort(a, left, right); // 以基准值为分割点，形成左右两部分：[left, mid-1 ] 和 [mid+1, right]
StackPush(&st, mid + 1);
StackPush(&st, right);
StackPush(&st, left);
StackPush(&st, mid - 1);
}
StackDestroy(&st);
}
对于快排的时间复杂度一般为 O(N log N)，看下图递归树。假设基准值每次都可以取到中间。
**但是快排最坏能到 O(N^2)，当数组完全有序（正序或逆序），每次选择的基准值都是最小或最大元素。但是一般少发生且可以避免。**毕竟快排还有很多优化。
如上图，递归为 O(log N)，非递归也为 O(log N)，非递归我们可以看做二叉树的前序遍历，一直从上图的左边下去。简单点，就是，出一个，带两个，持续 logN 次。
不稳定，相同元素的相对顺序可能改变。
快速排序通过'选基准、分区间、递归处理'的分治思想，实现了高效的排序。它的核心优势是平均时间复杂度接近 O（N log N），并且额外空间开销较小，因此被广泛应用于标准库中。虽然在极端情况下可能退化为 O（N²），而且本身不稳定，但通过三数取中、小区间转插排、三路划分等优化手段，可以在实际场景中保持优秀表现。递归和非递归两种实现方式各有应用，递归更直观，非递归更适合工程。总体来看，快速排序因高效与实用，成为排序算法中的'明星'。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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