SolitudeAlma

今天我们来讲一下快速排序

那么什么是快排呢？🤔🤔🤔

百度百科是这么介绍的：快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

也可以看看动态图😮😮😮
快速排序

它的主要思想是分治法，就是把一个问题分成相互独立的几个规模较小的子问题，然后逐一去解决，最终将得到“母问题的答案”。链接 ==>>分治法

今天我们将采用双指针算法去理解快速排序这一过程，对于双指针算法不太理解的小伙伴可以看看这个介绍 ==>>

算法 | 双指针套路总结

双指针算法基本原理和实践

因为我们是用数组去排序的，所以你只需要知道双指针代表着两个在改变的下标就行了（下标访问本质上也是指针）。

快排的平均时间复杂度为 $O(nlog_2n)$ ，最糟糕的时候是 $O(n^2)$ 。

首先我们先给出我们的快排模板👇👇👇

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为右指针 x为每一次分割区间时选定的比较数  >> 这个是右移运算符，是位运算的一种，将一个整数右移一位表示除以2 
    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]); //swap函数存在于C++的algorithm头文件中，相当于自己手写的交换变量函数，因为指针停下来的时候可能是穿过，重合这两种情况其中一种，如果未相遇我们就交换指针所指的数，然后直到l>=r循环结束
    }
    //每一次递归之后i、j的相对位置只有两种情况，i==j或者i==j+1
    quick_sort(q , l , j) , quick_sort(q , j + 1 , r);//递归处理左右区间，先左，再右（注意划分区间用的是i还是j）
}

好了，以上就是我们要用到的快排模板了，一个好的模板能让你快速记忆一个算法，同时它也已经帮我们解决了烦人的边界问题，只需要好好理解记忆即可

快排的三个步骤

确定分界点 q[l] , q[l + r >> 1] , q[r] , 随机

调整区间保证左边小于等于x，右边大于等于x，x在哪一边都可以💗💗💗

递归处理左右两段

这个模板其实不难理解，函数传入一个含有n个元素的有序或者无序的序列，我们用分治法的思想，首先先确定分界点，因为选取的是l + r >> 1也就是中间元素；而后寻找满足条件的数，直到 $l >= r$ ,接着调整区间，将其分为 $>=x$ 和 $<=x$ 的两个区间（用j划分，j的左边一定小于等于x，j的右边一定大于等于x）；最后再递归处理左右区间。

如果一个区间只有一个元素，而这个区间又满足小于等于x或者大于等于x这一条件，那么整个合并的区间都是有序的。

一共需要分 $log_2n$ 次,在第 $log_2n$ 次时每一个元素都在一个区间里，在那个区间中它是有序的。也是至此递归不再继续，因为区间中只有一个元素（ $l >= r$ ），还是不明白的小伙伴可以动手模拟一下，画一下图会清晰很多

一些细节

1.i , j 指针每次都在区间之外，这是因为我们用了do-while循环，每一次指针都是先+1/-1，再判断，这样可以避免死循环等一些迷之操作（其实一般来说都是先判断再操作，这样的话避免回退操作，这里用do-while循环是为了方便理解）

2.选取元素的作为比较的值时尽量不要选取左右端点，因为当序列有序时，时间复杂度会退化为 $O(n^2)$

3.如果选取右端点，则递归处理的代码为quick_sort(q , l , i - 1) , quick_sort(q , i , r);如果选的是左端点，则为quick_sort(q , l , j) , quick_sort(q , j + 1 , r);；如果选取中间点，两种都可以哦，但是中点选取变为 q[l + r + 1 >> 1]

4.一切有关边界问题的算法都建议背模板，因为这是经过n位大佬试验过的，只需要记就行了

5.如果用的时候无论如何都想不起快排的模板的话，还有一个暴力的方式。1.首先我们先创建a，b两个数组；2.遍历数组q，小于等于x的数放入a中，其他的放入b中；3.将a，b分别排序后，先将a中的元素放入q，再将b中的元素放入q即可

6.最后最后，还是用j做分界点和q[l + r >> 1]做目标值为好，这样能规避所有边界问题
这个算法难点在于调整区间,以j来划分区间的话，在j左边的数都小于等于x，在右边的都大于等于x，其他同理，应该注意你用的是i还是j来划分区间

附上一个简单的快速排序图解

现在我们来写一道模板题

AcWing 785.快速排序

题目描述

给定你一个长度为n的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

$1≤n≤100000$

输入样例：

5

3 1 2 4 5

输出样例：

1 2 3 4 5

这时候我们直接套用模板既可

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100010;

int n , a[N];

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

    int x = q[l + r >> 1] , i = l - 1 , j = r + 1;
    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);
}

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

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

    quick_sort(a , 0 , n - 1);

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

    return 0;
}

大家在学算法的时候，特别是学习一个类型题的模板时可以隔三岔五地去敲了两三遍，当然不用追求和模板一致，因为模板是死的，人是活的，只要知道哪里可以变哪里不可以变，灵活运用即可

最后祝大家学习了算法之后，在刷题时能够游刃有余🤺🤺🤺

快速排序的介绍以及算法的模板分享