算法题：快速排序

问题描述

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

输入格式

第 1 行为一个正整数 N(N<=10⁵)，第 2 行包含 N 个空格隔开的正整数 a~i~​，为你需要进行排序的数，数据保证了a~i~ 不超过 10⁹。

输出格式

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

样例

输入

5
4 2 4 5 1

输出

5 4 4 2 1

解决方案

思路

快速排序

代码

#include <iostream>

using namespace std;

void quick_sort(long long *arr, int begin, int end) {
    if (begin >= end)
        return;

    int b = begin;
    int e = end;
    long long m = arr[b];

    while (b < e) {
        while (b < e && arr[e] >= m)
            --e;
        arr[b] = arr[e];

        while (b < e && arr[b] <= m)
            ++b;
        arr[e] = arr[b];
    }
    arr[b] = m;

    quick_sort(arr, begin, b - 1);
    quick_sort(arr, b + 1, end);
}

int main() {

    int n;
    long long arr[100005];

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    quick_sort(arr, 0, n - 1);

    for (int i = n-1; i >= 0; --i) {
        cout << arr[i] << " ";
    }

    return 0;
}