P1177 【模板】快速排序

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

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

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

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

5
4 2 4 5 1

1 2 4 4 5

对于 20 % 20% 20% 的数据，有 N ≤ 1 0 3 Nleq 10^3 N≤103；

对于 100 % 100% 100% 的数据，有 N ≤ 1 0 5 Nleq 10^5 N≤105。

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

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

#include 

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;
}