必须要熟练掌握的归并排序

并排序时间复杂度分析

我们一趟归并，需要将两个小集合的长度放到大集合中，则需要将待排序序列中的所有记录扫描一遍所以时间复杂度为O(n)。

归并排序把集合一层一层的折半分组，则由完全二叉树的深度可知，整个排序过程需要进行 logn(向上取整)次,则总的时间复杂度为 O(nlogn)。

另外归并排序的执行效率与要排序的原始数组的有序程度无关，所以在最好，最坏，平均情况下时间复杂度均为 O(nlogn) 。

虽然归并排序时间复杂度很稳定，但是他的应用范围却不如快速排序广泛，这是因为归并排序不是原地排序算法，空间复杂度不为 O(1)，那么他的空间复杂度为多少呢?

归并排序的空间复杂度分析

归并排序所创建的临时结合都会在方法结束时释放，单次归并排序的最大空间是 n ,所以归并排序的空间复杂度为 O(n).

归并排序的稳定性分析

归并排序的稳定性，要看我们的 merge 函数，我们代码中设置了 arr[temp1] <= arr[temp2] ，当两个元素相同时，先放入arr[temp1] 的值到大集合中，所以两个相同元素的相对位置没有发生改变，所以归并排序是稳定的排序算法。如此时小集合大小为 1 。两个小集合分别为 [3],[1]。

然后我们根据合并规则，见第一个视频，将[3],[1]合并到临时数组中，则小的先进，进而实现了排序，然后再将临时数组的元素复制到原来数组中。则实现了一次合并。

下面则继续合并[4],[6]。具体步骤一致。所有的小集合合并完成后，则小集合的大小变为 2，继续执行刚才步骤，见下图。

（编辑：牡丹江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!