1. 说明
归并排序（MERGE-SORT） 是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。百度百科
现在让我带领大家看看怎么实现的吧！
2. 归并排序
一个时间性能比较好的排序方法，但是它的空间复杂度较高T(n)
2.1. 实现过程
通过递归将数组一直切割直至为将数组分成两两一组。排序完成之后往上层回溯，此时变成四四一组…重复上述过程直到递归结束。
2.2. 代码片段 - 自顶向下
2.2.1.代码片段
func MergeSort(arr []int) {
n := len(arr)
mergeSort(arr, 0, n-1)//注意这里的区间[0...r]，归并的过程中需要保持这个区间的性质不变。
}
func mergeSort(arr []int, l, r int) {
if l >= r {//当 l==r 的时候已经不需要递归分割了
return
}
mid := l + (r-l)/2 //公认防止整形溢出的写法。
mergeSort(arr, l, mid) //分割左边的数组
mergeSort(arr, mid+1, r)//分割右边的数组
_mergeSort(arr, l, mid, r) //在最底层往上开始处理数据
}
func _mergeSort(arr []int, l, mid, r int) {
if arr[mid+1] > arr[mid] { //归并优化，在右边大于左边的数值时，此时两个数组已经保持了顺序，不需要再排序了。
return
}
arrTemp := make([]int, len(arr[l : r+1]))
copy(arrTemp, arr[l:r+1]) //拷贝一份数组
i := l
j := mid + 1 //这里的i和j分别是两个数组的起点。
for k := l; k <= r; k++ {
if i > mid {//mid这个位置是闭区间，所以包含mid这个位置。当超过的时候才将j所在的数组全部补进去
arr[k] = arrTemp[j-l]
j++
} else if j > r {// 同 ↑
arr[k] = arrTemp[i-l]
i++
} else if arrTemp[i-l] <= arrTemp[j-l] { // <= 保证了归并过程中保持稳定性
arr[k] = arrTemp[i-l]
i++
} else {// 当且仅当 arrTemp[i-l] > arrTemp[j-l] 的时候才将 j所在的数据填入原数组
arr[k] = arrTemp[j-l]
j++
}
}
}
2.2.2. 代码解释
-
归并过程中，拷贝一份此区间的数组。然后通过比对这个数组的左右两边依次将较小的数据赋值给原数组。此时这份分割后的数组就是排序完成的。
-
加入了优化代码 arr[mid+1] > arr[mid] 此时数组已经有序不需要再进行操作。
2.3. 代码片段 - 自底向上
2.3.1. 代码片段
func MergeSortBottomUp(arr []int) {
n := len(arr)
for sz := 1; sz < n; sz = 2 * sz {
for i := 0; i+sz < n; i += 2 * sz {
_mergeSort(arr, i, i+sz-1, int(math.Min(float64(i+sz+sz-1), float64(n-1))));
}
}
}
2.3.2. 代码解释
-
_mergeSort() 的代码与自顶向下的方法一样。
-
本质上for循环仅仅是模拟了递归过程中，将数组切分开的元素位置。
-
需要主要的是右边界的问题，因为数组可能是无法刚好分割成整数的，所有在个别情况下应当只能取到数组的最大长度。
😁😁😁制作动画过程不易，烦请大家顺手点赞收藏咯 😁😁😁