输出前 k 大的数

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 int a[100010];
 5 
 6 int cmp(const void *a,const void *b)
 7 { return (*(int *)a) - (*(int *)b); }
 8 
 9 //将a[]数组下标区间[start,end]前k大的数放到数组下标在[start,end]范围的末尾部分.
10 void FindMaxK(int a[],int start,int End,int k)
11 {
12     if(start-End+1==k) return;//若是元素个数刚好就是k个，则可以直接返回. 
13     int i=start,j=End,key=a[start];
14     while(i<j)
15     {
16         while(i<j&&a[j]>=key) --j;
17         a[i]=a[j];
18         while(i<j&&a[i]<=key) ++i;
19         a[j]=a[i];
20     }
21     a[i]=key;
22     if(End-i+1==k) return;//数组后半段的元素个数为End-i+1,刚好够k个 
23     else if( End-i+1 > k) FindMaxK(a,i+1,End,k);//数组后半段的元素个数多于k个 
24     else FindMaxK(a,start,i-1,k-(End-i+1) );//数组后半段元素个数不够k个。所以要在前半段继续寻找k-（End-i+1）这么多个。 
25 }
26 int main()
27 {
28     int n,k;
29 
30     scanf("%d",&n);
31     for(int i = 0;i <n; ++i) scanf("%d",&a[i]);
32     scanf("%d",&k);
33     
34     FindMaxK(a,0,n-1,k);
35 
36     qsort(a+n-k,k,sizeof(a[0]),cmp);
37     for(int i = n-1;i >= n-k; --i) printf("%d\n",a[i]);
38     return 0;
39 }

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int a[100010];
 7 
 8 void swap(int & a,int & b)
 9 {  int tmp = a;  a = b;  b = tmp;  }
10 
11 //将a[]数组下标区间[start,end]前k大的数放到数组下标在[start,end]范围的末尾部分.
12 void FindMaxK(int a[],int start,int End,int k)
13 {
14     if(start-End+1==k) return;//若是元素个数刚好就是k个，则可以直接返回. 
15     int i=start,j=End,key=a[start];
16     while(i<j)
17     {
18         while(i<j&&a[j]>=key) --j;
19         swap(a[i],a[j]);
20         while(i<j&&a[i]<=key) ++i;
21         swap(a[i],a[j]);
22     }
23     if(End-i+1==k) return;//数组后半段的元素个数为End-i+1,刚好够k个 
24     else if( End-i+1 > k) FindMaxK(a,i+1,End,k);//数组后半段的元素个数多于k个 
25     else FindMaxK(a,start,i-1,k-(End-i+1) );//数组后半段元素个数不够k个。所以要在前半段继续寻找k-（End-i+1）这么多个。 
26 }
27 int main()
28 {
29     int n,k;
30     
31     scanf("%d",&n);
32     for(int i = 0;i <n; ++i) scanf("%d",&a[i]);
33     scanf("%d",&k);
34     
35     FindMaxK(a,0,n-1,k);
36 
37     sort(a+n-k-1,a+n);
38     for(int i = n-1;i >= n-k; --i)
39         printf("%d\n",a[i]);
40     return 0;
41 }