天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

快速排序

Posted on 2012-05-08 17:11 hoshelly 阅读(127) 评论(0)  编辑 收藏 引用 所属分类: Programming
输入

第一行包含一个整数T,表示有T组数据。对于每组数据:第一行包含一个数字N(<100),表示该组数据由N个元素;第二行包含N个数,就是这N个元素的值( <10000 )。

输出

对于每组数据输出一行,包含排序好后的N个元素,要求从小到大排序,相邻2个元素间有个空格,末尾无空格有个回车。

样例输入
1 3 1 3 2
样例输出
1 2 3


#include<stdio.h>
void swap(int a[],int low,int high)
{
    
int temp=a[low];
    a[low]
=a[high];
    a[high]
=temp;
}

int partition(int a[],int low,int high)
{
    
int pivotkey=a[low];
    
while(low<high)
    {
        
while(low<high && a[high]>=pivotkey)
            high
--;
        swap(a,low,high);
        
while(low<high && a[low]<=pivotkey)
            low
++;
        swap(a,low,high);
    }
    
return low;
}

void qsort(int a[],int low,int high)
{
    
int pivot;
    
if(low<high)
    {
        pivot
=partition(a,low,high);
        qsort(a,low,pivot
-1);
        qsort(a,pivot
+1,high);
    }
}


int main()
{
    
int n,m,i,a[102];
    scanf(
"%d",&n);
    
while(n--)
    {
        scanf(
"%d",&m);
        
for(i=0;i<m;i++)
        {
            scanf(
"%d",&a[i]);
        }

        qsort(a,
0,m-1);

            
        
for(i=0;i<m;i++)
        {
            printf(
"%d ",a[i]);
        }
        printf(
"\n");

    }

    
return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理