Merge_sort

09-排序1 排序（25 分）

给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。

本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：只有1个元素；

数据2：11个不相同的整数，测试基本正确性；

数据3：103个随机整数；

数据4：104个随机整数；

数据5：105个随机整数；

数据6：105个顺序整数；

数据7：105个逆序整数；

数据8：105个基本有序的整数；

数据9：105个随机正整数，每个数字不超过1000。

输入格式:

输入第一行给出正整数N（≤10​5​​），随后一行给出N个（长整型范围内的）整数，其间以空格分隔。

输出格式:

在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。

输入样例:

11
4 981 10 -17 0 -20 29 50 8 43 -5

输出样例:

-20 -17 -5 0 4 8 10 29 43 50 981

1.递归方法的归并排序；

#include<iostream>

using namespace std;
int size,flag=0;
void Merge(long int data[],int l,int r,int rend,int temp[]){
int n=rend-l+1;
int lend=r-1;
int s=l;
while(l<=lend&&r<=rend){
if(data[l]<data[r]) temp[s++]=data[l++];
else temp[s++]=data[r++];
}
while(l<=lend)
temp[s++]=data[l++];
while(r<=rend)
temp[s++]=data[r++];
for(int i=0;i<n;i++)
data[rend]=temp[rend--]; 
}
void Msort(long int data[],int l,int rend,int temp[]){
int center;
if(l<rend){
center=(l+rend)/2;
Msort(data,l,center,temp);
Msort(data,center+1,rend,temp);
Merge(data,l,center+1,rend,temp);
}
} 
void Merge_sort(long int data[],int N){
int *temp;
temp=(int*)malloc(N*sizeof(int));
if(temp!=NULL){
Msort(data,0,N-1,temp);
free(temp);
}
else
cout<<"these is no enough space"<<endl;
}
int main()
{
  int N=0;
  cin>>N;
  size=N;
  long int data[N];
  for(int i=0;i<N;i++)
  cin>>data[i];
  Merge_sort(data,N);
  for(int i=0;i<N;i++)
  if(flag++==0)
  cout<<data[i];
  else
  cout<<" "<<data[i];
  return 0;

} 

测试结果

2.非递归方法的归并排序

#include<iostream>
#include<memory>
using namespace std;
int size,flag=0;
void Merge1(long int data[],int l,int r,int rend,long int temp[]){
int n=rend-l+1;
int lend=r-1;
int s=l;
while(l<=lend&&r<=rend){
if(data[l]<data[r]) temp[s++]=data[l++];
else temp[s++]=data[r++];
}
while(l<=lend)
temp[s++]=data[l++];
while(r<=rend)
temp[s++]=data[r++];
//for(int i=0;i<n;i++)
//data[rend]=temp[rend--]; 
}
void Merge_pass(long int data[],int N,long int temp[],int length){
int i;
for(i=0;i<N-1-2*length;i+=length*2)
Merge1(data,i,i+length,i+2*length-1,temp);
if(i+length<N)
Merge1(data,i,i+length,N-1,temp);
else
for(int j=i;j<N;j++) temp[j]=data[j];
 
}
void Merge_sort2(long int data[],int N){
long int *temp; int length=1;
temp=(long int*)malloc(N*sizeof(long int));
if(temp!=NULL){
while(length<N){
Merge_pass(data,N,temp,length);
length*=2;
Merge_pass(temp,N,data,length);
length*=2;
}
free(temp);
}
else
cout<<"there is no enough space"<<endl;
}
int main()
{
  int N=0;
  cin>>N;
  size=N;
  long int data[N];
  for(int i=0;i<N;i++)
  cin>>data[i];
  Merge_sort2(data,N);
  for(int i=0;i<N;i++)
  if(flag++==0)
  cout<<data[i];
  else
  cout<<" "<<data[i];
  return 0;
} 

测试结果