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

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

百度百科是这么介绍的:快速排序由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 - 0 , 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)
}

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

快排的三个步骤

  1. 确定分界点 q[l] , q[l + r >> 1] , q[r] , 随机
  2. 调整区间 保证左边小于等于x,右边大于等于x,x在哪一边都可以💗💗💗
  3. 递归处理左右两段

这个模板其实不难理解,函数传入一个含有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;
}

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

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

Q.E.D.


都懂一点,不是很懂的小捞仔