heap.cpp

基于C++的排序各种排序操作,包括快速排序,shell排序,随机排序,选择排序等

#include<stdio.h>
void adjust(int,int);
int data[11]={0,75,23,98,44,57,12,29,64,38,82};

void main()
{
	int i,k,temp;
	printf("\n<<Heap sort>>\n");
	printf("\nNumber:");
	for(k=1;k<=10;k++)
		printf("%d ",data[k]);
	puts("");
	for(k=0;k<60;k++)printf("-");
	for(i=10/2;i>0;i--)
		adjust(i,10);
	printf("\nHeap  :");
	for(k=1;k<=10;k++)
		printf("%d ",data[k]);
	for(i=9;i>0;i--)
	{
		temp=data[i+1];
		data[i+1]=data[1];
		data[1]=temp;   /*将树根和最后的节点交换*/
		adjust(1,i);    /*再重新调整为堆树*/
        printf("\nAccess:");
		for(k=1;k<=10;k++)
			printf("%d ",data[k]);
	}
	puts("");
	for(k=0;k<60;k++)printf("-");
	printf("\nSorting:");
	for(k=1;k<=10;k++)
		printf("%d ",data[k]);
}

void adjust(int i,int n)  /*将数据调整为堆树*/
{
	int j,k,done=0;
	k=data[i];
	j=2*i;
	while((j<=n)&&(done==0))
	{
		if((j<n)&&(data[j]<data[j+1]))j++;
		if(k>=data[j])done=1;
		else
		{
			data[j/2]=data[j];
			j*=2;
		}
	}
	data[j/2]=k;
}