归并

/*
 归并排序的思想：
 假设初始序列含有n个记录，则可以看成是n个
 有序的子序列，每个子序列的长度为1，然后两两
 归并，得到n/2个长度为1或者2的有序子序列
 在两两归并，如此重复，直到一个长度为n的有序
 序列为止
 */
#include<cstdio>
#define MAX 1000

typedef struct seeqlist
{
	int Array[MAX];
	int length;
}SeqList;

void Merge(int S[],int T[],int i,int m,int n)
{
	int j,k;
	for(j=m+1,k=i;i<=m&&j<=n;k++)
	{
		if(S[i]<S[j])
			T[k]=S[i++];
		else
			T[k]=S[j++];
	}
	if(i<=m)//将剩余的S[i..m]合并到T中
	{
		for(;i<=m;i++)
			T[k++]=S[i];
	}
	if(j<=n)//将剩余的S[j..n]合并到T中
	{
		for(;j<=n;j++)
			T[k++]=S[j];
	}
}

void Msort(int S[],int T[],int s,int t)
{
	int T2[MAX];
	int m;
	if(s==t)
		T[s]=S[s];
	else
	{
		m=(s+t)/2;//将S[s..t]平分成S[s..m]和S[m+1..t]
		Msort(S,T2,s,m);//递归将S[s..m]归并为T2[s..m]
		Msort(S,T2,m+1,t);///递归将S[m+1..t]归并为T2[m+1..t]
		Merge(T2,T,s,m,t);//合并
	}
}

void MergeSort(SeqList *L)//只是为了保持传参的一致性
{
	Msort(L->Array,L->Array,1,L->length);
}

int main(int argc,char *argv[])
{
	int i;
	SeqList L;
	scanf("%d",&L.length);
	for(i=1;i<=L.length;i++)
		scanf("%d",&L.Array[i]);
	MergeSort(&L);
	printf("After Sort:\n");
	for(i=1;i<=L.length;i++)
		printf("%4d",L.Array[i]);
	printf("\n");

	return 0;
}

排序递归算法

归并排序递归算法