【C++】快速排序

快速排序的方法是给定待排序数组vec，首先从vec中选取一个基准值base，然后根据基准值划分数组，再递归排序子数组，伪码如下，当然这个伪码中重新分配了数组，带来了时空开销，基准值划分数组时，最好是原地进行的

def quick_sort(arr: List[T]) -> List[T]:
    if len(arr) <= 1:
        return arr
    base: T = arr[len(arr) // 2]
    left: List[T] = [x for x in arr if x < base]
    middle: List[T] = [x for x in arr if x == base]
    right: List[T] = [x for x in arr if x > base]
    return quick_sort(left) + middle + quick_sort(right)

原地划分数组可以使用填坑法: link

当然这种方法很丑，可以看到循环里判断了5次i < j，因为这里维护划分数组的形式为<基准值的、基准值本身、除了基准值本身>=基准值的三部分

但这里主要的问题是基准值选取的位置是固定的，对于[1, 2, 3, .. N]或[N, N-1, N-2, .. 1]之类的输入，时间复杂度会从估计的 $NlogN$ 上升到 $N^2$

void quick_sort(int s[], int l, int r)
{
    if (l < r)
    {
        //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
        int i = l, j = r, x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                j--;  
            if(i < j) 
                s[i++] = s[j];
            
            while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                i++;  
            if(i < j) 
                s[j--] = s[i];
        }
        s[i] = x;
        quick_sort(s, l, i - 1); // 递归调用 
        quick_sort(s, i + 1, r);
    }
}

首先我们也可以只分为两部分,>=基准值的和<=基准值的，这样循环只要遍历一次，根据当前元素与基准的大小关系判断即可

问题在于如何处理等于基准值的部分？

当然是不能随意放到某一部分的，因为只分成两个子数组，可能在以下情况无限递归

如果数组中元素全相同，而我们将等于基准值的部分都放到同一子数组
如果基准值选取的位置是固定，而且每次选中唯一的最大值或唯一的最小值

针对以上问题

如果数组中某个位置等于基准值，贪心地划分到元素较少的子数组
随机选取基准值

由于随机选取基准值，时间复杂度也许更接近理论的 $NlogN$

一个C++模板实现如下

template <typename Iter, typename Compare = std::less<typename Iter::value_type>, typename RandomEngineT = std::mt19937>
void quick_sort(Iter left, Iter right, Compare cmp = {}) {
    static std::random_device rd{};
    static RandomEngineT rng{rd()};
    auto length = std::distance(left, right);
    if (length < 2)
        return;
    // [left, right)
    std::swap(*(left + rng() % length), *left);
    auto& base = *left;
    auto iter1 = left + 1, iter2 = right - 1;
    // [left, iter1), (iter2, right)
    while (iter1 <= iter2) {
        if (cmp(*iter1, base) || (!cmp(base, *iter1) && std::distance(left, iter1) < std::distance(iter2, right)))
            ++iter1;
        else
            std::swap(*iter1, *(iter2--));
    }
    quick_sort(left, iter1);
    quick_sort(iter2 + 1, right);
}

首先我们定义形参为左闭右开的迭代器[left, right)

定义左右数组范围分别为左闭右开、左开右开的迭代器[left, iter1), (iter2, right)

当iter1 <= iter2时，说明还有元素没划分，当*iter1小于基准值base，或相等且左边子数组更短时划分到[left, iter1)，否则划分到(iter2, right)

这里写成

    std::swap(*(left + rng() % length), *left);
    auto& base = *left;

而不是

    auto  base = *(left + rng() % length);

是为了支持排序元素类型Iter::value_type只可移动不可复制（如std::unique_ptr）的情况

同时为了降低递归次数，考虑如果数组只有两个元素[a,b] 且a != b 时，根据代码中的策略，有1/2 的概率把两个数都分到左边，重新再在[a,b] 上递归一次

也就是说数组中元素较少时，我们更容易选中唯一的最大值或唯一的最小值，导致取随机数和递归的开销增加，但是数组中元素较少时，本身有序的概率也更大。所以元素小于10 的时候，直接冒泡排序

以上优化过的快排在leetcode-912.中时间开销可以达到104ms ，和直接std::sort（112ms）差不多

使用例

Copyable类型

vector v{321, 23, -2, 0, 9, -2, 89, 17};
quick_sort(v.begin(), v.end());
for (auto c : v)
    cout << c << ", ";
// -2, -2, 0, 9, 17, 23, 89, 321,

only-movable类型

vector<std::unique_ptr<int>> vv{};
vv.emplace_back(new int(2));
vv.emplace_back(new int(1));
vv.emplace_back(new int(3));
quick_sort(vv.begin(), vv.end(), [](auto const&a, auto const& b) {
    return *a < *b;
});
for (auto& c : vv)
    cout << *c << ", ";
// 1, 2, 3,

感谢您的支持，我会继续努力的!