heapsort.cpp

这是一段关于四种排序方法的完全源代码及其相互之间的比较,包括:Heap sort,Merge sort,Quick sort,Radix sort

#include <iostream.h>
#include <time.h>
#include <stdlib.h>
#include <windows.h>

void sift_down(int A[],int n,int i);
void makeheap(int A[],int n);
void heapsort(int A[],int n);

void main()
{
	srand(time(0));
	int n;
	cout<<"请输入n:";
	cin>>n;
	int *a;
	a=new int[n+1];
	for(int i=1;i<n+1;i++)
	{
		a[i]=rand();
	}
	cout<<"生成随机数组为:"<<'\n';
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<'\t';
	}
	cout<<endl;
	heapsort(a,n);
	cout<<"堆排序后数组为:"<<'\n';
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<'\t';
	}
	cout<<endl;
	delete a;

}
void heapsort(int A[],int n)
{
	int t;
	makeheap(A,n);
	for(int j=n;j>=2;j--)
	{
		t=A[1];
		A[1]=A[j];
		A[j]=t;
		sift_down(A,j-1,1);
	}
}


void makeheap(int A[],int n)
{
	for(int i=n/2;i>=1;i--)
	{
		sift_down(A,n,i);
	}
}

void sift_down(int A[],int n,int i)
{
	int done=0,t;
	if(i>n/2)
	{
		return;
	}
	else
	{
		while(i<=n/2&&done==0)
		{
			i=2*i;
			if(i+1<=n&&A[i+1]>A[i])
			{
				i=i+1;
			}
			if(A[i/2]<A[i])
			{
				t=A[i/2];
				A[i/2]=A[i];
				A[i]=t;
			}
			else
			{
				done=1;
			}
		}
	}
}