给定数组大小n和数组q[n]，对数组进行排序。
快速排序的原理：基于分治
（1）确定分界点x：可以取x为q[l], q[l + r >> 1]，q[r], 或者数组中间随机一个值（建议取q[l + r >> 1], 原因在后面说）。这里l和r是当前待排序数组的左右端点。
（2）重新调整区间，使得调整后的区间，小于等于x的数都在x的左边，大于等于x的数都在x的右边（和x相等的数在左边、右边都可）。 调整区间的方法有两种，后面说。
（3）递归处理分界点的左右两段，最后拼接起来的区间就是有序的了。
调整区间的方法（一）：
(1)额外开两个数组a[], b[]
(2)扫描数组q[l~r]，如果当前的数q[i] <= x, 则把q[i]存入数组a. 即q[i] -> a[];
如果当前的数q[i]>=x,则把q[i]存入数组b. 即q[i] -> b[i];
(3)此时a[], b[]就分别是q[]的左半部分和右半部分了，把它们的值赋给q[]. 即a[] -> q[], b[] -> q[]。
这种方法的优点是好理解。缺点也显而易见：空间开销大。
调整区间的方法（二）：
有一种用双指针来调整区间的优雅的方法。
（1）一开始，我们让两个指针i和j分别指向区间的两个端点l和r；
（2）当q[i] < x时，i向右移动，若找到q[i] >= x，则i停下。 j向左移动，直到i和j相遇或者q[j] <= x；
（3）若i和j未相遇，则i和j此时指向的元素都是错位的，交换这两个数的位置：swap(q[i], q[j]);
（4) 重复上面的步骤，知道i和j相遇。
这种划分区间方法的正确性证明：在任意时刻，左指针i左边的数都是小于等于x的，j右边的数都是大于等于x的，当i与j相遇时，
相遇点左边的数都小于等于x，相遇点右边的数都大于等于x，故区间调整正确。
这题代码如下：
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N];
void quick_sort(int q[], int l, int r) {
if(l >= r) { //如果区间没有数，或者只有一个数，直接return
return ;
}
int x = q[l + r >> 1], i = l - 1, j = r + 1; //分界点x最好取中位数q[l + r >> 1],因为如果取边界q[l]或者q[r],且区间是升序或降序时，时间复杂度为O(n^2)，在这题会超时
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;
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d", &q[i]);
}
quick_sort(q, 0, n - 1);
for(int i = 0; i < n; ++i) {
printf("%d ", q[i]);
}
return 0;
}