数据结构——三路划分（快排优化）-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构——三路划分（快排优化）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数据结构——三路划分（快排优化）,数据结构,数据结构,c语言,c++,windows,排序算法

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

数据结构——三路划分（快排优化）,数据结构,数据结构,c语言,c++,windows,排序算法

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

数据结构——三路划分（快排优化）,数据结构,数据结构,c语言,c++,windows,排序算法

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

数据结构——三路划分（快排优化）,数据结构,数据结构,c语言,c++,windows,排序算法

思考一下，为什么当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[left],arr[cur]);
            cur++;
            left++;
        }else if(arr[cur] > key)
        {
            swap(arr[cur],arr[right]);
            --right;
        }else 
        {
            ++cur;
        }
    }

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

}

文章来源地址https://www.toymoban.com/news/detail-714690.html

到了这里，关于数据结构——三路划分（快排优化）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！