lab22.cpp

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

//分治法
#include <iostream>
using namespace std;  
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
	{
       for(int q=i;q<=m;q++)
           d[k++]=c[q];
	}
}
void Copy(int x1[],int x2[],int left1,int right1)
{
    for(int i1=left1;i1<=right1;i1++)
    {
        x2[i1]=x1[i1];
    }
}
 void MergeSort(int a[],int left,int right)
{
	 int b[8];
     if(left<right)
	 {
       int i=(left+right)/2;
       MergeSort(a,left,i);
       MergeSort(a,i+1,right);
       Merge(a,b,left,i,right);
       Copy(b,a,left,right);
	 }
}
void main()
{
    int a[]={2,1,15,53,6,67,58,49};
    MergeSort(a,0,7);
    for(int i=0;i<8;i++)
        cout<<a[i]<<"  ";
}