快速排序优化：三路查找与自省排序

快速排序算法优化

在快速排序算法中，寻找基准值 key 位置的方法主要有两种：

1. Hoare 法：整体思路是创建两个下标变量 left 和 right。right 先从右侧寻找小于基准值的数据，left 从左侧开始寻找大于基准值的数据，将 right 和 left 的值交换。继续查找交换，直到 left 小于 right。
2. 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。

实现方法

1. 默认最左侧为 key 值。同时创建 left 和 right 指针变量。
2. 创建 cur 变量用来指示 left 的下一个值。
3. cur 向后移动，如果遇到的值比 key 小，那么和 left 的值进行交换，之后 cur 自增，left 自增。
4. 如果遇到的值大于 key，那么 cur 和 right 进行交换，之后 right 自减，而 cur 不需要自减。
5. 遇到的值等于 key，则 cur 直接自增，不需要进行数据交换。
6. 重复该过程，直到 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);
}