快速排序算法优化
在快速排序算法中,寻找基准值 key 位置的方法主要有两种:
- Hoare 法:整体思路是创建两个下标变量 left 和 right。right 先从右侧寻找小于基准值的数据,left 从左侧开始寻找大于基准值的数据,将 right 和 left 的值交换。继续查找交换,直到 left 小于 right。
- Lomuto 法:整体思路是快慢指针。cur 用作快指针,prev 用作慢指针。快指针 cur 先行,用来寻找数值小于 key 所指元素。找到后,prev 先自增,再和 cur 元素位置进行交换。直到 cur 越界访问。此时交换 key 和 prev 所指元素,prev 此时的位置就是所需要找的 key 的位置。
但这两种算法中,都没有对数值等于 key 的情况进行处理,尤其是在 Lomuto 法中,如果一个待排序数组为极端情况数值全体相等,那么 Lomuto 法的时间复杂度将会退化到 O(N^2)。同时快速排序寻找 key 本身存在的问题也是如果一个数组本身有序,那么其时间复杂度也会退化到 O(N^2)。
一、快速排序之三路查找
含义
三路查找的含义就是在对 key 寻找合适位置的过程中,包含了数值相等的情况。将数值相等的放到相邻位置,这些 key 值之前的都小于 key,之后的都大于 key。

如上图所示,默认最左侧的值为 key,在对 key 寻找合适位置的过程中,有着多个相同的数据,将这些相同的数据放到一起,left 和 right 下标最终是用来指示这些相同的数据的左右位置。 这样之后在递归的过程中,左子树的右边界就是 left-1,右子树的左边界就是 right+1。
实现方法
- 默认最左侧为 key 值。同时创建 left 和 right 指针变量。
- 创建 cur 变量用来指示 left 的下一个值。
- cur 向后移动,如果遇到的值比 key 小,那么和 left 的值进行交换,之后 cur 自增,left 自增。
- 如果遇到的值大于 key,那么 cur 和 right 进行交换,之后 right 自减,而 cur 不需要自减。
- 遇到的值等于 key,则 cur 直接自增,不需要进行数据交换。
- 重复该过程,直到 cur > right。
首先对第 4 点进行解释:因为 cur 遍历到的数值是和 key 进行比较,所以在和右侧 right 进行交换的过程中,并不知道 right 中的数值具体是大于还是小于 key。而左侧 left 所指的下标确切为 key 值,且随着数值的交换一直保持着左下标的位置,所以左侧不存在该问题。
在 cur 和右侧数据交换完成后,cur 仍需要指向当前位置,right 进行自减。cur 保持当前位置,从而对于交换后的新数据及时进行比较,将其放到合适的位置。

代码实现如下:
void QuickSort_ThreeSearch(int* arr, int left, right) {
(arr);
(left >= right) {
;
}
key = arr[left];
begin = left;
end = right;
cur = begin + ;
(cur <= end) {
(arr[cur] > key) {
(&arr[cur], &arr[end--]);
} (arr[cur] < key) {
(&arr[cur++], &arr[begin++]);
} {
cur++;
}
}
(arr, left, begin - );
(arr, end + , right);
}

