As Easy As A+B-蒲公英云

As Easy As A+B

男娘i 2024-02-18 23:00 141阅读 0赞

As Easy As A+B

小Q有很多书籍，有一天他想整理一下，把这些书按书的大小从小到大摆起来，请你帮帮他好么

Input

输入包含多组测试。第一行输入一个整数T代表测试的个数，接下来的T行每一行包含一个整数N(1<=N<=1000)，代表书本的本数，接下来N个数代表这N本书的大小

Output

对每个测试，输出排好序的结果

Sample Input

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

Sample Output

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

Hint

输出时每一个测试的最后一个数后面没有空格

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void paixu(int a[], int l, int r);
int main()
{
    int t, i, x;
    int a[1010];
    while(scanf("%d", &t) != EOF)
    {
        while(t--)
        {
            memset(a,0,sizeof(a));
            scanf("%d", &x);
            for(i = 0; i < x; i++)
            {
                scanf("%d", &a[i]);
            }
            paixu(a,0,x-1);
            for(i = 0; i < x; i++)
            {
                if(i == x - 1)
                {
                    printf("%d\n", a[i]);
                }
                else
                {
                    printf("%d ", a[i]);
                }
            }
        }
    }
    return 0;
}
void paixu(int a[], int l, int r)
{
    int i = l, j = r;
    int x = a[i];
    if(i >= j)
    {
        return;
    }
    else
    {
        while(i < j)
        {
            while(i < j && a[j] >= x)
            {
                j--;
            }
            a[i] = a[j];
            while(i < j && a[i] <= x)
            {
                i++;
            }
            a[j] = a[i];
        }
        a[i] = x;
        paixu(a,l,i-1);
        paixu(a,i+1,r);
    }
}