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

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

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

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

思考一下，为什么当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);

}