heapsort.cpp

来自「常用算法与数据结构原代码」· C++ 代码 · 共 40 行

template <class T>
void Sift(T elem[],int n,int s)
{
	int j;
	T t;
	t=elem[s];
	j=2*s+1;
	while (j<n)
	{
		if (j<n-1 && elem[j]<elem[j+1])
			j++;
		if (t<elem[j])
		{
			elem[s]=elem[j];
			s=j;
			j=2*s+1;
		}
		else 
			break;
	}
	elem[s]=t;
}

template <class T>
void HeapSort(T elem[],int n)
{
	int i;
	T t;
	for (i=n/2-1;i>=0;i--)
		Sift(elem,n,i);
	for (i=n-1;i>=1;i--)
	{
		t=elem[0];
		elem[0]=elem[i];
		elem[i]=t;
		Sift(elem,i,0);
	}

}