Chinaunix首页 | 论坛 | 博客

潜心修行bean.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

Bean_lee

  • 博客访问： 3844450
  • 博文数量： 146
  • 博客积分： 3918
  • 博客等级： 少校
  • 技术积分： 8584
  • 用 户 组： 普通用户
  • 注册时间： 2010-10-17 13:52
个人简介

个人微薄： weibo.com/manuscola

文章分类

全部博文（146）

文章存档

2016年（3）

2015年（2）

2014年（5）

2013年（42）

2012年（31）

2011年（58）

2010年（5）

我的朋友
最近访客
推荐博文
相关博文
归并排序mergesort的C实现

分类： C/C++

2011-08-21 08:23:19

    所有的排序算法中，我比较喜欢归并排序的思想，它采用了一种分解--整合---上报的思想。它把一个任务平均分成了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];

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

  10.                 i = l;j =r;

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

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

    好，闲言少叙，上代码：
    2. #include
    3. #include
    4. #include

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

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

    15. i = l;j =r;
    16. for(k = l;k<=r;k++)
    17. {
    18.     if(aux[j]
    19.     {
    20. array[k] = aux[j--];
    21.     }
    22.     else
    23.     {
    24. array[k] = aux[i++];
    25.     }
    26. }

    28. }

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

    40. int  mergesort(int array[],int l,int r)
    41. {
    42.    if(r
    43.    {
    44.       return -1;
    45.    }
    46.    if(r == l)
    47.    {
    48.       return 0;
    49.    }
    50.    
    51.    int len = r - l + 1;
    52.    int *aux = malloc(sizeof(int)*len); /*需要额外的空间，这是mergesort的缺点*/
    53.    if(aux == NULL)
    54.    {
    55.       return -2;
    56.    }
    57.    mergesort_r(array,l,r,aux);
    58.    free(aux);
    59.    return 0;
    60. }

    62. int test_mergesort()
    63. {
    64. int i;
    65. int number = 12;

    67. int *array = malloc(number*sizeof(int));
    69. if(array == NULL )
    70. {
    71. printf("malloc failed\n");
    72. return -1;
    73. }


    76. printf("----------------------------------------before merge sort--------------\n");
    77. srand(time(NULL));
    78. for(i = 0;i
    79. {
    80.         array[i] = rand()%1000;
    81. printf("\tarray[%6d] = %6d\n",i,array[i]);
    82. }

    84.         if（mergesort(array,0,number-1)）
    85.         {
    86.              printf("mergesort failed \n");
    87.              return -2;
    88.         }

    90. printf("----------------------------------------after merge sort-----------------\n");
    91. for(i = 0;i
    92. {
    93. printf("\tarray[%6d] = %6d\n",i,array[i]);
    94. }
             free(array);
    1. return 0;

    3. }
    4. int main()
    5. {
    6. test_mergesort();
    7. return  0;
    8. }
    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万左右。
阅读(11099) | 评论(0) | 转发(4) |
0

上一篇：希尔排序shellsort的C实现

下一篇：堆排序heapsort的C实现

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6