mergesort.cpp

数据结构c++-书的一些源代码

#include <iostream.h>
#include "datatype.h"

void Merge(datatype a[], int n, datatype swap[], int k)
//对有序表a[0]--a[n-1]进行一次二路归并排序，每个有序子表的长度为k
//一次二路归并排序后新的有序子表存于swap中
{
	int m = 0, u1,l2,i,j,u2;

	int l1 = 0;										//给出第一个有序子表下界	
	while(l1+k <= n-1)
	{
		l2 = l1 + k;								//计算第二个有序子表下界
		u1 = l2 - 1;								//计算第一个有序子表上界
		u2 = (l2+k-1 <= n-1)? l2+k-1: n-1;			//计算第二个有序子表上界

		//两个有序子表合并
		for(i = l1, j = l2; i <= u1 && j <= u2; m++)	
		{
			if(a[i].key <= a[j].key)
			{
				swap[m] = a[i];
				i++;
			}
			else
			{
				swap[m]=a[j];
				j++;
			}
		}

		//子表2已归并完，将子表1中剩余的对象顺序存放到数组swap中
		while(i <= u1)
		{
			swap[m] = a[i];
			m++;
			i++;
		}

		//子表1已归并完，将子表2中剩余的对象顺序存放到数组swap中
		while(j <= u2)
		{
			swap[m] = a[j];
			m++;
			j++;
		}

		l1 = u2 + 1;
	}

	//将原始数组中不足二组的对象顺序存放到数组swap中
	for(i = l1; i < n; i++, m++) swap[m] = a[i];
}

void MergeSort(datatype a[], int n)
//用二路归并排序法对对象数组a[0]--a[n-1]排序，swap用于临时存放对象
{
	int i, k = 1;								//归并长度由1开始
	datatype *swap = new datatype[n];			//动态数组申请

	while(k < n)
	{
		Merge(a, n, swap, k);
      
		//将记录从数组swap放回a中
		for(i = 0; i < n; i++) a[i] = swap[i];

		//归并长度加倍
		k = 2 * k;
	}
	delete []swap;
}

void main(void)
{
	datatype test[]={60,55,48,37,10,90,84,36};
	int n = 8;
	
	MergeSort(test, n);
	for(int i = 0; i < n; i++)
		cout << test[i].key << "  ";
}