Description

给定一维int型数组a[0,1,...,n-1], 使用快速排序方法, 对其进行从小到大排序, 请输出递归过程中自顶自下第二层的划分结果, 其中最顶层为第一层, 即最终的排序结果层. 
划分时请用第1个元素作为划分基准, 并使用课件上的方法进行一次扫描实现划分.

Input

输入第1行有一个int型正整数m (m<100), 表示有m行输入.
每行输入的第一个数为int型正整数n (8<n<1000), 后面接着输入n个int型整数.

Output

对每组数据, 输出自顶自下第二层的划分结果.

Sample Input

2
11 6 3 7 8 5 1 4 2 4 9 10
12 6 3 7 8 4 5 1 11 2 4 9 10

Sample Output

2 3 1 4 4 5 6 7 8 9 10
2 3 1 4 4 5 6 10 8 7 9 11

示例代码:
#include <stdio.h>
int res[1000] = {0};
int a[1000] = {0};
int n;
int quicksort(int low, int high, int depth) {
    if(low >= high) {
        return 0;
    }
    if(low+1 == high) {
        if(a[low] > a[high]) {
            int temp = a[low];
            a[low] = a[high];
            a[high] = a[low];
        }
        return 0;
    }
    int p = low;
    for(int i=low; i<=high; i++) {
        if(a[low] > a[i]) {
            p++;
            int temp = a[p];
            a[p] = a[i];
            a[i] = temp;
        }
    }
    int temp = a[low];
    a[low] = a[p];
    a[p] = temp;
    
    if(depth==1) {
        res[p] = a[p];    
    }
    if(depth==2) {
        for(int i=low; i<=high; i++) {
            res[i] = a[i];
        }
    }

    quicksort(low, p-1, depth+1);
    quicksort(p+1, high, depth+1);
    
    return 0;
}

int solve() {
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }

    quicksort(0, n-1, 1);

    for(int i=0; i<n; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");
    /*
    for(int i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");*/
    return 0;
}

int main() {
    int m;
    scanf("%d", &m);
    for(int i=0; i<m; i++) {
        solve();
    }
    return 0;
}