P1177 【模板】快速排序

#include<iostream>
using namespace std;

int n, a[1000001];
void qsort(int l, int r)//采用二分思想
{
    int  mid = a[(l + r) / 2];
    int i = l, j = r;
    do
    {
        while (a[i] < mid)//寻找左侧大于mid的数
            i++;
        while (a[j] > mid)//寻找右侧小于mid的数
            j--;
        if (i <= j)//一旦找到符合条件（左大右小）的两个数，将它们进行交换。
        {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    } while (i <= j);
    if (l < j)
        qsort(l, j);//继续对左侧区间调用qsort
    if (i < r)
        qsort(i, r);//继续对右侧区间调用qsort
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    qsort(1, n);
    for (int i = 1; i <= n; ++i)
        cout << a[i] << " ";
    return 0;
}