目录
前言
在浩瀚的计算机算法世界中，排序算法无疑扮演着基石性的角色。从早期的数据处理到现代的机器学习，高效的排序能力始终是衡量程序性能的重要指标。在众多排序算法中，“快速排序”（Quick Sort）以其卓越的平均性能、简洁的递归结构以及在实际应用中的广泛普及，赢得了算法“皇帝”的美誉。它不仅仅是一种将无序序列变为有序序列的工具，更是一种分治策略思想的完美体现。
本篇文章将带领大家深入C语言的殿堂，揭开快速排序算法的神秘面纱。我们将从最基础的原理出发，详细解读快速排序的核心思想——“分治法”，并逐步探讨其递归实现的精妙之处。通过C语言的简洁与高效，我们将亲手实现一个功能完备的快速排序函数，并对其中的关键步骤进行详细注释与解析。无论您是初学者，还是希望深化对排序算法理解的开发者，相信本文都能为您提供一次清晰且富有洞察力的学习体验。让我们一同踏上这场算法之旅，领略快速排序的独特魅力！
一、了解快速排序算法
1.1、核心思想
任取待排序元素序列中的某个元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中的所有元素均大于基准值。其左右子序列重复该过程。（有点像二叉树的味道）
1.2、算法图解
例如，我有这样一个序列：
经过某些操作找到一个基准值：
使得基准值左边的元素都比基准值要小，右边的元素都比基准值大，同理，再在左右两个子序列中继续寻找基准值：
一直到最后元素都出现在相应的位置上为止（也就是最后左右子序列就只剩一个元素的时候）
二、快速排序的代码实现
2.1、主干代码
通过上面的介绍和图解，很容易让人联想到二叉树，因此，在实现快速排序的时候，我们可以使用递归，那么，具体操作是什么样的？
我们设置两个参数 left 和 right 用来表示在 [left , right] 的范围内寻找基准值：
查找基准之后，继续查找左右子序列的基准值：
找到了左右子序列的基准值之后再继续查找各自的子序列的基准值，直到 left 和 right 重合为止：
因此，代码可以写成：
void QuicSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//找基准值的下标 keyi
int keyi = _QuicSort(arr, left, right);
//递归，进入到左右子序列
QuicSort(arr, left, keyi - 1);
QuicSort(arr, keyi+1, right);
}2.2、hoare 版本的找基准值
快速排序的主干已经写完了，那么，中间的找基准值的函数如何实现呢？其实，找基准值的方法有很多，我们不着急，一个一个来学习，首先来看看 hoare 版本的找基准值
如图：先假设 基准值的下标为 left ，然后依照以下两个规则进行：
（1）left 向右走，找比基准值大的元素
（2）right 向左走，找比基准值小的元素
（3）left 和 right 都找到之后，两个元素互换位置
步骤一：left 和 right 找到各自的目标：
步骤二：随后，left 和 right 代表的元素互换位置：
步骤三：left++ ，right-- 刷新位置，进行下一轮的寻找各自目标，直到 left 大于 right 为止，作者举得例子，这一步就已经 left 大于 right 了
步骤四：将 基准值和 right 互换位置，找到新的基准值：
随后进行左右子序列的基准值找法，
由于举例的特殊性，该例子到这里就结束了。下面来看看代码的细节：
//找基准值
int _QuicSort(int* arr, int left, int right)
{
int keyi = left; //假设基准的下标在最左边
left++; //left 和 right 寻找的是基准值意外的元素，因此left++直接跳过基准值‘
while (left <= right)
{
while (arr[right] > arr[keyi] && left <= right)
{
right--;
}
while (arr[left] < arr[keyi] && left <= right)
{
left++;
}
//交换left 和right 的元素位置
//如果left 已经大于 right，则需要跳过交换！
if (left <= right)
{
Swap(&arr[left], &arr[right]);
left++;
right--;
}
}
//走到这里，说明left 已经大于 right ，需要将right和keyi交换位置
Swap(&arr[right], &arr[keyi]);
//交换完后，right就是基准值的下标
return right;
}找基准值这里，主要细节就在于 left 和 right 相遇的情景：
如图，left 和 right 相遇在序列中间，由于我们每次循环完成后，需要left++， right--，导致right和left 相遇在一个大于基准值的地方，而我们最后基准值是和right直接换位置的，因此，left 和 right 相遇后不能跳出循环！
那么就变成了下面的样子：
此时，left 和 right 都找到了自己的目标，此时 left 和 right 的元素还能互换位置吗？答案明显是不能的。所以在每次循环末尾，我们在交换前需要判断 left 是否 <= right！
2.3、挖坑法找基准值
先来看看图解：
第一步：依然假设第一个元素为基准值，并且为坑，将其保存在一个零时空间 key 中
第二步：从右向左寻找比基准值小的元素，并将其放入坑中，那么该元素原来的位置将变成新的坑
第三步：从左向右寻找比基准值大的元素，将其放入坑中，那么该元素原来的位置将变成新的坑
第四步：重复第二、三步，直到 left 大于 right为止， 此时，再将最开始的元素放入到坑中，成为基准值
下面来看看代码如何实现：
//找基准值--挖坑法
int _QuicSort(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole]; //将初始坑中的元素存入key中
while (left < right)
{
while (arr[right] >= key && left < right)
{
right--;
}
//将right代表的元素放入坑中
arr[hole] = arr[right];
hole = right;
while (arr[left] <= key && left < right)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
//再将 key 中的元素放回坑中，作为基准值
arr[hole] = key;
return hole;
}这里left 和 right 判断时必须要加上等于号，避免因为元素等于基准值而导致的死循环，举个例子：
第一步：
第二步：
因为只有满足循环条件才可以更新left 和right 的位置，但是，如果不加等号，那么left 和 right就无法进入循环，就无法更新自己的位置，而且，由于 key 的值等于 left / right 的值，就算right将其填入坑，更新的也是坑的位置，而right的位置和key的值依旧没变，从而进入死循环
2.4、lomuto 前后指针找基准值
如图，设置两个指针，prev 和 cur ：
还是一样，先假设基准值为首元素，然后 cur 指向的元素与基准值比较，如果cur指向的元素比基准值小，先++prev ，再 cur 和 prev 交换值，最后++cur ; 如果cur指向的元素不比基准值小 ，则直接++cur
一直到cur走到序列末尾为止，然后再将基准值和prev指向的元素交换位置，此时，prev就是新的基准值下标了
步骤演示：
代码实现：
int _QuicSort3(int* arr, int left, int right)
{
assert(arr);
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
Swap(&arr[prev], &arr[cur]);
}
//无论哪种情况，都要cur++ ，直接放外面就行
cur++;
}
Swap(&arr[keyi], &arr[prev]);
return prev;
}这里 if 条件加了一个 ++prev ！= cur ，因为++prev 后如果和cur相等，那么交换了和没交换是一样的，所以干脆放到条件里，减轻负担。
三、时间复杂度
3.1、快速排序主干的时间复杂度
前面说到，快速排序跟二叉树很像，因此，快速排序主干的时间复杂度为O(logN)
3.2、找基准值的时间复杂度
这是hoare版本找基准值的代码，从代码上看，虽然有个嵌套循环，但是实际上只是把序列遍历了一遍，因此时间复杂度是 O(N)
所以最后快速排序的时间复杂度为 O(NlogN)
四、非递归的快速排序
4.1、基础介绍
上述的快速排序的主干是递归实现的，运行的时候会创建很多函数栈帧，那么有没有什么方法可以避免呢？
有的有的，用前面学到的数据结构--栈
如图，将left 和 right 入栈
然后再依次将两个元素出栈，作为新序列的左右范围 [left , right] ，等找到基准值之后，在将左右子序列的范围入栈，然后在出栈，循环操作，直到栈为空
下面是一些图解：
通俗点讲，就是每次把子序列的左右范围放入栈中，然后在提取就行。这有点像二叉树的层序遍历，递归遍历是深度优先，而这个是广度优先。
4.2、代码实现
void QuickSortNonR(int* a, int left, int right)
{
stack st; //创建一个栈
StackInit(&st); //栈初始化
StackPush(&st, right); //压栈
StackPush(&st, left);
while (!StackEmpty(&st))
{
int begin = StackTop(&st);
StackPop(&st);
int end = StackTop(&st);
StackPop(&st);
//在[begin, end]范围内找基准值
int keyi = _QuicSort(a, begin, end);
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (keyi - 1 > begin)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestory(&st);
}下面是栈的结构：
typedef int SDataType;
typedef struct stack
{
SDataType* arr;
int top;
int capacity;
}stack;好，这里要注意一个细节，栈只能先入先出，所以要想清楚入栈的顺序哦！当然，我觉得用队列也是可以实现这个效果的，读者可以自行下去尝试
4.3、时间复杂度
根据上面的代码可以看到，有一个外循环，而这个循环是通过栈来“层次遍历”这个二叉树节点的，因此，外层循环的时间复杂度为O(N)
而内层的找基准值的时间复杂度上文也有提及 ，为O(N)，因此，采用非递归实现的时间复杂度为O(N^2)，当然，这里值得是最坏的情况
结语
至此，我们已经完整地学习并实现了一个C语言版本的快速排序算法。通过深入理解其“分而治之”的核心思想，以及精巧的递归和分区实现，我们可以体会到算法设计的美妙与力量。快速排序以其平均时间复杂度为 O(n log n) 的高效表现，在绝大多数场景下都展示出卓越的性能，是工业界和学术界广泛应用的排序算法之一。尽管在最坏情况下（如输入数据已完全有序或逆序，且基准选择不当）其性能会退化到 O(n^2)，但通过优化基准选择（例如随机选择基准、三数取中法），可以有效避免这种情况的发生。
掌握快速排序不仅仅是学会一个算法，更是习得一种解决问题的分治思维模式。这种思维方式在解决其他复杂问题时也常常能发挥关键作用。希望本文能帮助您对快速排序有更深刻的理解，并为您的编程学习之路点亮一盏明灯。在未来的编程实践中，愿您能灵活运用所学，编写出更加高效、健壮的代码！