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

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

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

刷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);}