算法模版-归并排序

发布于 2019-11-02  40 次阅读


归并排序(Merge-Sort)

这真的是一个简单的算法

如果既想要编程时间快又想要运行速度快,在不能用 std::sort 的前提下除了归并排序貌似就没有其他选择了(手动滑稽

归并排序的核心算法是如何将两个已经排好序的数组合并成一个数组。在代码中这两个数组分别是 [first, fe) 和 [fe, last)。循环开始前 first 是指向第一个有序数组的第一个元素的指针,mid 是指向第二个数组的第一个元素的指针。在循环中比较 *first 和 *mid 的值,将较大的元素放入辅助空间里并将该指针指向下一个元素。循环在两个数组中至少有一个处理完毕时终止。此时剩下的部分肯定比已经处理完的元素还要大,于是直接将这些元素复制到辅助数组尾部。此时,辅助数组已经是我们所需的排好序的数组,将其复制到原先 first 的位置即可。

 

 

时间复杂度:O(n log n),参考《算法导论》中主定理,T(n) = 2T(n/2) + O(n)。

空间复杂度:O(n),需要一个和原数组等长的辅助空间。


Σσ(・Д・;)我我我什么都没做!!!