快速排序

题目描述

将读入的 N 个数从小到大排序后输出。

输入格式

第一行为一个正整数 N。

第二行包含 N 个空格隔开的正整数 ai​，为你需要进行排序的数。

输出格式

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

5
4 2 4 5 1

1 2 4 4 5

提示

对于 20% 的数据，有 1≤N≤103；

对于 100% 的数据，有 1≤N≤1****5，1≤a[i]​≤1****9。

要求

请用快速排序算法完成此题。

模板

#include <iostream>
using namespace std;

int q[10000005];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> q[i];
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++ ) cout << q[i] << " ";

    return 0;
}