合并排序算法.cpp

递归和分治法解一系列经典算法

//合并排序算法

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

//将有序序列SR[s..m]和SR[m+1..t]由小到大地合并为有序序列TR[s..t]
void Merge(int *SR, int *TR, int s, int m, int t)
{
	int i=s, j=m+1, k=s ,l;
	while(i<=m && j<=t)
	{
		if(SR[i]<=SR[j]) TR[k]=SR[i++];
		else TR[k]=SR[j++];
		++k;
	} //while
	for(l=i; l<=m; ++l) TR[k++]=SR[l];
	for(l=j; l<=t; ++l) TR[k++]=SR[l];
} //Merge

//将记录序列S[n]中的每个长度为l 的有序序列两两合并到R[n]中
void Merge2(int *S, int *R, int n, int l)
{
	int k=0; //每一对待合并序列的第1个元素下标
	while(k+2*l-1<n)
	{
		Merge(S, R, k, k+l-1, k+2*l-1);
		k+=2*l;
	} //while
	//归并最后两个长度不等的序列：
	if(k+l<=n) Merge(S, R, k, k+l-1, n-1);
	else  //将剩下的最后一个序列复制到R中
		for(int i=k; i<n; ++i) R[i]=S[i];
} //Merge2

void main()
{
	srand(time(0));
	int n,i,*R,*L;
	cout<<"请输入需要排序的整数的个数n：";
	cin>>n;
	R=new int[n];
	L=new int[n];
	cout<<"请输入"<<n<<"个待排序的整数：";
	for(i=0; i<n; i++) {
		cin>>R[i];
	}
	int l=1;  //有序子序列长度从1开始
	while(l<n)
	{
		//从R合并到L，得到有序序列长度为2*l
		Merge2(R, L, n, l);
		l*=2;
		//从L合并到R，得到有序序列长度为2*l
		Merge2(L, R, n, l);
		l*=2;
	} //while
	cout<<"排序后的整数序列是：";
	for(i=0; i<n; i++) cout<<R[i]<<' ';
	cout<<endl;
}