`/*
快速排序的分治思想：
1.确定分界点 第一个q[l]，中间q[l+r>>1]，随机q[r]都可以
2.调整这两个区间， 所有<=x 在左边， >= x 在右边
3.递归处理，给两个区间排序

实现：
（1）暴力法：开两个数组，单独存
（2）*优美法：两个指针分别从两边移动，直至相遇/穿过

*/

include

using namespace std;
const int n = 1e6 * 10; //n = 10的6次方
int q[n];
void quick_sortint (q[], int l, int r){
int x = q[l + r >> 1] //x=中间的数
int i = l - 1, j = r + 1; //i和j分别指向数组两边边界
if(r == l) return;//出口，当两个指针重合时
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 ++)
couy << q[i] << " ";
}
}
return 0;

}`