博主主页：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 < end && a[end] >= a[keyi])
{
end--;
}
while (begin < end && a[begin] <= a[keyi])
{
begin++;
}
Swap(&a[end], &a[begin]);
}
Swap(&a[end], &a[keyi]);
keyi = begin;
PartSort1(a, left, keyi - 1);
PartSort1(a, keyi + 1, right);
}
4、挖坑法快速排序
挖坑法快速排序示意图如下所示：
其主要思想为：使用循环遍历数组
- 将数组中keyi所在下标的值暂存起来，其位置看作坑位，先令end从右向左遍历寻找比暂存值小的值，寻找到后，将end所指向的值放入坑中，而后end所指向的位置变成新坑。
- 再令begin从右向左寻找比暂存值大的值，寻找到后，将begin所指向的值放入坑中，而后begin所指向位置变为新坑。
- 在循环过程中若begin与end相遇，则将暂存之放入此时的坑中。
- 记录下最后一个坑的位置视作分界点，从分界点处分出两个新的子数组，进行下一轮递归，直至所分出的新数组L >= R。
- 递归结束。
其递归示意图与标题三中所展示一致，故不再做重复展示。
- 挖坑法快速排序代码如下所示：
int PartSort2(int* a, int left, int right)
{
if (left >= right)
return;
int key = a[left];
int keyi = left;
int begin = left;
int end = right;
while (begin < end)
{
while (begin < end && a[end] >= key)
{
end--;
}
a[keyi] = a[end];
keyi = end;
while (begin < end && a[begin] <= key)
{
begin++;
}
a[keyi] = a[begin];
keyi = begin;
}
a[keyi] = key;
PartSort2(a, left, end - 1);
PartSort2(a, end + 1, right);
}
5、前后指针法快速排序
前后指针法快速排序示意图如下所示：
其主要思想为：
-
定义指针prev指向数组开始位置，cur指向数组开始第二个位置，并使用keyi记录数组中用作比较的数。
-
令cur向数组右端遍历，若出现小于keyi的数则停止遍历，转为prev进行遍历。
-
令prev向数组右端遍历，若出现大于keyi的数，则令其与cur交换位置，而后继续进行cur的遍历，直至cur达到数组末尾的下一位（即越界）。
-
当cur越界后将当前prev所代表的值与key所代表值进行交换，并将prev所处位置视为分界点，从分界点处分出两个新的子数组进行递归，直至所递归的数组L >= R。
-
递归结束。
其递归示意图与标题三中所展示一致，故不再做重复展示。
-
前后指针法快速排序代码如下所示：
void Swap(int* p1, int* p2)
{
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 <= right)
{
if (a[cur] < a[key] && a[++prev] != a[key])
Swap(&a[cur], &a[prev]);
cur++;
}
Swap(&a[key], &a[prev]);
PartSort3(a, left, prev - 1);
PartSort3(a, prev + 1, right);
}
6、非递归法快速排序
非递归的方法实现快速排序，其原理是使用栈来模拟代码在系统中的栈中的递归过程，也可称之为伪递归。
有关栈的相关内容可在下方查看：
栈（使用顺序表构建）
其主要思想为：
-
使用栈来模拟系统中栈的功能，将数组的右左下标依次传入栈中，每一次取其栈顶位置数据分别作为单词快排的目标数组左下标和右下表（每一次取值后需删除栈顶元素）。
-
在单次快排完成后判断其在分段点所分两个新的子数组左右下标是否合理（是否存在左下标大于或等于右下标的行为），若不存在则将右子数组右左下标依次推入栈中，而后将左子数组右左下标依次推入栈中，进行下一轮循环。
-
其循环判断条件为栈中是否为空。
-
有关其入栈顺序可不做过多研究，但要保证的前提是所取出数值需与操作数组的左右下标相对应，以避免不必要麻烦。
-
非递归法快速排序代码如下所示：
void Swap(int* p1, int* p2)
{
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 <= end)
{
if (a[cur] < a[key] && a[++prev] != a[key])
Swap(&a[cur], &a[prev]);
cur++;
}
Swap(&a[key], &a[prev]);
if (prev + 1 < end)
{
STPush(&s, end);
STPush(&s, prev + 1);
}
if (begin < prev - 1)
{
STPush(&s, prev - 1);
STPush(&s, begin);
}
}
STDestroy(&s);
}
7、快速排序的优化
此优化可适用于任意方法的可快速排序。
在日常生活中，我们所使用排序功能的目标对象可能不会想日常练习中那样少，或许是一个非常庞大的数量，且其所提供的数据可能在原本基础上就有部分有序化，例如所给的大量数据中第一位为最小值或最大值，而这样的数据我们从一开始就进行快速排序的话，会让end从末尾一直遍历到数据首部或begin从数据首部一直遍历到末尾，拥有时间复杂度上的浪费，所以我们提出了一个 三数取中的方法来进行优化，且针对于大量数据，当所处理数据的子数据数量过少时，我们还是用快速排序的方法有点大材小用了，故针对于此我们也提出了 少量数据另谋他法的方法应对。
7.1 三数取中
针对于所给目标数组第一位即为最小值或最大值而导致的时间复杂度浪费，我们可以取其数组首位，中位，末位三个数进行比较，选取其中处于中间位置的数，令其与数据首位进行交换。
- 其代码如下所示：
int GetMid(int* a, int left, int right)
{
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] < a[right])
return mid;
else if (a[right] < a[left])
return left;
else
return right;
}
}
7.2 少量数据另谋他法
对于根据分界点所得到的新子数组，若其数据量较小，我们还是用快速排序的化有些大材小用，故当数据量较小时，我们一般使用其他排序方法，如冒泡排序或插入排序等，进行快速的排序。
- 其代码如下所示
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - i - 1; j++)
{
if (a[j] > a[j + 1])
Swap(&a[j], &a[j + 1]);
}
}
}
if (right - left < 10)
{
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 < 10)
{
BubbleSort(a, right - left + 1);
}
else
{
int prev = left;
int cur = prev + 1;
int key = left;
while (cur <= right)
{
if (a[cur] < a[key] && a[++prev] != a[key])
Swap(&a[cur], &a[prev]);
cur++;
}
Swap(&a[key], &a[prev]);
PartSort3(a, left, prev - 1);
PartSort3(a, prev + 1, right);
}
}
8、快速排序的特性总结
快速排序的特性总结：
- 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定
9、结语
十分感谢您观看我的原创文章。
本文主要用于个人学习和知识分享，学习路漫漫，如有错误，感谢指正。
如需引用，注明地址。
