快速排序

最好情况：每次正好将数组分半，O(NlogN)

最坏情况：输入的输入已经排好序，O(N^2)

为了防止出现最坏情况，需要在进行快速排序前随机打乱数组以避免数组已经排好序

一、经典快速排序

1. 主要过程

void quick_sort_core(vector<int>& nums, int l, int h)
{
    if (h <= l)
        return;
    int m = partition(nums, l, h);
    quick_sort_core(nums, l, m - 1);
    quick_sort_core(nums, m + 1, h);
}
void quick_sort(vector<int>& nums)
{
    quick_sort_core(nums, 0, nums.size() - 1);
}

2. partition函数

int partition(vector<int>& nums, int l, int h)
{
    int i = l, j = h + 1;
    int v = nums[l];
    while (true)
    {
        while (nums[++i] < v && i != h);
        while (v < nums[--j] && j != l);
        if (i >= j)
            break;
        swap(nums, i, j);
    }
    swap(nums, l, j);
    return j;
}

partition函数的另一种写法，参考Leetcode

二、改进

1.随机快排

2. 切换到插入排序

因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序

3. 三数取中

三取样切分跟随机快排一样，也是从寻找最优的切分点这个方向上来优化快排。

三取样切分即是使用数组中的小部分元素的中位数来切分数组，这样做的切分更好，但是会带来计算中位数的负担，人们发现将取样大小设为3并用大小居中的元素切分效果最好。

4. 三向切分

熵最优的排序（三向切分）主要是为了处理数组中有大量重复元素的情况，如果数组中有大量重复的元素，如果不考虑对重复元素做特殊处理，就会少了一个优化的好机会，比如，一个元素全部重复的数组就不需要在进行排序了。

一个简单的想法就是将数组的元素分成三部分，大于哨兵的，小于哨兵的和等于哨兵的。这个问题有一个解法，就是Dijkstra解法，荷兰国旗问题可以通过此法解决，三向切分快速排序对于只有若干不同主键的随机数组可以在线性时间内完成排序

Dijkstra解法的主要思路是：从左到右遍历数组一次，维护一个指针lt，使得data[lo…lt-1]的所有元素都小于哨兵，一个指针gt，使得data[gt+1…hi]之间的元素都大于哨兵，维护一个指针i，使得data[lt…i-1]之间的元素都等于哨兵，data[i…gt]之间的元素还未处理。

具体的处理过程如下，一开始i等于lo，哨兵值等于v：

• 如果data[i]小于v，则交换data[i]和data[lt]，lt++, i++;
• 如果data[i]大于v，则交换data[i]和data[gt]，gt–;
• 如果data[i]等于v，i++;

void three_way_quick_sort(vector<int>& nums, int l, int h)
{
    if (h <= l)
        return;
    int lt = l, i = l + 1, gt = h;
    int v = nums[l];
    while (i < gt)
    {
        int cmp = nums[i] - v;
        if (cmp < 0)
            swap(nums, lt++, i++);
        else if (cmp > 0)
            swap(nums, i, gt--);
        else
            i++;
    }
    three_way_quick_sort(nums, l, lt-1);
    three_way_quick_sort(nums, gt+1, h);
}

5. 基于切分的快速选择算法

快速排序的partition方法，会返回一个整数j使得a[l..j-1]小于等于a[j],且a[j+1..h]大于等于a[j]，此时a[j]就是数组的第j大元素

可以利用这个特性找出数组的第k个元素

该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为(N+N/2+N/4+…)，直到找到第k个元素，这个和显然小于2N

void selectK(vector<int>& nums, int k)
{
    int l = 0, h = nums.size()-1;
    while (h > l)
    {
        int j = partition(nums, l, h);
        if (j == k)
            return nums[k];
        else if (j > k)
            h = j - 1;
        else
            l = j + 1;
    }
    return nums[k];
}