学步园

#include<iostream>
using namespace std;
void merge(int a[],int left,int mid,int right)
{
   int temp[right-left+1];//注意数组的定义
   int left1=left;
   int right1=mid;
   int left2=mid+1;
   int right2=right;
   int i=0;
   for(;(left1<=right1)&&(left2<=right2);++i)
   {
	   if(a[left1]<a[left2])
	   {
		   temp[i]=a[left1];
		   left1++;
	   }
	   else
	   {
		   temp[i]=a[left2];
		   left2++;
	   }
   }
   while(left1<=right1)
   {
	   temp[i++]=a[left1++];
   }
   while(left2<=right2)
   {
	   temp[i++]=a[left2++];
    }
	for(i=0;i<right-left;++i)
		a[i+left]=temp[i];
}
void sort(int a[],int left,int right)
{
	if(left<right)
	{
	  int mid=left+(right-left)/2;	
	  sort(a,left,mid);
	  sort(a,mid+1,right);
	  merge(a,left,mid,right);
	}
}
int main()
{
	int a[]={2,3,5,47,9,45,123};
	int j;
	sort(a,0,6);
        for(j=0;j<7;++j)
	cout<<a[j]<<endl;
	return 0;
}

在VS2008下，在merge()函数中temp[right-left+1]定义数组编译不通过，在G++下编译能通过

将数组的定义为以下形式：

   int *temp;
   temp=(int *)malloc(sizeof(int)*(right-left+1));

可以在VS2008中顺利编译成功和正确输出结果。
归并算法的时间复杂度为nlog(n),理解为要递归log(n)次，每一次合并的算法负责度为0(n).空间复杂度为0(n).

还有一种算法空间复杂度为0(1),时间复杂度为0(n^2).过程类似于插入排序

void merge2(int a[],int left,int mid,int right)
{
   int i,j,k,temp;
   for(i=left,j=mid+1;j<=right;++i)
      {
         if(a[i]>a[j])
           {
                  temp=a[j];
                  for(k=j;k>i;--k)a[k]=a[k-1];
                  a[k]=temp;
                  j++;
            }
           
      }
}