快速排序

思想：分治

步骤

  • 确定分界点

    选择一个点（ $a[l],a[r],a[mid]…$）,记为$x$

  • 调整范围

    令所有$\le x$ 的数在$x$左侧，$>x$ 的数在 $x$ 右侧

  • 递归处理左右两段

    重复处理$[1 \thicksim x],[x+1 \thicksim n]$两段

实现方式1：暴力（$O(n\log n)$）$空间复杂度极高$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n;
int q[N];

void qksort(int l,int r){
    if(l>=r)return;
    int mid=l+r>>1;
    int x=q[mid];
    int a[N],b[N],cnta=0,cntb=0;
    for(int i=l;i<=r;i++){
        if(q[i]<=x&&i!=mid){
            a[++cnta]=q[i];
        }
        else if(q[i]>x){
            b[++cntb]=q[i];
        }
    }
    for(int i=1;i<=cnta;i++){
        q[l+i-1]=a[i];
    }
    q[l+cnta]=x;
    for(int i=1;i<=cntb;i++){
        q[l+cnta+i]=b[i];
    }
    qksort(l,l+cnta-1),qksort(l+cnta+1,r);
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> q[i];
    }
    qksort(1,n);
    for(int i=1;i<=n;i++){
        cout << q[i] << ' ' ;
    }
    return 0;
}

实现方式2：双指针（$O(n\log n)$）$空间复杂度O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n;
int q[N];

void qksort(int l,int r){
    if(l>=r)return;
    int x=q[l+r>>1];
    int L=l-1,R=r+1;
    while(L<R){
        do L++;while(q[L]<x);
        do R--;while(q[R]>x);
        if(L<R)swap(q[L],q[R]);
    }
    qksort(l,R),qksort(R+1,r);
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> q[i];
    }
    qksort(1,n);
    for(int i=1;i<=n;i++){
        cout << q[i] << ' ';
    }
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~