merge.cpp

来自「解决全排列的问题 可以包含特殊符号和一般的重复问题」· C++ 代码 · 共 54 行

//合并排序算法

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#define N 10

//将有序序列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 i,R[N],L[N];
	for(i=0; i<N; i++) R[i]=rand();
	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
	for(i=0; i<N; i++) cout<<R[i]<<'\t';
	cout<<endl;
}