1005 快速排序

Dear 丶 2022-09-11 12:24 109阅读 0赞

**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;
    }