快速排序
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目背景
快速排序用到了分治的思想。
首先在这个序列中随便找一个数作为基准数。为了方便，取中间位置的数为基准数。接下来，需要将这个序列中所有比基准数大的数放在它的右边，比基准数小的数放在它的左边。可以通过“交换”达到这一目的。
继续对左右两个序列做同样操作。
题目描述
输入一个数组的长度n和所有元素，将数组按从小到大的顺序排序。
注：本题为模板题，仅作为教学使用。
输入格式
第一行一个整数n(1≤n≤10^6)；
第二行是n个不大于100000的正整数。
输出格式
n个用空格分隔的整数，为排序后的数组。
输入/输出样例
10
2 7 9 1 6 3 4 1 5 8
1 1 2 3 4 5 6 7 8 9
说明/提示
时间1000ms，内存256MiB