第一讲 基础算法 - 01 快速排序

[toc]

推荐阅读：

快速排序

快速排序算法模板 —— 模板题 AcWing 785. 快速排序

1. 简介

快速排序是一种常见且高效的排序算法。其基本思想可以归纳为以下几个步骤：

  1. 选择一个基准元素（通常是数组的第一个或最后一个元素）作为分割点。
  2. 将数组中小于基准的元素移动到基准的左边，大于基准的元素移动到右边。这个过程称为分区操作。
  3. 对分区后的左右两个子数组，重复步骤1和步骤2，直到子数组的大小为1或0，即已经排序完成。
  4. 最后将所有子数组拼接起来，即得到排好序的数组。

这种分而治之的思想使得快速排序具有较好的平均时间复杂度（O(nlogn)），并且它是一种原地排序算法，不需要额外的辅助空间。

需要注意的是，快速排序的性能高度依赖于选取的基准元素。不同的选择方式可能导致最好情况和最坏情况的时间复杂度差异较大，因此一些优化方法也被提出来，如随机选择基准元素、三数取中法等。

2. 算法步骤

基于分治。
第一步 确定分界点x：取左边界q[l]，或者取中间值q[(l+r)/2]，或者取右边界q[r]，也可以随机。
第二步 调整区间(较难部分)：让小于等于x的数在一个区间，大于x的在另一个区间——最终效果是：x 左边的都是小于等于 x，x 右边的都是大于等于 x。

$fileName
调整区间

第三步 递归处理左右两端

平均时间复杂度： O(nlogn)
每层期望是 n/2 ，递归深度 logn，故平均时间复杂度 O(nlogn)

3. 思路讲解

思路1（暴力解法，需要额外空间放a b）：
但从时间复杂度上来说也是线性的，一共扫了2遍，时间复杂度为 O(n)，常数可以不考虑。

$fileName
暴力解法

思路2（较优美的解法）：
使用双指针，从数组两端向中间靠拢。指针 i 从左端找大于等于 x 的数，指针 j 从右端找小于等于 x 的数，然后swap二者，直至 i 和 j 相遇。

$fileName
优美解法

4. 快排模板


const int N = 1e6 + 10;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];    // 确定分界点 x
    while (i < j)
    {   // 调整区间
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);   // 递归处理左, 右两部分
}

递归 quick_sort(q, l, j), quick_sort(q, j + 1, r); 中 j 也可以换成用 i 的写法，但是要注意 x 的取值边界问题。