1.前言
因为快排的名声太大
并且快排在某些场景下比较慢,所以leetcode"修理"了一下快排
特意设计了一些专门针对快排的测试用例
所以用快排过不了这一题
2.为什么需要三路划分的优化?
我们遇到了第一个为难快排的测试用例全是重复值2
我们发现快排在遇到全是重复值的数据时,
这里以左右指针法为例
每次右指针从右向左找小时都要跑到左指针位置处
然后进行交换,递归
每次都只能把那个重复数据2放到当前递归区间的起始位置,就像是冒泡排序一样每次只能冒一个数到对应位置,但是冒泡排序好歹还能有一个优化(没有发生数据交换时即为有序,排序结束),可是这时快排连优化都没有
退化到了O(n^2)的时间复杂度
3.三路划分的思想及举例画图
这是整个过程,大家也可以自己对照三种情况画一下
一趟三路划分
前:
后:
我们发现:
一趟三路划分后整个数组被分为三个部分:
假设区间左端点:begin,右端点:end
[begin,l-1]:这一段上区间的值小于key
[l,r] :这一段上区间的值等于key
[r+1,end]:这一段上区间的值大于key
等于key的那一段区间不需要递归了,因为它们已经位于它们该在的地方了
接下来只需要递归[begin,l-1],[r+1,end]即可
4.三路划分的代码实现
//三路划分
void QuickSort(int* a, int begin, int end)
{
if(begin>=end)
{
return;
}
int keyIndex=GetMidIndex(a,begin,end);
Swap(&a[begin],&a[keyIndex]);
int key=a[begin];
int left=begin,right=end,cur=begin+1;
while(cur<=right)
{
if(a[cur]<key)
{
Swap(&a[cur],&a[left]);
cur++;
left++;
}
else if(a[cur]==key)
{
cur++;
}
else
{
Swap(&a[cur],&a[right]);
right--;
}
}
QuickSort(a,begin,left-1);
QuickSort(a,right+1,end);
}
所以我们可以发现,三路划分之后,数组中重复越多,我们快排就越快
因为重复值直接就跳过了
对于那个测试用例来说
第一趟排序之后left还是等于begin,right还是等于end
所以再往下递归就会触发begin>=end这个条件,就会直接返回
所以达到了O(n)的时间复杂度
所以对于这个测试用例来说已经比较快了
5.三数取中修改
但是:
尽管我们通过了所有的测试用例,但是因为耗时太长leetcode直接针对快排
那么怎么办,怎么过呢?
我们去掉三数取中优化,看一下是哪个测试用例对我们的针对
这里我们打印了一下数组开头,中间,结尾的那三个数
这个题目最大值是50000,
这个测试用例最大值是上万,而我们三数取中取出来的是7500,相对来说偏小了
所以我们要对三数取中的mid搞一个随机数
只需要在三数取中的代码中给mid一个随机值即可
这里设置随机数种子,避免出现rand函数产生的重复值不变的情况
尽管我们过是过了,但是Leetcode这一题的测试用例太针对快排了
所以快排被欺负的很惨
文章来源：https://www.toymoban.com/news/detail-721210.html
以上就是leetcodeT912针对快排的三路划分优化的讲解,希望能对大家有所帮助!文章来源地址https://www.toymoban.com/news/detail-721210.html
到了这里，关于leetcodeT912-快排优化-三路划分的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
