归并排序是创建在归并操作上的一种有效排序算法。所谓归并操作,指的是将两个已经排序的序列合并成一个序列的操作。归并排序是分治思想的典型示范。
归并排序具体步骤如下:
用golang实现如下:
// merge方法实现归并排序中的归并操作,将两个已排序数组归并操作成一个已排序数组
func (this *MergeSort) merge(a []Comparable, compare Compare, lo int, mid int, hi int) {
i := lo
j := mid + 1
arrayBak := make([]Comparable, len(a))
copy(arrayBak, a)
for k := lo; k <= hi; k++ {
if i > mid {
a[k] = arrayBak[j]
j++
} else if j > hi {
a[k] = arrayBak[i]
i++
} else if this.less(arrayBak[i], arrayBak[j], compare) {
a[k] = arrayBak[i]
i++
} else {
a[k] = arrayBak[j]
j++
}
}
}
// Sort1采用自顶向下方法进行归并排序
// Sort中参数类型Comparable为统一的可比较接口,若为整数数组排序,则Comparable为int即可
// Sort中参数类型Compare为配合Comparable接口的比较方法,若为整数数组排序,则Compare即满足a int < a int即可
func (this *MergeSort) sort1(a []Comparable, compare Compare, lo int, hi int) {
if lo >= hi {
return
}
mid := (lo + hi) / 2
this.sort1(a, compare, lo, mid)
this.sort1(a, compare, mid+1, hi)
this.merge(a, compare, lo, mid, hi)
}
// Sort2采用自底向上方法进行归并排序,先从子数组为1开始归并操作,逐渐递增,直到归并成完整数组为止
// Sort中参数类型Comparable为统一的可比较接口,若为整数数组排序,则Comparable为int即可
// Sort中参数类型Compare为配合Comparable接口的比较方法,若为整数数组排序,则Compare即满足a int < a int即可
func (this *MergeSort) sort2(a []Comparable, compare Compare) {
for sz := 1; sz < len(a); sz += sz {
for lo := 0; lo < len(a)-sz; lo += sz + sz {
this.merge(a, compare, lo, lo+sz-1, int(math.Min(float64(lo+sz+sz-1), float64(len(a)-1))))
}
}
}
下面我们来考虑下归并排序的效率问题。首先我们假设数组有N个元素,而N的值为2^n,所以采用归并排序的过程,可以用如下图的树状图表示:
图中每一个结点都表示一个merge()方法归并而成的一个数组。这棵树正好有n层。对于0到n-1之间的任意k,自顶向下的第k层有2^k个子数组,每个子数组又包含有2^(n-k)元素,所以归并操作最多需要2^(n-k)次比较。因此,每层的比较操作次数为2^n次,所以n次总共需要n2^n次比较操作。又由于N=2^n,所以归并排序整个数组最多需要n2^n=NlogN次比较操作。当然,每次归并操作最少需要2^(n-k)/2次比较,所以归并排序整个数组的话,最小需要NlogN/2次比较操作。综合上述分析,归并排序需要NlogN/2至NlogN次比较操作,因此其时间复杂度是线性对数型的,即O(NlogN)。
可见,归并排序是适合用于大规模数据排序的算法。但不要忘了,归并排序有个明显的缺陷,即她需要申请与排序数组相同大小的数组进行归并操作,在空间利用方面并不是十分理想,因此可能不适合用于空间不宽裕的场合。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。