|
P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。
P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。
博主主页：LiUEEEEE C语言专栏 数据结构专栏 力扣牛客经典题目专栏 
目录
1、快排的基本思想2、快排的四种实现方法3、Hoare快速排序4、挖坑法快速排序5、前后指针法快速排序6、非递归法快速排序7、快速排序的优化7.1 三数取中7.2 少量数据另谋他法
8、快速排序的特性总结9、结语
1、快排的基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
2、快排的四种实现方法
快速排序有多种实现方法，其具体体现如下：
Hoare快速排序挖坑法快速排序前后指针法快速排序非递归法快速排序
下文将对上述四种实现方法依次进行讲解。
3、Hoare快速排序
Hoare快速排序的示意图如下所示：
 其主要思想为：使用循环遍历数组
将所给数组的第一个值的下标给予key变量和begin变量（下文中统一为keyi，方便理解其为下标地址而非数组成员值），将数组最后一个值的下标给予end变量。开始执行是令end向数组左侧遍历，寻找数值比数组下标为keyi的值小的数，若未寻找到，则继续向左侧遍历，若寻找到，则停止遍历，转而为begin向数组右侧遍历。begin向数组右侧遍历，寻找数值比下标为keyi的值大的数，若寻找到，则交换数组中下标为end和begin的值。若在begin与end遍历过程中两变量出现相等的情况，则退出循环，将数组中下标为keyi和end的值交换。记录下交换位置，令其为新的分割点，利用递归的思想，将数组根据新分割点分割的左右两次子数组进行递归，直到出现新数组中L >= R。递归结束。 其递归思想的图示如下，示例：成员为4,2,6,5,7,1,3,8,10,9的数组。  当记录交换位置为3，即会有新的子数组【0，2】【4，9】，使用新数组进行递归。
 递归方法如上图所示（除3外其余递归交换位置为虚构，需实际计算得到）。
Hoare快速排序代码如下
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int PartSort1(int* a, int left, int right)
{
if (left >= right)
return;
int begin = left;
int end = right;
int keyi = left;
while (begin
end--;
}
while (begin
if (left >= right)
return;
int key = a[left];
int keyi = left;
int begin = left;
int end = right;
while (begin
end--;
}
a[keyi] = a[end];
keyi = end;
while (begin
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
int PartSort3(int* a, int left, int right)
{
if (left >= right)
return;
int prev = left;
int cur = prev + 1;
int key = left;
while (cur
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void QuickSortNonR(int* a, int left, int right)
{
ST s;
STInit(&s);
STPush(&s, right);
STPush(&s, left);
while (!STEmpty(&s))
{
int begin = STTop(&s);
STPop(&s);
int end = STTop(&s);
STPop(&s);
int prev = begin;
int cur = prev + 1;
int key = begin;
while (cur
STPush(&s, end);
STPush(&s, prev + 1);
}
if (begin
int mid = (left + right) / 2;
if (a[left] > a[mid])
{
if (a[mid] > a[right])
return mid;
else if (a[right] > a[left])
return left;
else
return right;
}
else
{
if (a[mid]
for (int j = 0; j
BubbleSort(a, right - left + 1);
}
至此快速排序的优化结束，其完整代码如下所示（前后指针法快速排序）：
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
int mid = GetMid(a, left, right);
Swap(&a[left], &a[mid]);
if (right - left
int prev = left;
int cur = prev + 1;
int key = left;
while (cur |