合并排序

简单介绍

合并排序使用分治策略来实现对n个算法的排序问题。

基本思想是：将待排序元素分成大小相同的两个子集合，分别对两个子集合进行论排序，最终将排好序的子集合并成排好序的集合。

该算法的时间复杂度是O(nlogn)，由于排列问题的计算时间下界为nlogn，故合并排序是一个渐进最优算法。

实现思路

有两种实现方式：递归形式，非递归形式。

递归形式

void Merge(int *c, int *d, int l, int m, int r){
	int i=l, j=m+1, k=l;
	while((i<=m) && (j<=r)){
		if(c[i] <= c[j])
			d[k++] = c[i++];
		else d[k++] = c[j++];
		if(i>m)
			for(int q=j; q<=r; q++)
				d[k++] = c[q];
		else if(j>r)
			for(int q=i; q<=m; q++)
				d[k++] = c[q];
	}
}
int num[maxn], b[maxn];
void MergeSort(int *a, int left, int right){
    if(left < right){
        int i = (left+right)/2;
        MergeSort(a, left, i);
        MergeSort(a, i+1, right);
        Merge(a, b, left, i, right);
        for(int i=left, i<=right, i++)
            a[i] = b[i];
    }
}

非递归形式

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<sstream>
typedef long long ll;
using namespace std;
const double eps=1e-6;
const int inf=0x3f3f3f3f;
const int MAXN=1E6+7;
int num[MAXN], num1[MAXN];
void Merge(int *c, int *d, int l, int m, int r){
	int i=l, j=m+1, k=l;
	while((i<=m) && (j<=r)){
		if(c[i] <= c[j])
			d[k++] = c[i++];
		else d[k++] = c[j++];
		if(i>m)
			for(int q=j; q<=r; q++)
				d[k++] = c[q];
		else if(j>r)
			for(int q=i; q<=m; q++)
				d[k++] = c[q];
	}
}
void MergePass(int *x, int *y, int s, int n){
	int i = 0;
	while(i <= n-2*s){
		Merge(x, y, i, i+s-1, i+2*s-1);
		i += 2*s;
	}
	if(i+s < n)
		Merge(x, y, i, i+s-1, n-1);
	else 
		for(int j=i; j<=n-1; j++)
			y[j] = x[j];
}
int MergeSort(int *a, int n){
	int s = 1;
	while(s < n){
		MergePass(a, num1, s, n);
		s+=s;
		MergePass(num1, a, s, n);
		s+=s;
	}
} 
int main()
{
	int n;
	while(cin>>n){
		for(int i=0; i<n; i++)
			cin>>num[i];
		MergeSort(num, n);
		for(int i=0; i<n; i++)
			cout<<num[i]<<" ";
		cout<<endl;
	}
	return 0;
}

参考资料

《计算机算法设计与分析》