# Quick Sort 快速排序 · `QuickSort.cpp`

快排和他的名字一样，是一个排序比较快的算法，它的核心思想是选定一个基准p，将数组中小于p的放在一边，大于p的放在一边，分成两个子数组，之后再分别对这两个子数组进行排序，不断重复直到整个数组有序

## 一、复杂度与特性

| 项目         | 值                       | 说明                                                                             |
| ------------ | ------------------------ | -------------------------------------------------------------------------------- |
| 时间（最好） | O(n log n)               | 每次划分都恰好对半：递归树高`log n` 层，每层合计扫一遍 O(n)                    |
| 时间（平均） | O(n log n)               | 期望比较次数 ≈`2n·ln n` ≈ `1.39·n·log₂n` |
| 时间（最坏） | O(n²)                   | 每次都选到极值当基准 ⇒ 划分成`0` 和 `n-1` 两段、递归 `n` 层               |
| 空间         | O(log n) 平均，O(n) 最坏 | 原地排序，不额外开数组，只花递归栈                                               |
| 稳定性       | 否                       | 划分时的远距离交换会打乱相等元素的相对次序                                       |
| 比较次数     | n·log n                 | 一趟划分 O(n)，一共log n 层                                                      |

## 二、代码

```cpp
void quick_sort(std::vector<int> &a, int l, int r)
{

    if (r - l <= 0)
        return;
    std::swap(a[l], a[r]);
    int p = a[l]; // 也可以为其它位置
    int i = l - 1, j = r + 1; // 两个指针分别指向最左边和最右边
    while (true)
    {
        do
        {
            ++i;
        } while (a[i] < p);
        do
        {
            --j;
        } while (a[j] > p);
        if (i >= j) // 判断是否已经分好
            break;
        std::swap(a[i], a[j]);
    }
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}
```

要点：

1. 快排中基准元素的选取很重要，选的好与不好差距很大（最好是随机选取，并且不能留在区间右端）
2. 出口条件是长度小于等于一，也就是`l>=r`
3. `i >= j`时必须先`break`再交换；否则会交换一对本该分离两侧的元素导致划分失效。
4. 划分里的交换是远距离的，无法保证稳定性，如[2a, 2b, 0] 排完是 [0 2b 2a]，两个2顺序颠倒了
5. 内层必须严格小于大于，否则指针会冲过区间另一端导致划分不均
6. 递归点用`j`而不是`i`