changesort.cpp

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

#include "base.h"

void BubbleSort(SqList &L)
{//冒泡排序
	int i,j,hug;
	RedType t;

	for(i=1;i<=L.length-1;i++)
	{
		hug=1;
		for(j=1;j<=L.length-i;j++)
			if(LT(L.r[j+1].key,L.r[j].key))
			{
				t=L.r[j];
				L.r[j]=L.r[j+1];
				L.r[j+1]=t;
				hug=0;
			}
		if(hug==1)
			break;
	}
}

int Partition(SqList &L,int low,int high)
{//交换顺序表L中子表L.r[low..high]的纪录,枢轴记录到位,并返回其所在位置
 //此时在它之前(后)的记录均不大(小)于它
	int pivotkey;

	L.r[0]=L.r[low];
	pivotkey=L.r[low].key;
	while(low<high)
	{
		while(low<high&&L.r[high].key>=pivotkey)
			high--;
		L.r[low]=L.r[high];	
		while(low<high&&L.r[low].key<=pivotkey)
			low++;
		L.r[high]=L.r[low];
	}
	L.r[low]=L.r[0];
	return low;
}

void QSort(SqList &L,int low,int high)
{//对顺序表L中子序列L.r[low..high]作快速排序
	int pivotloc;

	if(low<high)
	{
		pivotloc=Partition(L,low,high);
		QSort(L,low,pivotloc-1);
		QSort(L,pivotloc+1,high);
	}
}

void QuickSort(SqList &L)
{//快速排序
	QSort(L,1,L.length);
}