sort

Time Limit: 6000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 45198    Accepted Submission(s): 13067

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
Hint
请用VC/VC++提交
 

Author
LL
 

Source
ACM暑期集训队练习赛（三） 

思路：

做这道题就是想看一下堆排序和sort快排哪个更快一点.事实证明两个速度差不多，都是NlogN。

sort：


heapsort：


代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int h[1000000+5];
int n;

// heapsort  N(NlogN)

void swap(int x,int y)
{
	int t;
	t=h[x];
	h[x]=h[y];
	h[y]=t;
}

void siftdown(int i)//传入一个需要向下调整的节点编号 
{
	int t,flag=0;
	while(i*2<=n&&flag==0)
	{
		if(h[i]<h[i*2])
		{
			t=i*2;
		}
		else
		{
			t=i;
		}
		if(i*2+1<=n)
		{
			if(h[t]<h[i*2+1])
			{
				t=2*i+1;
			}
		}
		if(t!=i)
		{
			swap(t,i);
			i=t;
		}
		else 
		{
			flag=1;
		}
	}
}

void creat()
{
	int i;
	for(i=n/2;i>=1;i--)
	{
		siftdown(i);
	}
}

void heapsort()
{
	while(n>1)
	{
		swap(1,n);
		n--;
		siftdown(1);
	} 
}



int main()
{
	
	int num,m;
	while(~scanf("%d%d",&num,&m))
	{
		for(int i=1;i<=num;i++)
		{
			scanf("%d",&h[i]);
		}
		n=num;
		creat();
		heapsort();
		for(int i=num;i>num-m+1;i--)
		{
			printf("%d ",h[i]);
		}
		printf("%d\n",h[num-m+1]); 
	}
	return 0;	
} 


//    sort O(NlogN)
//int main()
//{
//	
//	int num,m;
//	while(~scanf("%d%d",&num,&m))
//	{
//		for(int i=1;i<=num;i++)
//		{
//			scanf("%d",&h[i]);
//		}
//		sort(h+1,h+1+num);
//		for(int i=num;i>num-m+1;i--)
//		{
//			printf("%d ",h[i]);
//		}
//		printf("%d\n",h[num-m+1]); 
//	}
//	return 0;	
//}