leetcodeT912-快排优化-三路划分

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这一题的测试用例太针对快排了

所以快排被欺负的很惨

以上就是leetcodeT912针对快排的三路划分优化的讲解,希望能对大家有所帮助!