快速排序

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

 1 #include <stdio.h>
 2 
 3 void quickSort(int a[],int left,int right);
 4 int array[1000001];
 5 
 6 int main(){
 7     int n;
 8     int m;
 9     int i;
10     
11     while(scanf("%d%d",&n,&m)!=EOF){
12         for(i=0;i<n;i++)
13             scanf("%d",&array[i]);
14             
15         quickSort(array,0,n-1);
16         
17         for(i=n-1;i>n-m-1;i--){
18             if(i==n-1)
19                 printf("%d",array[i]);
20                 
21             else
22                 printf(" %d",array[i]);
23         }
24         
25         printf("
");
26     }
27     
28     return 0;
29 }
30 
31 void quickSort(int a[],int left,int right){
32     int i;
33     int j;
34     int temp;
35     
36     i=left;
37     j=right;
38     temp=a[left];
39     
40     if(left>=right)
41         return;
42         
43     while(i!=j){
44         while(i<j && a[j]>=temp)
45             j--;
46             
47         if(i<j){
48             a[i]=a[j];
49         }
50             
51             
52         while(i<j && a[i]<=temp)
53              i++;
54              
55         if(i<j){
56             a[j]=a[i];
57         }
58     }
59     a[i]=temp;
60     
61     quickSort(a,left,i-1);
62     quickSort(a,i+1,right);    
63 }