归并排序
时间：2010-07-05 来源：星巴
归并排序（mergesort）采用分治的思想，将输入数据对列分为若干段，递归地将这些段排好，然后再通过师并的操作把这几段拼起来，从而将整个对列排序。
典型的归并是2路归并排序，过程如下所示：
|
例如数组A有以下7个数据： 49 38 65 97 76 13 27 [49] [38] [65] [97] [76] [13] [27]//看成由长度为1的7个子序列组成 [38 49] [65 97] [13 76] [27] //看成由长度为1或2的4个子序列组成 [38 49 65 97] [13 27 76] //看成由长度为4或3的2个子序列组成 [13 27 38 49 65 76 97] |
归并算法的时间复杂度是o(nlogn)，但空间复杂度却是o(n)，为了解决归并算法空间复杂度的问题，很多研究者都做了相关的研究，最早在1969年的时候，M. A. Kronrod就解决了这个问题，使其空间复杂度为o(1)，也就是说不占用了额外存储空间。
《数据结构》P213对此空间复杂度为0(1)的归并算法进行了较详细的介绍，过程比较复杂，需慢慢研究体会。
此文待继！！！
相关阅读 更多 +
