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、使用内建sort函数
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int ans[1000001];
int main()
{
int n,m;
while (scanf("%d%d",&n,&m) != EOF)
{
for (int i = 0;i < n;i++)
{
scanf("%d",&ans[i]);
}
sort(ans,ans + n);
printf("%d",ans[n - 1]);
for(int i = n - 2;m > 1;m--,i--)
{
printf(" %d",ans[i]);
}
printf("
");
}
return 0;
}
2、使用内建优先队列
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
int main()
{
int N,M;
while (~scanf("%d%d",&N,&M))
{
priority_queue<int>que;
bool first = true;
int tmp;
while (N--)
{
scanf("%d",&tmp);
que.push(tmp);
}
while (M--)
{
first?printf("%d",que.top()):printf(" %d",que.top());
que.pop();
first = false;
}
printf("
");
}
return 0;
}
3、使用内部堆函数
#include <cstdio>
#include <algorithm>
using namespace std;
static int a[1000000];
int main()
{
int i,n,m;
while(EOF != scanf("%d %d",&n,&m))
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
make_heap(a,a+n);
printf("%d",a[0]);
for(i=1;i<m;i++)
{
pop_heap(a,a+n-i+1);
printf(" %d",a[0]);
}
printf("
");
}
return 0;
}
4、手写最大堆
#include<stdio.h>
#include<string.h>
const int maxn = 1000005;
int heap[maxn],sz = 0;
void push(int x)
{
int i = sz++;
while (i > 0)
{
int p = (i - 1)/2;
if (heap[p] >= x) break;
heap[i] = heap[p];
i = p;
}
heap[i] = x;
}
int pop()
{
int ret = heap[0];
int x = heap[--sz];
int i = 0;
while (i*2+1<sz)
{
int a = i*2+1,b = i*2+2;
if (b < sz && heap[b]>heap[a]) a = b;
if (heap[a] <= x) break;
heap[i] = heap[a];
i = a;
}
heap[i] = x;
return ret;
}
int main()
{
int n,m,tmp;
while (~scanf("%d%d",&n,&m))
{
sz = 0;
memset(heap,0,sizeof(heap));
for (int i = 0;i < n;i++) scanf("%d",&tmp),push(tmp);
for (int i = 1;i < m;i++) printf("%d ",pop());
printf("%d
",pop());
}
return 0;
}
5、手写堆排序（从大到小）
#include<bits/stdc++.h>
using namespace std;
#define LeftChild(i) (2*(i)+1)
const int maxn = 1000005;
int a[maxn];
void PercDown(int a[],int i,int N)
{
int Child;
int tmp;
for (tmp = a[i];LeftChild(i) <N;i = Child)
{
Child = LeftChild(i);
if (Child != N - 1 && a[Child+1] < a[Child])
Child++;
if (tmp > a[Child])
a[i] = a[Child];
else
break;
}
a[i] = tmp;
}
void Heapsort(int a[],int N)
{
int i;
for (i = N/2;i >= 0;i--)
PercDown(a,i,N);
for (i = N-1;i > 0;i--)
{
swap(a[0],a[i]);
PercDown(a,0,i);
}
}
int main()
{
int n,m;
while (~scanf("%d%d",&n,&m))
{
for (int i = 0;i < n;i++) scanf("%d",&a[i]);
Heapsort(a,n);
printf("%d",a[0]);
for (int i = 1;i < m;i++) printf(" %d",a[i]);
printf("
");
}
return 0;
}
6、手写堆排序（从小到大）
#include<cstdio>
#include<algorithm>
using namespace std;
#define LeftChild(i) (2*(i)+1)
const int maxn = 1000005;
int a[maxn];
void PercDown(int a[],int i,int N)
{
int Child;
int tmp;
for (tmp = a[i];LeftChild(i) <N;i = Child)
{
Child = LeftChild(i);
if (Child != N - 1 && a[Child+1] > a[Child])
Child++;
if (tmp < a[Child])
a[i] = a[Child];
else
break;
}
a[i] = tmp;
}
void Heapsort(int a[],int N)
{
int i;
for (i = N/2;i >= 0;i--)
PercDown(a,i,N);
for (i = N-1;i > 0;i--)
{
swap(a[0],a[i]);
PercDown(a,0,i);
}
}
int main()
{
int n,m;
while (~scanf("%d%d",&n,&m))
{
for (int i = 0;i < n;i++) scanf("%d",&a[i]);
Heapsort(a,n);
printf("%d",a[n-1]);
for (int i = n-2;i > n-1 - m;i--) printf(" %d",a[i]);
printf("
");
}
return 0;
}
7、手写快速排序（从大到小）
#include<bits/stdc++.h>
using namespace std;
#define Cutoff (3)
const int maxn = 1000005;
int a[maxn];
void InsertionSort(int a[],int N)
{
int i,j,tmp;
for (i = N - 2;i >= 0;i--)
{
tmp = a[i];
for (j = i;j < N - 1 && a[j + 1] > tmp;j++)
a[j] = a[j + 1];
a[j] = tmp;
}
}
int median3(int a[],int left,int right)
{
int center = (left + right) / 2;
if (a[left] < a[center])
swap(a[left],a[center]);
if (a[left] < a[right])
swap(a[left],a[right]);
if (a[center] < a[right])
swap(a[center],a[right]);
swap(a[center],a[left + 1]);
return a[left + 1];
}
void qsort(int a[],int left,int right)
{
int i,j,pivot;
if (left + Cutoff <= right)
{
pivot = median3(a,left,right);
i = left + 1;j = right;
for (;;)
{
while (a[++i] > pivot){}
while (a[--j] < pivot){}
if (i < j) swap(a[i],a[j]);
else break;
}
swap(a[j],a[left + 1]);
qsort(a,left,j - 1);
qsort(a,j + 1,right);
}
else InsertionSort(a + left,right - left + 1);
}
int main()
{
int n,m;
while (~scanf("%d%d",&n,&m))
{
for (int i = 0;i < n;i++) scanf("%d",&a[i]);
qsort(a,0,n - 1);
printf("%d",a[0]);
for (int i = 1;i < m;i++) printf(" %d",a[i]);
printf("
");
}
return 0;
}
8、手写快速排序（从小到大）
#include<bits/stdc++.h>
using namespace std;
const int Cutoff = 10;
const int maxn = 1000005;
int a[maxn];
void InsertionSort(int a[],int N)
{
int i,j,tmp;
for (i = 1;i < N;i++)
{
tmp = a[i];
for (j = i;j > 0 && a[j - 1] > tmp;j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
int median3(int a[],int left,int right)
{
int center = (left + right) / 2;
if (a[left] > a[center])
swap(a[left],a[center]);
if (a[left] > a[right])
swap(a[left],a[right]);
if (a[center] > a[right])
swap(a[center],a[right]);
swap(a[center],a[right-1]);
return a[right-1];
}
void qsort(int a[],int left,int right)
{
int i,j,pivot;
if (left + Cutoff <= right)
{
pivot = median3(a,left,right);
i = left;j = right-1;
for (;;)
{
while (a[++i] < pivot){}
while (a[--j] > pivot){}
if (i < j) swap(a[i],a[j]);
else break;
}
swap(a[i],a[right-1]);
qsort(a,left,i - 1);
qsort(a,i + 1,right);
}
else InsertionSort(a + left,right - left + 1);
}
int main()
{
int n,m;
while (~scanf("%d%d",&n,&m))
{
for (int i = 0;i < n;i++) scanf("%d",&a[i]);
qsort(a,0,n - 1);
printf("%d",a[n - 1]);
for (int i = n - 2;i > n - m - 1;i--) printf(" %d",a[i]);
printf("
");
}
return 0;
}