快速排序

原理

代码

#include <iostream>
using namespace std;

const int N = 100010;
int a[N];

void quick_sort (int l, int r) { // yxc 的快排模板
    if (l >= r) return;
    int pivot = a[l + r >> 1], i = l - 1, j = r + 1;
    while (i < j) {
        do ++ i; while (a[i] < pivot);
        do -- j; while (a[j] > pivot);
        if (i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

void quick_sort (int l, int r) { // 《啊哈！算法》的快排模板
    if (l >= r) return;
    int pivot = a[l], i = l, j = r;
    while (i != j) {
        while (i < j && a[j] >= pivot) -- j;
        while (i < j && a[i] <= pivot) ++ i;
        if (i < j) swap(a[i], a[j]);
    }
    a[l] = a[i];
    a[i] = pivot;

    quick_sort(l, i - 1);
    quick_sort(i + 1, r);
}

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