Loading... 归并排序（mergesort），最早由冯·诺依曼于1945年在EDVAC上首次编程实现，它建立在归并操作上，是第一个在最坏情况下依然可以保持o(nlogn)运行时间的确定性算法。 归并排序的主要思想是分治。具体来说，就是将规模为n的问题，分解为两个规模为n/2的问题，再将这两个子问题分解为规模为n/4的4个子问题，以此类推，直至每个子问题规模为1。我们知道，单个元素是自然有序的，因此，这时我们就有了n个有序的向量。接下来，每两个相邻的有序向量来进行二路归并，直至全部排序完毕。 从上面对于原理的简单介绍可以看出，归并排序可以用递归的方式实现，下面就是一段用C++实现的，针对数组的核心代码。 ```cpp template <typename T> void mergeSort(T *_elem, int lo, int hi) { if (hi - lo < 2) return; //递归基 int mi = (lo + hi) >> 1; mergeSort(_elem, lo, mi); mergeSort(_elem, mi, hi); //左右两边分别排序 merge(_elem, lo, mi, hi); //二路归并 } ``` 归并排序的核心是归并操作，即merge()函数。归并操作，简单地说就是将两个有序向量连接为一个有序向量，其具体操作是每次比较两个子向量的首元素，将较小者从子向量中移出，存入输出向量的末尾，以此迭代，直至某个子向量为空，将另一个子向量剩余元素直接存入输出向量末尾。 下图是将向量（5,8,13,21）和（2,4,10,29）进行归并操作的例子（引用自《数据结构（C++语言版）》,邓俊辉）： ![][1] 基于上述思想，可以设计merge()函数如下： ```cpp template <typename T> void merge(T *_elem, int lo, int mi, int hi) { T* A = _elem + lo; //输出向量，无需申请临时空间 int lb = mi - lo; T* B = new T[lb]; //第一个子向量，申请临时空间 for (int i = 0; i < lb; B[i] = A[i++]); int lc = hi - mi; T* C = _elem + mi; //第二个子向量，无需申请临时空间 for (int i = 0, j = 0, k = 0; (j < lb) || (k < lc); ) //归并操作 { if ((j < lb) && (!(k < lc) || (B[j] <= C[k]))) A[i++] = B[j++]; if ((k < lc) && (!(j < lb) || (C[k] < B[j]))) A[i++] = C[k++]; } delete[] B; //释放临时空间B } ``` 值得注意的是，考虑到空间利用率，以及new操作比较耗时，这里仅对第一个子向量申请了临时空间，第二个子向量及输出向量均存储在原有的空间内。这样的话，两个子向量的地位并不平等，当第一个子向量的元素全部存入输出向量时，第二个子向量就无需移动了。为此，可以对上述逻辑进行简化： ```cpp template <typename T> void merge(T *_elem, int lo, int mi, int hi) { T* A = _elem + lo; //输出向量，无需申请临时空间 int lb = mi - lo; T* B = new T[lb]; //第一个子向量，申请临时空间 for (int i = 0; i < lb; B[i] = A[i++]); int lc = hi - mi; T* C = _elem + mi; //第二个子向量，无需申请临时空间 for (int i = 0, j = 0, k = 0; j < lb; ) //归并操作 { if (!(k < lc) || (B[j] <= C[k])) A[i++] = B[j++]; if ((k < lc) && (C[k] < B[j])) A[i++] = C[k++]; } delete[] B; //释放临时空间B } ``` 参考文献： [1] 邓俊辉. 数据结构(C++语言版)(第3版)(清华大学计算机系列教材)[M]. 清华大学出版社, 2013. [1]: http://www.lxalxy.com/medias/article_images/2016/08/10/02-18.png © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏
