归并排序时间复杂度----主定理

忘是亡心i 2022-09-25 12:18 162阅读 0赞

http://blog.csdn.net/touch\_2011/article/details/6785881

## 1、序言 ##

> 这是《漫谈经典排序[算法][Link 1]系列》第四篇，解析了归并排序。
> 
> 各种排序算法的解析请参考如下：
> 
> [《漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析》][Link 2]
> 
> [《漫谈经典排序算法:二、各种插入排序解析及性能比较》][Link 3]
> 
> [《漫谈经典排序算法:三、冒泡排序 && 快速排序》][Link 4]
> 
> [《漫谈经典排序算法:四、归并排序》][Link 5]
> 
> [《漫谈经典排序算法:五、线性时间排序(计数、基数、桶排序)》][Link 6]
> 
> [《漫谈经典排序算法:六、各种排序算法总结》][Link 7]
> 
> 注：为了叙述方便，本文以及源代码中均不考虑A\[0\],默认下标从1开始。

## 2、归并排序 ##

###  2.1 引出 ###

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

###  2.2 代码 ###

> **\[cpp\]** [view plain][] [copy][view plain]
> 
> 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。
> 
> ![0_1316274273mgZp.gif][]
> 
> 从这个递归树可以看出，第一层时间代价为cn，第二层时间代价为cn/2+cn/2=cn.....每一层代价都是cn，总共有logn+1层。所以总的时间代价为cn\*(logn+1).时间复杂度是o(nlogn).

## 3、附录 ##

参考书籍: 《算法导论》

[Link 1]: http://lib.csdn.net/base/31
[Link 2]: http://blog.csdn.net/touch_2011/article/details/6767673
[Link 3]: http://blog.csdn.net/touch_2011/article/details/6783965
[Link 4]: http://blog.csdn.net/touch_2011/article/details/6784639
[Link 5]: http://blog.csdn.net/touch_2011/article/details/6785881
[Link 6]: http://blog.csdn.net/touch_2011/article/details/6787127
[Link 7]: http://blog.csdn.net/touch_2011/article/details/6787364
[view plain]: http://blog.csdn.net/touch_2011/article/details/6785881#
[0_1316274273mgZp.gif]: /images/20220717/01446662216b437a8866e95f764ce306.png