📑前言
什么是快排?快排的速度到底有多快呢?它们的思想和实现是什么样的?
本文会对这快速排序进行详解,绝对细致入微!让你彻底搞懂快排!
🌤️快速排序的概念
☁️快速排序的由来
英国计算机科学家Tony Hoare在1960年为了解决计算机上的排序问题,提出了快速排序的算法,最初是为了在英国的英尔兰电子公司(ELLIOTT Brothers)的快速硬件上实现高效的排序算法。
☁️快速排序的思想
快速排序的主要思想是分治法,将一个大问题分割成小问题,解决小问题后再合并它们的结果。
☁️快速排序的实现步骤
- 从待排序的数组中选择一个元素,称之为枢纽元(pivot)。
- 将数组中小于枢纽元的元素移到枢纽元的左边,将大于枢纽元的元素移到枢纽元的右边,这个过程称为分区(partition)。
- 递归地对枢纽元左边的子数组和右边的子数组进行排序。
- 当所有子数组都有序时,整个数组就自然有序了。
🌤️快速排序(递归版)
☁️快排主框架
void QuickSort(int* a, int left, int right)
{
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
if (right <= left)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
//int keyi = PartSort1(a, left, right);
//int keyi = PartSort2(a, left, right);
int keyi = PartSort3(a, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, keyi-1) 和 [keyi+1, right)
// 递归排[left, keyi-1)
QuickSort(a, left, keyi - 1);
// 递归排[keyi+1, right)
QuickSort(a, keyi + 1, right);
}
上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,在写递归框架时想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
☁️Hoare版本快排
⭐代码与图解
int PartSort1(int* a, int left, int right)
{
//三数取中(优化)
//int keyi = NumBers(a, left, right);
//Swap(&a[keyi], &a[left]);
int key = left;
while (left < right)
{
while (left < right && a[left] <= a[right])
{
right--;
}
while (left < right && a[left] <= a[right])
{
left++;
}
Swap(&a[left], &a[right]);
}
Swap(&a[left], &a[key]);
return left;
}
⭐代码解析:
- 首先,定义一个变量key,用于保存基准值的下标,初始值为left。
- 进入一个循环,循环条件是left < right,即左右指针没有相遇。
- 在循环中,首先从右边开始,找到第一个小于等于基准值的元素的下标,将right指针左移,直到找到符合条件的元素或者left和right相遇。
- 然后从左边开始,找到第一个大于基准值的元素的下标,将left指针右移,直到找到符合条件的元素或者left和right相遇。
- 如果left < right,说明找到了需要交换的元素,将a[left]和a[right]交换位置。
- 重复步骤3到步骤5,直到left和right相遇。
- 最后,将基准值a[key]和a[left]交换位置,将基准值放在正确的位置上。
- 返回分割点的下标left。
实现了一次快速排序的分割操作,将数组分成两部分,左边的元素都小于等于基准值,右边的元素都大于基准值。然后再通过递归调用这个函数,这就是hoare版的快排。
☁️挖坑法
⭐代码与图解
int PartSort2(int* a, int left, int right)
{
//三数取中优化
//int keyi = NumBers(a, left, right);
//Swap(&a[keyi], &a[left]);
int key = a[left];
int hole = left;//为第一个坑
while (left < right)
{
while (left < right && key <= a[right])
{
--right;
}
a[hole] = a[right];
hole = right;
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;
}
a[hole] = key;
return hole;
}
⭐代码解析:
- 定义一个变量key,用于保存基准值,初始值为a[left]。
- 定义一个变量hole,用于保存空洞的位置,初始值为left。
- 进入一个循环,循环条件是left < right,即左右指针没有相遇。
- 在循环中,首先从右边开始,找到第一个小于基准值的元素的下标,将right指针左移,直到找到符合条件的元素或者left和right相遇。
- 将a[right]的值赋给a[hole],将空洞的位置移动到right。
- 然后从左边开始,找到第一个大于基准值的元素的下标,将left指针右移,直到找到符合条件的元素或者left和right相遇。
- 将a[left]的值赋给a[hole],将空洞的位置移动到left。
- 重复步骤4到步骤7,直到left和right相遇。
- 最后,将基准值key放入空洞的位置a[hole],将基准值放在正确的位置上。
- 返回空洞的位置hole。
同样实现了将数据分成两部分,左边的元素都小于等于基准值,右边的元素都大于基准值。
☁️双指针法
⭐代码与图解
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
//三数取中优化
//int midi = NumBers(a, left, right);
//Swap(&a[left], &a[midi]);
int prev = left;
int cur = prev + 1;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
{
Swap(&a[prev], &a[cur]);
}
++cur;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
⭐代码解析
- 定义两个指针prev和cur,分别指向left和left+1。
- 定义一个变量keyi,用于保存基准值的下标,初始值为left。
- 进入一个循环,循环条件是cur <= right,即cur指针没有越界。
- 在循环中,如果a[cur]小于基准值a[keyi],则将prev指针右移一位,并交换a[prev]和a[cur]的值,保证prev指针之前的元素都小于基准值。
- 将cur指针右移一位。
- 重复步骤4到步骤6,直到cur指针越界。
- 最后,将基准值a[keyi]和a[prev]交换位置,将基准值放在正确的位置上。
- 返回分割点的下标prev。
同样实现了将数据分成两部分,左边的元素都小于等于基准值,右边的元素都大于基准值。
☁️三数取中优化
⭐为什么要三数取中?
-
三数取中是为了选择一个更好的基准值,以提高快速排序的效率。在快速排序中,选择一个合适的基准值是非常重要的,它决定了每次分割的平衡性。
-
快速排序是通过一趟排序将待排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的小,然后再对这两部分分别进行快速排序,递归地进行下去,直到整个序列有序。
-
如果每次选择的基准值都是最左边或最右边的元素,那么在某些情况下,快速排序的效率可能会降低。例如,当待排序序列已经有序时,如果每次选择的基准值都是最左边或最右边的元素,那么每次分割得到的两个子序列的长度差可能会非常大,导致递归深度增加,快速排序的效率降低。
-
而通过三数取中的优化,可以选择一个更好的基准值,使得每次分割得到的两个子序列的长度差更小,从而提高快速排序的效率。
-
具体来说,三数取中的优化是选择待排序序列的左端、右端和中间位置的三个元素,然后取它们的中值作为基准值。这样选择的基准值相对于最左边或最右边的元素,更接近整个序列的中间位置,可以更好地平衡分割后的两个子序列的长度,从而提高快速排序的效率。
-
通过三数取中的优化,可以减少递归深度,提高分割的平衡性,使得快速排序的效率更稳定,适用于各种不同的输入情况。
⭐三数取中代码实现
//三数取中
int NumBers(int* a, int left, int right)
{
int mid = (left + right) / 2;
// left mid right
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[left] > a[right]) // mid是最大值
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right]) // mid是最小
{
return left;
}
else
{
return right;
}
}
}
☁️小区间优化
⭐什么是区间优化?
小区间优化是指在快速排序中,当待排序的子序列的长度小于一定阈值时,不再继续使用快速排序,而是转而使用直接插入排序。
⭐小区间优化代码实现
void QuickSort(int* a, int left, int right)
{
if (right <= left)
return;
if(right - left + 1 > 10)
{
int keyi = PartSort3(a, left, right);
QuickSort(a, left, keyi - 1);
QuickSort(a, keyi + 1, right);
}
else
{
InsertSort(a + left,right - left + 1);
}
}
⭐小区间优化的好处
- 减少递归深度:使用插入排序来处理较小的子序列,可以减少递归的深度,从而减少了函数调用的开销。
- 提高局部性:插入排序是一种稳定的排序算法,它具有良好的局部性,可以充分利用已经有序的部分序列。对于较小的子序列,插入排序的效率更高。
- 减少分割次数:对于较小的子序列,使用插入排序可以减少分割的次数。快速排序的分割操作需要移动元素,而插入排序只需要进行元素的比较和交换,因此在较小的子序列中使用插入排序可以减少分割操作的次数。
小区间优化可以在一定程度上提高快速排序的性能。它通过减少递归深度、提高局部性和减少分割次数来优化算法的效率,特别适用于处理较小的子序列。
🌤️快速排序(非递归版)
这里需要借助栈的来实现非递归.关于栈详情见:数据结构剖析–栈
// 快速排序 非递归实现
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);
int keyi = PartSort3(a, begin, end);
if (keyi + 1 < end)
{
StackPush(&st, end);
StackPush(&st, keyi + 1);
}
if (begin < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, begin);
}
}
StackDestroy(&st);
}
☁️代码解析
- 将整个序列的起始和结束位置入栈。然后,进入循环,不断从栈中取出子序列的起始和结束位置。
- 在每次循环中,通过PartSort3函数将当前子序列分割成两部分,并得到基准值的下标keyi。如果基准值右边的子序列长度大于1,则将右边子序列的起始和结束位置入栈。如果基准值左边的子序列长度大于1,则将左边子序列的起始和结束位置入栈。
- 循环继续,直到栈为空,表示所有的子序列都已经排序完成。
通过使用栈来模拟递归的过程,非递归实现避免了递归调用的开销,提高了快速排序的效率。
🌤️快速排序的特性总结
-
快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
-
时间复杂度:O(N*logN)
-
空间复杂度:O(logN)
-
稳定性:不稳定
🌤️全篇总结
本章对快排从其思想到实现,一步步由浅入深的讲解,相信聪明的你看到这里已经对快排有一个明白的理解了!
看到这里希望给博主留个:👍点赞🌟收藏⭐️关注!文章来源:https://www.toymoban.com/news/detail-742683.html
文章来源地址https://www.toymoban.com/news/detail-742683.html
到了这里,关于【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!