sort
Time Limit : 6000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Problem Description
给你n个整数，请按从大到小的顺序输出其中前m大的数。
Input
每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。
Output
对每组测试数据按从大到小的顺序输出前m大的数。
Sample Input
5 3 3 -35 92 213 -644
Sample Output
213 92 3
就是快排非常简单的应用。。。。
#include<stdio.h>
int s[1000001];
/*int partition(int *a,int l,int h)//注释掉的是开始写的从小到大的
{int v=a[l];int i=l,j=h+1;while(1){while(a[++i]<v)if(i==h)break;while(a[--j]>v)if(j==l)break;if(i>=j)break;int t=a[i];a[i]=a[j];a[j]=t;}int t=a[j];a[j]=a[l];a[l]=t;return j;
}
void q_sort(int *a,int l,int h)
{if(l>=h)return ;int j=partition(a,l,h);q_sort(a,l,j-1);q_sort(a,j+1,h);
}*/
int partition(int *a,int l,int h)//这是从大到小的，都一样。。。。
{int v=a[l];int i=l,j=h+1;while(1){while(a[++i]>v)if(i==h)break;while(a[--j]<v)if(j==l)break;if(i>=j)break;int t=a[i];a[i]=a[j];a[j]=t;}int t=a[j];a[j]=a[l];a[l]=t;return j;
}
void q_sort(int *a,int l,int h)
{if(l>=h)return ;int j=partition(a,l,h);q_sort(a,l,j-1);q_sort(a,j+1,h);
}
int main()
{int n,m,i;while(~scanf("%d%d",&n,&m)){for(i=1;i<=n;++i){scanf("%d",&s[i]);}q_sort(s,1,n);printf("%d",s[1]);for(i=2;i<=m;++i)printf(" %d",s[i]);//printf("%d",s[n]);//for(i=n-1;i>n-m;i--)printf(" %d",s[i]);printf("\n");}return 0;
}
