快速排序

快速排序概述

快速排序是一种分治算法，分而治之，每次将序列分成两部分，递归处理，进而求得答案

快排正如y总说的那样，它的边界问题很多。对于这种情况，把模板背了就好，没有必要过分纠结一些细节(当然知道也更好)。追求效率的话，背过即可

快排算法分析

1. 确定分界点

分界点可以是$l$ ~ $r$任意一点，常用为$l, r, (l + r >> 1)$， 分界点为$x$

2. 调整范围

需要得到的结果是左部分的数均小于等于枢纽元，右侧均大于等于枢纽元。
(1)开辟两个数组，遍历时候，小于等于的放在第一个数组，大于放第二个数组最后合并(空间浪费)
(2)双指针算法(维护次序)。 $i$ 从左到右遇到第一个 $>= x$， 停下来， $j$从右到左，遇到第一个 $<=x$的停下来。二者交换。最终也可以分成两个满足需求的部分

3. 递归处理

递归处理左部分与右部分。递归结束条件, $l >= r$，即区间内没有数字或者只有一个数字的时候截止递归

常见问题

1.

Q: $i$和$j$在等于的情况下交换，是不是不必要的？
A: 如果我们不在等于的时候交换，那么$i, j$就很容易越界，会出现很多边界问题，为了解决这个问题，将会让代码复杂化，这个代价相比于多出的微不足道的时间是要多很多的。

2.

Q: 分界点取$j$，用$i$可不可以？
A: 可以，但是二者需要对称着写，同时要注意取得枢纽元，比如用i的话，就不能取左边界作枢纽元，中点也需要像上取证，否则就会出现死循环，($eg$,课上的例子，$0,2$)

3.

模板保证的是左部分$<= x$， 右部分 $>=x$，但分界点不一定是$x$。这与在教科书上看到的工程式写法不同，那种写法一般最后有一次交换操作

4.

枢纽元选取的问题，个人一般使用的是中点，采用左右端点，如果遇到不太好的数列，比如单调递增/递减，就会出$O(n^{2})$的时间复杂度。中点相对于端点就好了很多(当然也不是最好的，三数取中法应该是不错的，取随机数代价也是很大的)

时间复杂度

平均情况$O(n\log n)$，最坏情况$O(n^2)$
$c++$ 一秒计算$10^8$ 到$10^9$次
平均情况得不到200w，可以计算出来

代码

#include <iostream>

using namespace std;

const int N = 100010;//多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];
    //因为我们每次是指针先移动，再判断，所以定义i,j为端点两侧
    while (i < j)
    {
        do i ++ ; while (q[i] < x);//从左向右找到第一个 >= x的数字
        do j -- ; while (q[j] > x);//从右向左找到第一个 <= x的数字
        if (i < j) swap(q[i], q[j]);//满足条件则交换
    }

    quick_sort(q, l, j);//递归处理左右两部分
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);//左右区间端点是0, n - 1

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}