快速排序

快速排序是一种原地排序，只需要一个很小的栈作为辅助空间，空间复杂度为O(logN)，所以适合在数据集比较大且无序的时候使用。实现方法有经典快排和双指针快排，本文介绍的是双指针快排的实现。

快排算法复杂度
空间复杂度 时间复杂度（最好） 时间复杂度（最差） 时间复杂度（平均）
O(logN) O(N) O(N^2) O(NlogN)

基本思想

随机找出一个数，可以随机取，也可以取固定位置，一般是取第一个或最后一个称为基准，然后就是比基准小的放在左边，比基准大的放到右边。

实现方法

一种是在每次递归时利用两个数组存取基准pivot前后的数据，这种空间复杂度较高。

另外一种是利用双指针的思想：利用left和right指针，首先left从前向后遍历，碰到大于pivot的数则停止；right从后向前遍历，碰到小于pivot的数则停止，随后交换left和right处的数据，直到left>=right。代码如下：

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
#include<iostream>

using namespace std;
const int N=1e6+10;
int a[N];

void quick_sort(int q[], int l, int r){
    if(l>=r)return;
    int idx = rand() % (r - l + 1) + l;
    swap(q[idx], q[r]);
    int x=q[r];
    int 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(){
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;i++)scanf("%d", &a[i]);
    quick_sort(a, 0, n-1);
    for(int i=0;i<n;i++)printf("%d ", a[i]);
    return 0;
}

快排的应用——-快速选择寻找第k个数

给定一个长度为n的整数数列，以及一个整数 k，快速求出数列从小到大排序后的第k个数。
思路
快速排序后根据下标选择即可：

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<iostream>

using namespace std;

const int N=1e6+10;
int a[N];

int quick_select(int q[], int l, int r){
    if(l>=r)return 0;
    int idx=rand()%(r-l+1)+l;
    int x=q[idx];
    swap(q[idx], q[r]);
    int 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_select(q, l, j);
    quick_select(q, j+1, r);
}

int main(){
    int n, label;
    scanf("%d %d", &n, &label);
    for(int i=0;i<n;i++)scanf("%d", &a[i]);
    quick_select(a, 0, n-1);
    printf("%d", a[label-1]);
    return 0;
}