堆排序

[c]代码库

void HeapAdjust ( S_TBL *h，int s，int m )
{/*r[s…m]中的记录关键码除r[s]外均满足堆的定义，本函数将对第s 个结点为根的子树筛选，使其成为大顶堆*/
	rc=h->r[s];
	for ( j=2*s; j<=m; j=j*2 ) /* 沿关键码较大的子女结点向下筛选*/
	{
		if ( j<m&&h->r[j].key<h->r[j+1].key )
			j=j+1; /* 为关键码较大的元素下标*/
		if ( rc.key<h->r[j].key ) break; /* rc 应插入在位置s 上*/
		h->r[s]=h->r[j];
		s=j; /* 使s 结点满足堆定义*/
	}
	h->r[s]=rc; /* 插入*/
}
void HeapSort ( S_TBL *h )
{
	for ( i=h->length/2; i>0; i-- ) /* 将r[1..length]建成堆*/
		HeapAdjust ( h，i，h->length );
	for ( i=h->length; i>1; i-- )
	{
		h->r[1]<-->h->r[i]; /* 堆顶与堆低元素交换*/
		HeapAdjust ( h，1，i-1 ); /*将r[1..i-1]重新调整为堆*/
	}
}