#include "base.h"

int SelectMinKey(SqList L,int begin)
{//在L.r[begin..L.length]中選擇key最小的記錄
	int min;
	int i;

	min=begin;
	for(i=begin+1;i<=L.length;i++)
	{
		if(LT(L.r[i].key,L.r[min].key))
			min=i;
	}
	return min;
}

void SelectSort(SqList &L)
{//簡(jiǎn)單選擇排序
	int i,j;
	RedType t;

	for(i=1;i<L.length;i++)
	{
		j=SelectMinKey(L,i);
		if(i!=j)
		{
			t=L.r[i];
			L.r[i]=L.r[j];
			L.r[j]=t;
		}
	}
}

void HeapAdjust(HeapType &H,int s,int m)
{//已知H.r[s..m]中記錄的關(guān)鍵字除H.r[s].key之外均滿足堆定義，本函數(shù)調(diào)整H.r[s]
 //的關(guān)鍵字，使H.r[s..m]成為一個(gè)大頂堆
	RedType rc;
	int j;
	
	rc=H.r[s];
	for(j=2*s;j<=m;j*=2)
	{
		if(j<m&&LT(H.r[j].key,H.r[j+1].key))	//沿key較大的孩子節(jié)點(diǎn)向下篩選
			j++;								//j為key較大的記錄的下標(biāo)
		if(!LT(rc.key,H.r[j].key))
			break;								//rc應(yīng)插在s上
		H.r[s]=H.r[j];
		s=j;
	}
	H.r[s]=rc;
}

void HeapSort(HeapType &H)
{//堆排序
	int i;
	RedType t;

	for(i=H.length/2;i>0;i--)					//把H.r[1..length]建成大頂堆
		HeapAdjust(H,i,H.length);
	for(i=H.length;i>1;i--)
	{
		t=H.r[1];								//將堆頂記錄和當(dāng)前未經(jīng)排序子序列H.r[1..i]
		H.r[1]=H.r[i];							//中最后一個(gè)記錄交換
		H.r[i]=t;

		HeapAdjust(H,1,i-1);					//將H.r[1..i-1]重新調(diào)整為大頂堆
	}
}