题解 【P1177】 【模板】快速排序

题面

https://www.luogu.com.cn/problem/P1177

什么是快速排序

快速排序是运用分治思想的最坏时间复杂度为O(n²), 期望时间复杂度为O(nlgn)的排序算法。

下面简述步骤: > 首先设定一个分界值，通过该分界值将数组分成左右两部分。 > 将大于或等于分界值的数据集中到分界右侧，小于分界值的数据集中到分界左侧。直至左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。 > 分别对左右两边的数据进行快速排序。

完整AC代码

点我查看完整代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[100009];
void qsort(int l, int r){
    int mid = a[(l + r)/2];
    int i = l, j = r;
    do{
        while(a[i] < mid)	i++;
        while(a[j] > mid)	j--;
        if (i <= j){
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }while(i <= j);
    if (i < r)	qsort(i, r);
    if (j > l)	qsort(l, j);
}
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    qsort(0, n - 1);
    for (int i = 0; i < n - 1; i++){
        printf("%d ", a[i]);
    }
    printf("%d\n", a[n - 1]);
    return 0;
}