mergesort.h

有各种排序算法

#include"DataList.h"
template <class T>
void merge (dataList<T>& L1, dataList<T>& L2,const int left, const int mid, const int right) 
{
	//L1.Vector[left..mid]与L1.Vector[mid+1..right]是两
	//个有序表, 将这两个有序表归并成一个有序表
	//L2.Vector[left..right]
	int k, i, j; 
	i = left;  j = mid+1;  k = left;
	// i, j是检测指针, k是存放指针   
	while (i <= mid && j <= right)	   //两两比较
		if (L1[i] <= L1[j]) 
			L2[k++] = L1[i++];
		else 
			L2[k++] = L1[j++];
	while (i <= mid) L2[k++] = L1[i++];
	//若第一个表未检测完,复制
	while (j <= right) L2[k++] = L1[j++];
	//若第二个表未检测完,复制
}
template <class T>
void MergePass (dataList<T>& L1, dataList<T>& L2, const int len) 
{  //一趟归并排序的算法,结果在L2中
	int i = 0, j, n = L1.Length();
	while (i+2*len <= n-1)
	{
		merge (L1, L2, i, i+len-1, i+2*len-1);
		i += 2 * len;                //循环两两归并
	}
	if (i+len <= n-1)
		merge (L1, L2, i, i+len-1, n-1);
	//剩下一个长度为len的归并项和另一个长度不足len的归并项
	else for (j = i; j <= n-1; j++) L2[j] = L1[j];
	//只剩下一个归并项
};
template <class T> 
void MergeSort (dataList<T>& L) {
	//按元素排序码非递减的顺序对表L中元素排序
	int n = L.GetSize();
	dataList<T> tempList (n);		//创建临时表
	int len = 1;
	while (len < n) {
		MergePass (L, tempList, len);   len *= 2; 	
		MergePass (tempList, L, len);   len *= 2; 
	}   //主表、辅表（临时表）轮换归并
};