双路快速排序法
在上一篇文的最后，我们发现快速排序在对大量重复元素的数组进行排序时复杂度发生了退化。
优化
不难想象，在元素完全相等的情况下，无论我们如何随机选择基准元素，都无法改善分割元素左右部分的平衡。
究其根本，是因为我们在以前的算法里并没有严格的将数组分为小于基准元素和大于基准元素的两部分，而是分为了小于基准元素和不小于(即大于等于)基准元素的两部分，而罪魁祸首就是等于基准元素的这一部分，由于我们每次都将这一部分连同大于的部分一同换到了右边，导致在有大量重复元素的情况下右边的重量极其大，分割元素左右的平衡性变得非常差。
如何优化呢？
双路快速排序
换一种新的方式处理数组并确定分割点，即优化partition这个函数。
原本我们是在单向遍历的过程中将大于等于基准元素的部分全都换到右边，为了解决这个问题，我们需要同时从左右两头开始向中心遍历。
- 设定两个扫描点，分别在数组的两头（除基准元素）。
- 首先让左边的扫描点向右遍历直到遇见了大于等于基准元素的元素，我们知道这个元素应该待在右边，左扫描点暂停。
- 让右边的扫描点向左遍历，直到遇见了大于等于基准元素的元素。此时让左扫描点与右扫描点指向的元素交换。
- 直到左扫描点与右扫描点相遇，此时数组已经被分为了两部分，小于基准元素部分的末尾便是右扫描点最后指向的元素，即分割元素，这一点可以在后面的代码中慢慢理解。
在以上的处理中，为什么我们要交换两边等于基准元素的部分，仔细想一下，在完全重复的数组中，假如不交换等于的部分，那么将会重蹈单路快速排序的覆辙，而交换之后，分割点将有很大的概率是靠近中间而并非两边。
实现
int __partition2(int arr[], int l, int r) {
//随机选取一个元素与第一个元素交换
swap(arr[l], arr[rand() % (r - l + 1) + l]);
//将数组的第一个元素设为基准元素，用一个变量保存
int base = arr[l];
//基准元素后的第一个元素为左扫描点
int i = l + 1;
//数组最后一个元素为右扫描点
int j = r;
//开始遍历
while (true) {
//从左向右遍历直到大于等于基准元素
while (arr[i] < base && i <= j) i ++;
//从右向左遍历直到小于等于基准元素
while (arr[j] > base && j >= i) j --;
//若i遇见了j或是经过了j，证明遍历结束
if (i >= j) break;
//若遍历未结束，交换。
swap(arr[i] , arr[j]);
//继续遍历
i ++;
j --;
}
//遍历结束后交换基准元素与分割元素，返回分割点
swap(arr[l], arr[j]);
return j;
}
注意遍历结束的条件判断如果写在while的参数中，可能会漏掉一组元素没有交换，因此要写在交换之前。
测试
大量重复与完全重复的数组测试
merge sort : 0.006169s
quick sort : 0.259619s
quick sort2 : 0.004532s
merge sort : 0.000329s
quick sort : 2.776326s
quick sort2 : 0.003351s
可以发现情况已经被大大改善了，但趋于完全重复的数组时依然无法与归并排序相提并论。