标签:合并排序

合并排序MergeSort

发表于3年前(Dec 24, 2014 9:57:55 AM)  阅读 713  评论 0

分类: Java 算法 排序

标签: sort 排序 mergesort 合并排序 递归

合并排序是分治法的典型应用,就是我们常说的递归。合并排序是将两个已经排好序的数组合并成一个有序数组的过程,所以只需保证子数组有序,那么合并出来的数组也是有序的,那剩下的问题就是如何递归地对子数组进行排序。

合并排序是不能在原数组上实现的,他的时间复杂度为O(nlog n)。在上面的代码中,核心算法是merge合并算法。在该算法的实现中,对要合并的目标数组进行了拷贝,然后替换源数组的值,这样的话可读性较好,但实际上也是一件影响效率的工作。参考网上其它的算法,一般是返回一个新的排序数组,各中优略请读者自己把握。