selectionsort.cpp

各种内部排序算法的实现和比较

#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)
{//简单选择排序
	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]中记录的关键字除H.r[s].key之外均满足堆定义，本函数调整H.r[s]
 //的关键字，使H.r[s..m]成为一个大顶堆
	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较大的孩子节点向下筛选
			j++;								//j为key较大的记录的下标
		if(!LT(rc.key,H.r[j].key))
			break;								//rc应插在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];								//将堆顶记录和当前未经排序子序列H.r[1..i]
		H.r[1]=H.r[i];							//中最后一个记录交换
		H.r[i]=t;

		HeapAdjust(H,1,i-1);					//将H.r[1..i-1]重新调整为大顶堆
	}
}