sort.cpp

这是同一个数据结构的课程设计,由C++语言编写的

#include "sort.h" 


//------------------------------------------------------------------------//

//对顺序表R中的记录R[1..n]按递增序进行插入排序
template <class T>
void sort<T>::Insertion(T R[])
{ 
    int i, j;
    for (i=2; i<=size; i++) //依次插入R[2]，…，R[n]
	{
		if (R[i] < R[i-1])  //若R[i]大于等于有序区中所有的keys，则R[i]应在原有位置上
		{
			R[0] = R[i];    //R[0]是哨兵，且是R[i]的副本
			j = i-1; 
			do              //从右向左在有序区R[1．．i-1]中查找R[i]的插入位置
			{ 
				R[j+1] = R[j];  //将关键字大于R[i]的记录后移
				j--;
			}
			while(R[0] < R[j]); //当R[i] >= R[j]时终止

			R[j+1] = R[0];      //R[i]插入到正确的位置上
		}
	}
}
//------------------------------------------------------------------------//

//希尔排序
template <class T>
void sort<T>::Shell(T R[])
{
	int increment = size;   //增量初值，不妨设size>0
    do
	{
		increment = increment / 3 + 1;  //求下一增量
        ShellPass(R, increment); //一趟增量为increment的Shell插入排序
	}
	while(increment > 1);
}

//希尔排序中的一趟排序，d为当前增量
template <class T>
void sort<T>::ShellPass(T R[], int d) 
{
	for (int j, i=d+1; i<=size; i++)  //将R[d+1..size]分别插入各组当前的有序区
	{
		if (R[i] < R[i-d])
		{
			R[0] = R[i];        //R[0]只是暂存单元，不是哨兵
			j = i-d;     
			do 
			{                   //查找R[i]的插入位置
				R[j+d] = R[j];  //后移记录
				j = j-d;        //查找前一记录
			}
			while(j>0 && R[0] < R[j]);
			R[j+d] = R[0];     //插入R[i]到正确的位置上
		}
	}
}
//------------------------------------------------------------------------//

template <class T>
void sort<T>::Selection(T R[])
{
	int i, j, k;
	for (i=1; i<size; i++)  //做第i趟排序(1≤i≤size-1)
	{
		k = i;
		for (j=i+1; j<=size; j++) //在当前无序区R[i..n]中选key最小的记录R[k]
			if (R[j] < R[k])
				k=j;	     		//k记下目前找到的最小关键字所在的位置
		if(k != i)  //交换R[i]和R[k]
		{ 
			R[0] = R[i];
			R[i] = R[k];
			R[k] = R[0]; //R[0]作暂存单元
        }
    }
}
//------------------------------------------------------------------------//

//R（l..n)是待排序的文件，采用自下向上扫描，对R做冒泡排序
template <class T>
void sort<T>::Bubble(T R[])
{ 
	int i, j;
    bool exchange;        //交换标志

    for(i=1; i<size; i++)    //最多做size-1趟排序
	{   
		exchange = false;     //本趟排序开始前，交换标志应为假
		for(j=size-1; j>=i; j--) //对当前无序区R[i..n]自下向上扫描
		{
			if(R[j+1] < R[j])  //交换记录
			{
				R[0] = R[j+1];  //R[0]不是哨兵，仅做暂存单元
				R[j+1] = R[j];
				R[j] = R[0];
				exchange = true; //发生了交换，故将交换标志置为真
			}
		}
		if(!exchange) //本趟排序未发生交换，提前终止算法
			return;
    }
}
//------------------------------------------------------------------------//

//对R[low..high]快速排序
template <class T>
void sort<T>::Quick(T R[], int low, int high)
{ 
	int pivotpos;   //划分后的基准记录的位置

    if (low < high) //仅当区间长度大于1时才须排序
	{   
        pivotpos = Partition(R, low, high);  //对R[low..high]做划分

        Quick(R, low, pivotpos-1);  //对左区间递归排序
        Quick(R, pivotpos+1, high); //对右区间递归排序
	}
}

//调用Partition(R，low，high)时，对R[low..high]做划分，并返回基准记录的位置
template <class T>
int sort<T>::Partition(T R[], int i, int j)
{
	T pivot = R[i]; //用区间的第1个记录作为基准

	while (i < j)   //从区间两端交替向中间扫描，直至i=j为止
	{ 
		while (i < j && R[j] >= pivot) //pivot相当于在位置i上
			j--;         //从右向左扫描，查找第1个关键字小于pivot.key的记录R[j]

		if (i < j)   //表示找到的R[j]的关键字<pivot.key
			R[i++] = R[j]; //相当于交换R[i]和R[j]，交换后i指针加1

		while (i < j && R[i] <= pivot)  //pivot相当于在位置j上
			i++;     //从左向右扫描，查找第1个关键字大于pivot.key的记录R[i]

        if (i < j)   //表示找到了R[i]，使R[i].key>pivot.key
			R[j--] = R[i]; //相当于交换R[i]和R[j]，交换后j指针减1
	}
    R[i] = pivot;  //基准记录已被最后定位
	return i;
}
//------------------------------------------------------------------------// 

//对R[1..size]进行堆排序，不妨用R[0]做暂存单无
template <class T>
void sort<T>::Heap(T R[])
{
	int i;
	BuildHeap(R);   //将R[1..size]建成初始堆

	for (i=size; i>1; i--)  //对当前无序区R[1..i]进行堆排序，共做size-1趟
	{
		//将堆顶和堆中最后一个记录交换
		R[0] = R[1];
		R[1] = R[i];
		R[i] = R[0];

		Heapify(R, 1, i-1);  //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质
	}
}

//将R[low..high]调整为大根堆，除R[low]外，其余结点均满足堆性质
template <class T>
void sort<T>::Heapify(T R[], int low, int high)
{
	int large;  //large指向调整结点的左、右孩子结点中关键字较大者
	T temp = R[low];  //暂存调整结点

	for (large = 2*low; large <= high; large *= 2)  //R[low]是当前调整结点
	{
		//若large>high，则表示R[low]是叶子，调整结束;否则先令large指向R[low]的左孩子

		if (large < high && R[large] < R[large+1])
			large ++;   //若R[low]的右孩子存在且关键字大于左史兄弟，则令large指向它

		//现在R[large]是调整结点R[low]的左右孩子结点中关键字较大者

		if (temp >= R[large])  //temp始终对应R[low]
			break;  //当前调整结点不小于其孩子结点的关键字，结束调整

		R[low] = R[large];  //相当于交换了R[low]和R[large]
		low = large; //令low指向新的调整结点，相当于temp已筛下到large的位置
	}
	R[low] = temp;  //将被调整结点放入到最终的位置上
}

//将初始文件R[1..size]构造为大根堆
template <class T>
void sort<T>::BuildHeap(T R[])
{
	int i;
	
	//将R[i..size]调整为堆
	for (i=size/2; i>0; i--)
		Heapify(R, i, size);
}
//------------------------------------------------------------------------// 

//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]
template <class T>
void sort<T>::MergeEx(T R[], int low, int m, int high)
{     
	int i=low, j=m+1, p=0;   //置初始值

    T *R1 = NULL;     //R1是局部向量，若p定义为此类型指针速度更快
    R1 = new T[(high-low+1)*sizeof(T)];
    if (! R1)          //申请空间失败
	{
		cout << "Insufficient memory available!" << endl;
		return;
	}
    
	while (i <= m && j <= high) //两子文件非空时取其小者输出到R1[p]上
		R1[p++] = (R[i] <= R[j]) ? R[i++]: R[j++];

    while (i <= m)     //若第1个子文件非空，则复制剩余记录到R1中
		R1[p++] = R[i++];

    while (j <= high)  //若第2个子文件非空，则复制剩余记录到R1中
		R1[p++] = R[j++];

    for(p=0, i=low; i<=high; p++,i++)
		R[i] = R1[p];  //归并完成后将结果复制回R[low..high]
	
    if (! R1)
		delete [] R1;
}

//对R[1..n]做一趟归并排序
template <class T>
void sort<T>::MergePass(T R[], int length)
{
	int i;
    
	for (i=1; i+2*length-1<=size; i=i+2*length)  //归并长度为length的两个相邻子文件
		MergeEx(R, i, i+length-1, i+2*length-1);
           
	if(i+length-1 < size) //尚有两个子文件，其中后一个长度小于length
		MergeEx(R, i, i+length-1, size); //归并最后两个子文件

    //注意：若i≤n且i+length-1≥n时，则剩余一个子文件轮空，无须归并
}

//采用自底向上的方法，对R[1..n]进行二路归并排序
template <class T>
void sort<T>::Merge(T R[])
{
	int length;
    for(length=1; length<size; length*=2) //做[lgn]趟归并
		MergePass(R, length);  //有序段长度≥n时终止
}
//------------------------------------------------------------------------// 

//对R[0..n-1]进行基数排序，R[i]为非负整数，且位数不超过KeySize
template <class T>
void sort<T>::Radix(T R[])
{
	LinkQueue B[RadixNum];  //10个箱子，每个都是一个链队列
	int i;

	for (i=0; i<RadixNum; i++)  //初始化，箱子置空
		InitQueue(&B[i]);    
	
	for (i=KeySize-1; i>=0; i--)  //从低位到高位做d趟箱排序
	{
		Distribute(R, B, i);  //第KeySize-i趟分配
		Collect(R, B);  //第KeySize-i趟收集
	}
}

//按关键字的第j个分量进行分配，进入此过程时各箱子一定为空
template <class T>
void sort<T>::Distribute(T R[], LinkQueue B[], int j)
{
	int i, k, t;

	j = KeySize - j;    //确定关键字从个位起是第几个
	for (i=1; i<=size; i++) //依次扫描R[i]，将其装箱
	{
		k = R[i];
		for (t=1; t<j; t++) 
			k = k/10;
		k = k%10;  //取关键的第j位（从低位开始）数字k
		EnQueue(&B[k], R[i]); //将R[i]装放箱子B[k]
	}
}

//依次将各非空看箱子中的记录连接起来，本过程结束时各箱子均变空
template <class T>
void sort<T>::Collect(T R[], LinkQueue B[])
{
	int i=1, j;
	for (j=0; j<RadixNum; j++)   //注意：各箱子中记录数之和必为n
		while (!QueueEmpty(&B[j]))
			R[i++] = DeQueue(&B[j]);  //将出队记录依次输出到R[i]中
}
//------------------------------------------------------------------------//