mergesort.cpp

合并排序算法是用分治策略实现对n个元素进行排序的算法。其基本思想是：将待排序的元素分成大小大致相同的2个子集合

#include"iostream.h"

static unsigned int RAND_SEED=1;
unsigned int random(void)//产生随机数
{
    RAND_SEED=(RAND_SEED*123+59)%65536;
    return(RAND_SEED);
}
void random_start(int xxx)//初始种子
{
	RAND_SEED=xxx;
}

int *onerange(int   n)   //产生随机序列
{   
	int i;
	int   *d   =   new   int[n];  
	int  *range=new int[n];
	int seed=0;
	unsigned   int   a;   
	for   (i=0;   i<n;   i++)   
	{   
		*(d+i)   =   i+1;   
	}   
	for   (i=0;   i<n;)   
	{  
		random_start(seed);
		a=random(); 
		seed=a;
		a   %=   n;   
		if   (*(d+a)!=-1)   
		{
			range[i]=*(d+a);//cout<<*(d+a)<<"\t";   
			*(d+a)   =   -1;   
			i++;   
		}   
	} 
	delete d;
	return range;
}


void merge(int c[], int d[], int l, int m, int r){
	//合并c[l:m]和c[m+1:r]到d[l:r]
	int i = l;
	int j = m+1;
	int 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(; j <= r;)
			d[k++] = c[j++];
	}
	else{
		for(; i <= m;)
			d[k++] = c[i++];
	}
}

void mergeSort(int a[], int n, int left, int right){
	if(left<right){
		int i = (left + right)/2;
		mergeSort(a, n, left, i);
		mergeSort(a, n, i+1, right);
		int *b=new int[n];
		merge(a, b, left, i, right);
		int j;
		for(j = left; j <= right; j++){
			a[j] = b[j];
		}
		delete []b;
	}
}
void main()
{
	int n=50;
	int *p=onerange(n);
	mergeSort(p,n,0,n-1);
	for(int i=0;i<n;i++)
		cout<<p[i]<<endl;
}