【模板】快速排序

题目描述

利用快速排序算法将读入的 $N$ 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

输入格式

第 $1$ 行为一个正整数 $N$，第 $2$ 行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数，数据保证了 $A_i$ 不超过 $10^9$。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

样例 #1

样例输入 #1

5
4 2 4 5 1
1
2

样例输出 #1

1 2 4 4 5
1

提示

对于 $20\%$ 的数据，有 $N\le 10^3$；

对于 $100\%$ 的数据，有 $N\le 10^5$。

分析

快排就是分治算法，先分成两段，再分别继续去分这两段；

1. 需要注意这是个递归的过程，要有递归出口，刚开始是一个整段，递归出口就是当l>=r的时候，后面分治的没一小段，也都要满足l>=r时候结束递归
2. x的选取就选在中间，防止int炸了，采取了代码中的巧妙方式，i,j分别是指向两端的指针，由于do先执行的i++，所以让i提前一位，同理j后移一位。让x左边的数都小于等于x，让x右边的数都大于等于x；
3. 过程就是：在满足i<j的这个过程中，如果i这个位置的数<x，就让i++，继续进行下去；如果j这个位置>x，就让 j– ，让j往前移一个位置；当这两个dowhile循环都结束说明，i，j这两个位置的数正好和想要的相反，直接交换。然后看看如果i<j;那就继续上述过程。
4. 最后去递归调用这两段，quick_sort(a, l, j); quick_sort(a, j + 1, r); ==(l,j）和（j+1,r）==这两段。

代码

#include <bits/stdc++.h>

using namespace std;

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

void quick_sort(int a[], int l, int r) {
    if (l >= r) return;//递归出口
    int x = a[l + (r - l) / 2];
    int i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j)
            swap(a[i], a[j]);
    }
    quick_sort(a, l, j);
    quick_sort(a, 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;
}
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