lab2.cpp

两种方法（分治法、自底向上非递归算法）实现数组排序的C++实现

//底向上非递归
#include <iostream>
using namespace std;
void Merge(int c[],int c1[],int l,int m,int r)
{
  int i,j,k;
  i=l;
  j=m+1;
  k=l;
  while((i<=m) && (j<=r))
  {
   if(c[i]<=c[j])
    c1[k++]=c[i++];
   else
    c1[k++]=c[j++];
  }

 if(i>m)
 {
   for(int q=j;q<=r;q++)
    c1[k++]=c[q];
 }
 else
 {
  for(int q=i;q<=m;q++)
    c1[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=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]; 
	   
}
void MergeSort(int a[],int n)
{
  int*  b=new int[n];
  int s=1;
  while(s<n)
  {
    MergePass(a,b,s,n);
    s+=s;
    MergePass(b,a,s,n);
    s+=s;
  }  
}
void main()
{
  int a[]={11,53,74,62,76,50,16,49};
  MergeSort(a,8);
  int i=0;
  while(i<8)
  {
    cout<<a[i++]<<" ";
  }
}