三分钟学会快速排序(图示讲解,附代码,通俗易懂)

三分钟学会快速排序(图示讲解,附代码,通俗易懂)


文章目录

tag:分治、排序

快速排序的通俗解释


1.从数组中选出一个元素 x x x(可以随意选取)

2.把所有 < = x <=x <=x的元素放在x前面(形成一个子区间),所有 > = x >=x >=x大的元素放在 x x x后面(形成另一个子区间)

3.使用递归的方法,对“2”中形成的两个子区间重复执行操作,最终可以得到一个排好序的数组

具体实现可见下面的gif图:

三分钟学会快速排序(图示讲解,附代码,通俗易懂)

换句话说,快速排序就是递归的做这样一个事情:把一个区间划分为两个子区间,左区间全都 > = >= >=某个特定数 x x x,有区间全都 > = >= >=某个特定数 x x x。
三分钟学会快速排序(图示讲解,附代码,通俗易懂)

void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;//区间里面只有一个数或者没有数
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;//选择中间数作为标记数

    while (i < j)//执行一次while语句,可以使一个区间划分为两个区间
    {
        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);
}

对上述图示与代码的解释

假设有这样一个数组q

q=[5,4,3,1];

选取中间数4作为分割区间的标记数,在初始时,i,j对应的下标分别是-1和4,如下图所示:

三分钟学会快速排序(图示讲解,附代码,通俗易懂)

经过一次do while语句之后,i,j分别对应0和3,指向数组第一个和最后一个元素。

三分钟学会快速排序(图示讲解,附代码,通俗易懂)

为了使前一个区间全都小于标记值4,后一个区间全都大于标记值4,我们使i++,直到i对应的值小于或等于标记值4;使j++,直到j对应的值大于或等于值4,之后进行元素值的交换(swap语句)。

通过这一次while循环,可以使得原先数组的前一半部分全部小于标记值4,后一部分全都大于标记值4。

while (i < j)//每经过一次while循环
    {
        do i++;while (q[i] < x);
        do j--;while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

把5和1进行交换:

三分钟学会快速排序(图示讲解,附代码,通俗易懂)

交换之后得到:

三分钟学会快速排序(图示讲解,附代码,通俗易懂)

此时i = 0,j = 3,满足i < j,进入下一次while循环:

我们发现此时i指向4,j指向3,交换值,可以得到:

三分钟学会快速排序(图示讲解,附代码,通俗易懂)

最终经过一次while循环,我们得到了基于标记值4的数组分割:即前面的数字都$<= 4 , 后 面 的 数 字 都 4,后面的数字都 4,后面的数字都>=$4

三分钟学会快速排序(图示讲解,附代码,通俗易懂)

最后递归的对这两个小区间进行快速排序,即:

quick_sort(q, l, j);
quick_sort(q,j+1,r);

算法复杂度分析

平均时间复杂度: O ( n log ⁡ n ) O(n\log n) O(nlogn)

每进行一次【划分区间】操作,会递归调用处理一半大小的数列。因此,在递归结束前,我们要作 O ( log ⁡ n ) O(\log n) O(logn)次嵌套的调用,即调用树的深度是 O ( log ⁡ n ) O(\log n) O(logn)。程序调用的每一层次结构总共全部仅需要 O ( n ) O(n) O(n)的时间。结果是这个算法仅需使用 O ( n log ⁡ n ) O(n\log n) O(nlogn)时间。

三分钟学会快速排序(图示讲解,附代码,通俗易懂)

最差时间复杂度: O ( n 2 ) O(n^{2}) O(n2)

当数组已经排好序的情况下,快速排序退化为冒泡排序。

每一个区间划分成的两子区间分别含有 1 1 1 和 n − 1 n-1 n−1个元素。第 i i i 次调用作了 O ( n − i ) O(n-i) O(n−i)的工作量,且
∑ i = 0 n ( n − i ) = O ( n 2 ) \sum _{i=0}^{n}(n-i)=O(n^{2}) i=0∑n​(n−i)=O(n2)
递归关系式为:
T ( n ) = O ( n ) + T ( 1 ) + T ( n − 1 ) = O ( n ) + T ( n − 1 ) T(n)=O(n)+T(1)+T(n-1)=O(n)+T(n-1) T(n)=O(n)+T(1)+T(n−1)=O(n)+T(n−1)

这与插入排序与选择排序有相同的关系式,上式被解为 T ( n ) = O ( n 2 ) T(n)=O(n^{2}) T(n)=O(n2)。

c++代码

#include <vector>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r)
        return;//区间里面只有一个数或者没有数
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;

    while (i < j)//每经过一次while循环
    {
        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()
{
    cin >> n;

    for (int i = 0; i < n;i++)
        cin >> q[i];

    quick_sort(q, 0, n - 1);

    for (int i = 0;i < n;i++)
        cout << q[i]<<" ";

    return 0;
}

运行截图

三分钟学会快速排序(图示讲解,附代码,通俗易懂)

上一篇:Qt-类库模块划分详解


下一篇:2021-07-04 Day #1