mergesort.cpp

这是一段关于四种排序方法的完全源代码及其相互之间的比较,包括:Heap sort,Merge sort,Quick sort,Radix sort

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

void merge(int A[],int p,int q,int r);
void mergesort(int A[],int low,int high);
int B[100000];
void main()
{
	int n;
	srand(time(0));
	cout<<"请输入n:";
	cin>>n;
	int *a;
	a=new int[n+1];
	for(int i=1;i<=n;i++)\
	{
		a[i]=rand();
	}
	cout<<"生成随机数组为:"<<'\n';
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<'\t';
	}
	cout<<endl;
	mergesort(a,1,n);
	cout<<"快速排序后数组为:"<<'\n';
	for(i=1;i<=n;i++)
	{
		cout<<a[i]<<'\t';
	}
	cout<<endl;
	delete a;
}

void mergesort(int A[],int low,int high)
{
	int mid;
	if(low<high)
	{
		mid=(low+high)/2;
		mergesort(A,low,mid);
		mergesort(A,mid+1,high);
		merge(A,low,mid,high);
	}
}

void merge(int A[],int p,int q,int r)
{
	int i;
	int s=p,t=q+1,k=p;
	while(s<=q&&t<=r)
	{
		if(A[s]<=A[t])
		{
			B[k++]=A[s++];
		}
		else
		{
			B[k++]=A[t++];
		}
	}
	if(s==q+1)
	{
		for(i=t;i<=r;i++)
		{
			B[k++]=A[i];
		}
	}
	else
	{
		for(i=s;i<=r;i++)
		{
			B[k++]=A[i];
		}
	}
	for(i=p;i<=r;i++)
	{
		A[i]=B[i];
	}
}