归并排序mergesort的C实现

  所有的排序算法中，我比较喜欢归并排序的思想，它采用了一种分解--整合---上报的思想。它把一个任务平均分成了2份，交给两个下属去做，然后将下属上报上来的结果，整合完整，整合完整后，在上报给自己的上级。这种思想很优美。

     而且归并排序有一个好的特性，无论何等输入，对N个元素排序所需的时间与NlogN成正比。这种特性的达成是因为它把任务平均分成了互不干扰的2份，交给两个下属分别去做，然后将两个下属的成果整合（merge）。这种平均分2份，造就了归并的优越性。

 

     

              注图片来源：爪哇人的技术博客（如有侵权，通知我删除图片）

     我们考虑下前面提到的快速排序，快速排序也是递归实现，也是把一个任务分成了两份，但是有个问题，可能两份不一样多。我们回想下，前文快速排序quicksort的C实现中提到，每次把最右边的元素作为主元或者是衡量的坐标，把比主元大的放到主元的右边，比主元小的放在主元的左边，有一种极端的情况是，主元是最大的元素，或者主元是最小的元素，那么，我们的分治并没有起到效果，，因为左右两边很不均衡。所以说极端情况下，快速排序并不快速，和输入有一定关系。当然也有解决的办法，比如随机选择一个元素作为主元。即随机快速排序算法。

     OK，再次回到的我们的归并排序。所谓归并排序，关键在归并，即前面提到的整合。两个下属已经上报了2个排好顺序的数组上报上来了，接下来就是要归并。归并的含义是，把两个已序的数组合并成一个已序的大数组。

     首先array[l]~array[mid] 是一个下属提上来的已序的数组， array[mid+1]~array[r],是另外一个下属提上来的已序的数组。我们需要一个辅助的数组来实现归并。         

void merge(int array[],int l,int mid,int r,int aux[])
{
                int i,j,k;
                for(i = l;i<=mid;i++)
                                aux[i] = array[i];

                for(j = mid+1;j<=r;j++)
                                aux[j] = array[mid+1+r-j];

                i = l;j =r;

                for(k = l;k<=r;k++)
                {
                                if(aux[j] <aux[i])
                                {
                                                array[k] = aux[j--];
                                }
                                else
                                {
                                                array[k] = aux[i++];
                                }
                }

}

    OK，需要提一句归并排序的缺点了，归并排序的缺点就是他需要一个辅助数组。换句话说，他需要额外的空间。当然可以采用其他办法来克服这个缺点，但是代价有点大。

    好，闲言少叙，上代码：

#include
#include
#include

void merge(int array[],int 
l,int mid,int r,int aux[])
{
int i,j,k;
for(i = 
l;i<=mid;i++)
  
 aux[i] = array[i];

for(j 
= mid+1;j<=r;j++)
  
 aux[j] = array[mid+1+r-j];

i = l;j =r;
for(k = 
l;k<=r;k++)
{
  
  if(aux[j]
  
  {
array[k] 
= aux[j--];
  
  }
  
  else
  
  {
array[k] 
= aux[i++];
  
  }
}

}

void mergesort_r(int 
array[],int l,int r,int aux[])
{
int mid = (l+r)/2;
if(r<=l)
  
 return ;
mergesort_r(array,l,mid,aux);
mergesort_r(array,mid+1,r,aux);
merge(array,l,mid,r,aux);/*把两个下属完成的两个已序的小数组归并成一个大的已序数组*/
}

int  mergesort(int array[],int 
l,int r)
{
   if(r
   {
      return -1;
   }
   if(r == l)
   {
      return 0;
   }

   int len = r - l + 
1;
   int *aux = 
malloc(sizeof(int)*len); /*需要额外的空间，这是mergesort的缺点*/
   if(aux == NULL)
   {
      return -2;
   }
  
 mergesort_r(array,l,r,aux);
   free(aux);
   return 0;
}

int test_mergesort()
{
int 
i;
int 
number = 12;

int 
*array = malloc(number*sizeof(int));

if(array 
== NULL )
{
printf("malloc 
failed\n");
return -1;
}


printf("----------------------------------------before 
merge sort--------------\n");
srand(time(NULL));
for(i 
= 0;i
{
    
    array[i] = rand()%1000;
printf("\tarray[%6d] 
= %6d\n",i,array[i]);
}

        
if（mergesort(array,0,number-1)）
        {
             printf("mergesort 
failed \n");
             return 
-2;
        }

printf("----------------------------------------after 
merge sort-----------------\n");
for(i 
= 0;i
{
printf("\tarray[%6d] 
= %6d\n",i,array[i]);
}
        
 free(array);
return 
0;

}
int main()
{
test_mergesort();
return 
 0;
}
----------------------------------------before merge 
sort--------------
array[ 0] = 592
array[ 1] = 485
array[ 2] = 750
array[ 3] = 325
array[ 4] = 477
array[ 5] = 838
array[ 6] = 184
array[ 7] = 723
array[ 8] = 229
array[ 9] = 314
array[ 10] = 52
array[ 11] = 42
----------------------------------------after merge 
sort-----------------
array[ 0] = 42
array[ 1] = 52
array[ 2] = 184
array[ 3] = 229
array[ 4] = 314
array[ 5] = 325
array[ 6] = 477
array[ 7] = 485
array[ 8] = 592
array[ 9] = 723
array[ 10] = 750
array[ 11] = 
838

       下面提一下归并排序的另外一个缺点，函数调用太多了，看下mergesort_r中的这条语句

          if(r<=l)
  
  return ;

       mergesort太懒了，啥活也不干，来了活就分解给自己的下属。对于长度少于10的数组排序，完全可以直接排序了，不要在找下属。我们可以想见，按照上面的代码，如果有100万个元素需要排序，那么最底层的就有100万个函数，return上报给自己的直接上级，这种情况对于我这种对递归嵌套深度有恐惧的人来说太可怕了。     

      一种优化的方法是

      if（r-l <= 10）

      {

          insertsort(a,l,r);

          return;

      }

     

     insertsort的效率是不高，但是应付长度低于10的数组，足够了。而且减少了大量的函数调用，效率有提升。

    数组个数为2^N的理想情况下，减少一层调用，函数掉用就降为原来的1/3，

对于10以下的数组直接排序，相当于减少了长度为8 4 2 这三层函数的调用，至少降为原来的1/27。函数调用从100万降到了4万左右。