http://blog.csdn.net/touch_2011/article/details/6785881

1、序言

这是《漫谈经典排序算法系列》第四篇，解析了归并排序。 

各种排序算法的解析请参考如下：

《漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析》

《漫谈经典排序算法:二、各种插入排序解析及性能比较》

《漫谈经典排序算法:三、冒泡排序 && 快速排序》

《漫谈经典排序算法:四、归并排序》

《漫谈经典排序算法:五、线性时间排序(计数、基数、桶排序)》

《漫谈经典排序算法:六、各种排序算法总结》

注：为了叙述方便，本文以及源代码中均不考虑A[0],默认下标从1开始。

2、归并排序

          2.1 引出

           归并排序又是另一类排序算法，它是一种基于“分治”策略的一种算法。归并排序算法是典型的分治算法，对于规模较大的问题，可以分解成若干容易求解的简单的问题，最后把解合并构成初始问题的解。详细的排序过程可以参考《数据结构》或者《算法导论》。

          2.2 代码

[cpp]  view plain  copy
  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. #define INFINITE 1000  
  4.   
  5. //对两个序列进行合并,数组从mid分开  
  6. //对a[start...mid]和a[start+1...end]进行合并  
  7. void merge(int *a,int start,int mid,int end)  
  8. {  
  9.     int i,j,k;  
  10.     //申请辅助数组  
  11.     int *array1=(int *)malloc(sizeof(int)*(mid-start+2));  
  12.     int *array2=(int *)malloc(sizeof(int)*(end-mid+1));  
  13.   
  14.     //把a从mid分开分别赋值给数组  
  15.     for(i=0;i<mid-start+1;i++)  
  16.         *(array1+i)=a[start+i];  
  17.     *(array1+i)=INFINITE;//作为哨兵  
  18.     for(i=0;i<end-mid;i++)  
  19.         *(array2+i)=a[i+mid+1];  
  20.     *(array2+i)=INFINITE;  
  21.     //有序的归并到数组a中  
  22.     i=j=0;  
  23.     for(k=start;k<=end;k++){  
  24.         if(*(array1+i) > *(array2+j)){  
  25.             a[k]=*(array2+j);  
  26.             j++;  
  27.         }  
  28.         else{  
  29.             a[k]=*(array1+i);  
  30.             i++;  
  31.         }  
  32.     }  
  33.     free(array1);  
  34.     free(array2);  
  35. }  
  36.   
  37. //归并排序  
  38. void mergeSort(int *a,int start,int end)  
  39. {  
  40.     int mid=(start+end)/2;  
  41.     if(start<end){  
  42.         //分解  
  43.         mergeSort(a,start,mid);  
  44.         mergeSort(a,mid+1,end);  
  45.         //合并  
  46.         merge(a,start,mid,end);  
  47.     }  
  48. }  
  49.   
  50. void main()  
  51. {  
  52.     int i;  
  53.     int a[7]={0,3,5,8,9,1,2};//不考虑a[0]  
  54.     mergeSort(a,1,6);  
  55.     for(i=1;i<=6;i++)  
  56.         printf("%-4d",a[i]);  
  57.     printf("\n");  
  58. }  


 

          2.3 效率分析

可以说合并排序是比较复杂的排序，特别是对于不了解分治法基本思想的同学来说可能难以理解。总时间=分解时间+解决问题时间+合并时间。分解时间就是把一个待排序序列分解成两序列，时间为一常数，时间复杂度o(1).解决问题时间是两个递归式，把一个规模为n的问题分成两个规模分别为n/2的子问题，时间为2T(n/2).合并时间复杂度为o（n）。总时间T(n)=2T(n/2)+o(n).这个递归式可以用递归树来解，其解是o(nlogn).此外在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn).从合并过程中可以看出合并排序稳定。 

用递归树的方法解递归式T(n)=2T(n/2)+o(n):假设解决最后的子问题用时为常数c，则对于n个待排序记录来说整个问题的规模为cn。

 

从这个递归树可以看出，第一层时间代价为cn，第二层时间代价为cn/2+cn/2=cn.....每一层代价都是cn，总共有logn+1层。所以总的时间代价为cn*(logn+1).时间复杂度是o(nlogn).

 

3、附录

      参考书籍:  《算法导论》