Chinaunix首页 | 论坛 | 博客
  • 博客访问: 189084
  • 博文数量: 49
  • 博客积分: 635
  • 博客等级: 中士
  • 技术积分: 410
  • 用 户 组: 普通用户
  • 注册时间: 2011-08-25 12:58
文章分类

全部博文(49)

文章存档

2012年(9)

2011年(40)

分类:

2011-08-26 12:40:13

原文地址:归并排序mergesort的C实现 作者:Bean_lee

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

     而且归并排序有一个好的特性,无论何等输入,对N个元素排序所需的时间与NlogN成正比。这种特性的达成是因为它把任务平均分成了互不干扰的2份,交给两个下属分别去做,然后将两个下属的成果整合(merge)。这种平均分2份,造就了归并的优越性。
 
     
              注图片来源:爪哇人的技术博客(如有侵权,通知我删除图片)
     我们考虑下前面提到的快速排序,快速排序也是递归实现,也是把一个任务分成了两份,但是有个问题,可能两份不一样多。我们回想下,前文快速排序quicksort的C实现中提到,每次把最右边的元素作为主元或者是衡量的坐标,把比主元大的放到主元的右边,比主元小的放在主元的左边,有一种极端的情况是,主元是最大的元素,或者主元是最小的元素,那么,我们的分治并没有起到效果,,因为左右两边很不均衡。所以说极端情况下,快速排序并不快速,和输入有一定关系。当然也有解决的办法,比如随机选择一个元素作为主元。即随机快速排序算法。

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

     首先array[l]~array[mid] 是一个下属提上来的已序的数组, array[mid+1]~array[r],是另外一个下属提上来的已序的数组。我们需要一个辅助数组来实现归并。         
  1. void merge(int array[],int l,int mid,int r,int aux[])
  2. {
  3.                 int i,j,k;
  4.                 for(i = l;i<=mid;i++)
  5.                                 aux[i] = array[i];

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

  8.                 i = l;j =r;

  9.                 for(k = l;k<=r;k++)
  10.                 {
  11.                                 if(aux[j] <aux[i])
  12.                                 {
  13.                                                 array[k] = aux[j--];
  14.                                 }
  15.                                 else
  16.                                 {
  17.                                                 array[k] = aux[i++];
  18.                                 }
  19.                 }

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

    好,闲言少叙,上代码:
    1. #include
    2. #include
    3. #include

    4. void merge(int array[],int l,int mid,int r,int aux[])
    5. {
    6. int i,j,k;
    7. for(i = l;i<=mid;i++)
    8.    aux[i] = array[i];

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

    11. i = l;j =r;
    12. for(k = l;k<=r;k++)
    13. {
    14.     if(aux[j]
    15.     {
    16. array[k] = aux[j--];
    17.     }
    18.     else
    19.     {
    20. array[k] = aux[i++];
    21.     }
    22. }

    23. }

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

    33. int  mergesort(int array[],int l,int r)
    34. {
    35.    if(r
    36.    {
    37.       return -1;
    38.    }
    39.    if(r == l)
    40.    {
    41.       return 0;
    42.    }
    43.    
    44.    int len = r - l + 1;
    45.    int *aux = malloc(sizeof(int)*len); /*需要额外的空间,这是mergesort的缺点*/
    46.    if(aux == NULL)
    47.    {
    48.       return -2;
    49.    }
    50.    mergesort_r(array,l,r,aux);
    51.    free(aux);
    52.    return 0;
    53. }

    54. int test_mergesort()
    55. {
    56. int i;
    57. int number = 12;

    58. int *array = malloc(number*sizeof(int));
    59. if(array == NULL )
    60. {
    61. printf("malloc failed\n");
    62. return -1;
    63. }


    64. printf("----------------------------------------before merge sort--------------\n");
    65. srand(time(NULL));
    66. for(i = 0;i
    67. {
    68.         array[i] = rand()%1000;
    69. printf("\tarray[%6d] = %6d\n",i,array[i]);
    70. }

    71.         if(mergesort(array,0,number-1))
    72.         {
    73.              printf("mergesort failed \n");
    74.              return -2;
    75.         }

    76. printf("----------------------------------------after merge sort-----------------\n");
    77. for(i = 0;i
    78. {
    79. printf("\tarray[%6d] = %6d\n",i,array[i]);
    80. }
             free(array);
    1. return 0;

    2. }
    3. int main()
    4. {
    5. test_mergesort();
    6. return  0;
    7. }
    1. ----------------------------------------before merge sort--------------
    2. array[ 0] = 592
    3. array[ 1] = 485
    4. array[ 2] = 750
    5. array[ 3] = 325
    6. array[ 4] = 477
    7. array[ 5] = 838
    8. array[ 6] = 184
    9. array[ 7] = 723
    10. array[ 8] = 229
    11. array[ 9] = 314
    12. array[ 10] = 52
    13. array[ 11] = 42
    14. ----------------------------------------after merge sort-----------------
    15. array[ 0] = 42
    16. array[ 1] = 52
    17. array[ 2] = 184
    18. array[ 3] = 229
    19. array[ 4] = 314
    20. array[ 5] = 325
    21. array[ 6] = 477
    22. array[ 7] = 485
    23. array[ 8] = 592
    24. array[ 9] = 723
    25. array[ 10] = 750
    26. array[ 11] = 838
       下面提一下归并排序的另外一个缺点,函数调用太多了,看下mergesort_r中的这条语句
  1.           if(r<=l)
  2.     return ;

       mergesort太懒了,啥活也不干,来了活就分解给自己的下属。对于长度少于10的数组排序,完全可以直接排序了,不要在找下属。我们可以想见,按照上面的代码,如果有100万个元素需要排序,那么最底层的就有100万个函数,return上报给自己的直接上级,这种情况对于我这种对递归嵌套深度有恐惧的人来说太可怕了。     
      一种优化的方法是
      if(r-l <= 10)
      {
          insertsort(a,l,r);
          return;
      }
     

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

    数组个数为2^N的理想情况下,减少一层调用,函数掉用就降为原来的1/2,
对于10以下的数组直接排序,相当于减少了长度为8 4 2 这三层函数的调用,至少降为原来的1/8。函数调用从100万降到了12万左右。
阅读(905) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~