listsort.cpp.~1~

我们高校的数据结构与算法的教师讲义,适合想自学数据结构的朋友参考.

//---------------------------------------------------------------------------
//基于数组的一些排序： 堆排序
//---------------------------------------------------------------------------

#include "listsort.h"

void swap(Datatype& d1, Datatype& d2)
{
	Datatype temp=d1;
	d1=d2;
	d2=temp;
}


//下面是堆排序
void heapajust(Datatype *theArray, int s, int m)
{
	Datatype temp=theArray[s];
	int i=2*s+1;
	for (; i <= m;i=2*s+1) 
	{
		if (i<m && theArray[i+1].key>theArray[i].key) //找到哪个孩子比较大一点儿
		{
			i=i+1;
		}
		if (theArray[i].key>theArray[s].key) 
		{
			break;
		}
		theArray[s]=theArray[i];
		s=i;
	}
	theArray[s]=temp;

}

void HeapSort(Datatype *theArray, int n)
{
	int i;
	for (i=(n-1)/2; i >=0 ; i-- ) {
		heapajust(theArray,i,n-1);
	}
	for (i = n-1; i >=0; i--) {
		swap(theArray[0],theArray[i]);
		heapajust(theArray,0 , i-1);
	}
}