heapsort.c

堆排序

#include <stdio.h>
//#include "buildarray.c"
//#include "sort.h"

unsigned long int compare=0,move=0;


void crheap(int *p,int n,int s)
{
	int temp,num_S,num_C;
	temp=*(p+s);
	move++;
	num_S=s;
	num_C=2*num_S+1;
	while(num_C<n){
		if(num_C<n-1&&*(p+num_C)<*(p+num_C+1))
		num_C++;
		compare++;
		if(temp<*(p+num_C)){
			compare++;
			*(p+num_S)=*(p+num_C);
			move++;
			num_S=num_C;
			num_C=2*num_S+1;
		}
		else{
			compare++;
			break;
		}
				
	}
	*(p+num_S)=temp;
	move++;	
}


void HeapSort(int *p,int n)
{
	int i,k,temp;
	int count;
	for(i=n/2-1;i>=0;i--)
		crheap(p,n,i);
	for(k=n-1;k>=1;k--){
		temp=*(p+0);
		*(p+0)=*(p+k);
		*(p+k)=temp;
		move+=3;
		crheap(p,k,0);
	}
	printf("the queue sorted by heapsort is:\n");
	for(i=0;i<n;i++){
		printf("%d	",*(p+i));
		count++;
		if(count%10==0)
		printf("\n");
	}
}


main()
{
	int Queue[9]={8,5,6,9,2,1,3,4,7};
	HeapSort(Queue,9);
	printf("HeapSort compare=%ld,move=%ld",compare,move);
	printf("\n");	
}