dui.cpp

堆排序 稳定的排序 复杂度为N（logN ） 也是一种快速的排序

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
int shuzu[10000];
using namespace std;
int huifu(int num,int geshu)
{
	int temp,w=1;
	int k1,k2;
	
	while(w)
	{
		w=0;
		k1=2*num+1;
	    k2=2*num+2;
	   if(k1>=geshu)
		return 1;
       if(shuzu[k1]>shuzu[num])
	   {
		  if(shuzu[k2]>shuzu[k1])
		  {
		     temp=shuzu[k2];
		     shuzu[k2]=shuzu[num];
		     shuzu[num]=temp;
		     w=1;
		     num=k2;
		  }
	      else
		  {
			temp=shuzu[k1];
			shuzu[k1]=shuzu[num];
			shuzu[num]=temp;
			w=1;
			num=k1;
		  }
	   }
	  else
	  {
         if(shuzu[k2]>shuzu[num])
		 {
		   temp=shuzu[k2];
		   shuzu[k2]=shuzu[num];
		   shuzu[num]=temp;
		   w=1;
		   num=k2;
		 }
	  }
	}
	return 1;
}
void gouzao(int geshu)
{
	int num,k;
	int temp;
	num=geshu;
	if(num%2==1)
	  num++;
	while(num)
	{
       k=num/2-1;
	   huifu(k,geshu);
	   num-=2;
	}
	
}
void duipai(int geshu)
{
	int temp;
	while(geshu)
	{
	  temp=shuzu[0];
	  shuzu[0]=shuzu[geshu];
	  shuzu[geshu]=temp;
	  geshu--;
	  huifu(0,geshu);
	}
}
void dayin(int geshu)
{
	int i;
	for(i=0;i<geshu;i++)
		printf("%d   ",shuzu[i]);
}
int main()
{
	freopen("a.txt","r",stdin);
	freopen("b.txt","w",stdout);
	memset(shuzu,0,sizeof(shuzu));
	int num;
	int geshu=0;
	while(scanf("%d",&num)!=EOF)
	{
		shuzu[geshu]=num;
		geshu++;
	}
	gouzao(geshu-1);
//	printf("okokokok");
	duipai(geshu-1);
    dayin(geshu);
	return 0;
}