三路快速排序法
优化
针对上一篇文中提到的问题，还有一种更好的解决方案，依旧是改进处理数组的部分，解决等于基准元素部分带来的麻烦。
试想一下，如果我们能将数组分为小于、等于、大于基准元素的三个部分，那么每次递归只需要处理小于和大于的两个部分就够了，这样就可以完全解除大量重复元素数组的不平衡问题。
具体做法是：
- 使用两个点分别标定小于基准元素部分的头部和尾部，同样的，再使用两个点标定大于基准元素的头部和尾部，这样一来，从小于基准元素的尾部到大于基准元素的头部之间的部分就是等于基准元素的。
- 从左到右遍历数组，如果元素小于基准元素，就将它与等于基准元素部分的头部交换，小于基准元素的尾部向后移动一次。
- 如果元素大于基准元素，就将它与等于基准元素部分的尾部交换，大于基准元素的头部向前移动一次。
- 如果元素等于基准元素，什么都不做，继续遍历。
- 直到遍历到大于基准元素的头部，最后将基准元素与小于基准元素的尾部交换，整个数组处理完毕。
由于我们需要返回的是小于基准元素的尾部与大于基准元素的头部这两个点，在C++中不是很容易办到，因此我们直接将partition部分写在quicksort里面。
实现
//------三路快速排序------
void __quickSort3(int arr[], int l, int r) {
//切换到插入排序
if (r - l <= 15) {
insertionSort2(arr, l, r);
return;
}
//随机选取一个元素与第一个元素交换
swap(arr[l], arr[rand() % (r - l + 1) + l]);
//将数组的第一个元素设为基准元素，用一个变量保存
int base = arr[l];
//基准元素后的第一个元素为扫描点
int i = l + 1;
//将扫描点的前一个元素作为小于部分的尾部，此时该部分是空的
int lEnd = l;
//将数组末尾的后一个元素作为大于部分的头部，此时该部分也是空的
int rBegin = r + 1;
//开始遍历 当到大于部分的头部时结束遍历
while (i < rBegin) {
//当前元素小于基准元素时，将其与等于部分的头部交换，小于部分的尾部后移
if (arr[i] < base) {
swap(arr[i],arr[lEnd + 1]);
lEnd ++;
}
//当前元素大于基准元素时，将其与未处理部分的尾部交换，大于部分的头部前移
//注意因为交换过来的是未处理部分因此遍历点不用后移，直接跳到下个循环
else if (arr[i] > base) {
swap(arr[i],arr[rBegin - 1]);
rBegin --;
continue;
}
i ++;
}
//遍历结束后交换基准元素与小于基准元素的尾部交换
swap(arr[l], arr[lEnd]);
//对左边的部分递归处理，注意由于基准元素加入了等于部分，因此小于部分的尾部要前移。
__quickSort3(arr, l, lEnd - 1);
//对右边的部分递归处理
__quickSort3(arr, rBegin, r);
}
测试
数据量为100W
随机数组
merge sort : 0.217579s
quick sort2 : 0.168809s
quick sort3 : 0.216727s
近乎有序的数组
merge sort : 0.035672s
quick sort2 : 0.098913s
quick sort3 : 0.151417s
完全有序的数组
merge sort : 0.004990s
quick sort2 : 0.098252s
quick sort3 : 0.156945s
大量重复的数组
merge sort : 0.145970s
quick sort2 : 0.099979s
quick sort3 : 0.033550s
完全重复的数组
merge sort : 0.004849s
quick sort2 : 0.077188s
quick sort3 : 0.002459s
总结
三路快速排序在重复数组中表现除了非常大的优势，在其他的情况下表现也可以接受，它是目前应用最广泛的快速排序版本。