数据结构实验之排序八：快速排序

Time Limit: 1000MS Memory Limit: 65536KB

Submit Statistic

Problem Description

给定N(N≤10^5)个整数，要求用快速排序对数据进行升序排列，注意不得使用STL。

Input

连续输入多组数据，每组输入数据第一行给出正整数N(≤10^5)，随后给出N个整数，数字间以空格分隔。

Output

输出排序后的结果，数字间以一个空格间隔，行末不得有多余空格。

Example Input

8
49 38 65 97 76 13 27 49

Example Output

13 27 38 49 49 65 76 97

Hint

Author

#include <stdio.h>

void  list(int a[], int left, int right)
{
    int low=left;
    int key=a[left];
    int length=right;
    if(left>=right)
        return ;
    while(low<length)
    {
        while(key<=a[length]&&low<length)
        {
            length--;
        }
        a[low]=a[length];
        while(key>=a[low]&&low<length)
        {
            low++;
        }
        a[length]=a[low];
    }
    a[low]=key;
    list(a, left, low-1);
    list(a, low+1, right);
}

int main()
{
    int a[345670];
    int i, n, t;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        list(a, 0, n-1);
        for(i=0; i<n-1; i++)
        {
            printf("%d ",a[i]);
        }
        printf("%d
", a[i]);
    }
    return 0;
}