数据结构——三路划分（快排优化）

• 算法结构

d8c27d0acd1a422aa5e196d3d08ce561.png

刷Leetcode时遇到的问题，用普通的快排去跑，发现有问题。

099021bb94dd4135998075128b463e14.png

 普通的Hoare或者其他的快排好像都没有直接解决掉这个问题，当一个数重复出现的时候，用普通的快排效率其实并没有那么高。所以，这也是普通快排的缺点之一。

2f04f5466f3d4bbbb8f457e15e04d46e.png

所以，在一个元素重复出现多次的时候，可以用三路划分来优化快排。

70a65998131c415db9d3344fadb29066.png

思考一下，为什么当arr[cur] > key的时候，cur不++呢？

这是因为，我们只知道当时在cur位置上的值比key大，而right不知道比key大还是小，所以不用cur++，而right–，是因为在交换后，已经知道肯定比key大了。 

源码如下：

void QuickSork(int arr[],int left,int right)
{
    if(left >= right)
        return;
    
    int begin = left;
    int end = right;

    int cur = left+1;
    int key = arr[left];
    while(cur <= right)
    {
        if(arr[cur]  key)
        {
            swap(arr[cur],arr[right]);
            --right;
        }else 
        {
            ++cur;
        }
    }

    QuickSork(arr,begin,left-1);
    QuickSork(arr,right+1,end);

}

 

 

 

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/f500e371a1.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐