T588555 快速排序

快速排序（Quicksort）采用“**选基准 → 分区 → 递归**”的分治思想：选取一个**基准（pivot）**，把数组划分为 **左段 $ \le pivot$、右段 $> pivot$** ，再分别对两段进行快速排序（分治），最终得到升序序列。 * **稳定性**：**不稳定**（相等元素的相对次序可能改变）。sort排序主要使用快排，所以并不稳定。排完序后，想要实现根据输入顺序输出，需要再加一个顺序变量。 * **空间复杂度**：$O(\log n)$（递归栈，每次函数返回了一个变量，那么就创造了一个空间，平均是$O(\log n)$ 的空间）；最坏时可达 $O(n)$。 * **时间复杂度**： * **平均**：$O(n\log n)$； * **最好**：$O(n\log n)$（分区均衡）； * **最坏**：$O(n^2)$（如已近乎有序或基准选择不当）。 * **注意事项**：随机基准/三数取中可降低退化概率；面对大量重复值可用**三路划分**提升性能。 

给定 $n$ 个整数，请用快速排序按**升序**排序并输出。

* 第一行：一个整数 $n$； * 第二行：$n$ 个 32 位有符号整数。

输出一行，将这 $n$ 个数按升序排列，数之间以一个空格分隔。

数据范围：$1 \le n \le 10^5$。