内容简介:查看完整的代码,不了解归并排序的可以查看
查看完整的代码, 点击这里
归并排序的实现
基本实现
package main import "fmt" // 合并 [l,r] 两部分数据,mid 左半部分的终点,mid + 1 是右半部分的起点 func merge(arr []int, l int, mid int, r int) { // 因为需要直接修改 arr 数据,这里首先复制 [l,r] 的数据到新的数组中,用于赋值操作 temp := make([]int, r-l+1) for i := l; i <= r; i++ { temp[i-l] = arr[i] } // 指向两部分起点 left := l right := mid + 1 for i := l; i <= r; i++ { // 左边的点超过中点,说明只剩右边的数据 if left > mid { arr[i] = temp[right-l] right++ // 右边的数据超过终点,说明只剩左边的数据 } else if right > r { arr[i] = temp[left-l] left++ // 左边的数据大于右边的数据,选小的数字 } else if temp[left - l] > temp[right - l] { arr[i] = temp[right - l] right++ } else { arr[i] = temp[left - l] left++ } } } func MergeSort(arr []int, l int, r int) { if l >= r { return } // 递归向下 mid := (r + l) / 2 MergeSort(arr, l, mid) MergeSort(arr, mid+1, r) // 归并向上 merge(arr, l, mid, r) } func main() { arr := []int{3, 1, 2, 5, 6, 43, 4} MergeSort(arr, 0, len(arr)-1) fmt.Println(arr) }
优化点
-
只有左边数据的最大值大于右边数据的最小值时才需要归并
举例:现在需要归并的左右部分为 [1,3] 和 [4,5],则不需要进行「并」的操作。而 [1,4] 和 [3,5] 则需要进行「并」为 [1,3,4,5]
-
当二分数据到一定阶段,可以使用插入排序而不是继续向下二分
虽然复杂度上看 nlogn 始终大于 n^2,但是都忽略了常数项,而归并的常数项大于插入排序,所以当 n 足够小时,插入排序速度更快
以下是结合优化点的程序更改:
package main import "fmt" func merge(arr []int, l int, mid int, r int) { temp := make([]int, r-l+1) for i := l; i <= r; i++ { temp[i-l] = arr[i] } left := l right := mid + 1 for i := l; i <= r; i++ { if left > mid { arr[i] = temp[right-l] right++ } else if right > r { arr[i] = temp[left-l] left++ } else if temp[left - l] > temp[right - l] { arr[i] = temp[right - l] right++ } else { arr[i] = temp[left - l] left++ } } } func MergeSort(arr []int, l int, r int) { // 第二步优化,当数据规模足够小的时候,可以使用插入排序 if r - l <= 15 { // 对 l,r 的数据执行插入排序 for i := l + 1; i <= r; i++ { temp := arr[i] j := i for ; j > 0 && temp < arr[j-1]; j-- { arr[j] = arr[j-1] } arr[j] = temp } return } mid := (r + l) / 2 MergeSort(arr, l, mid) MergeSort(arr, mid+1, r) // 第一步优化,左右两部分已排好序,只有当左边的最大值大于右边的最小值,才需要对这两部分进行merge操作 if arr[mid] > arr[mid + 1] { merge(arr, l, mid, r) } } func main() { arr := []int{3, 1, 2, 5, 6, 43, 4} MergeSort(arr, 0, len(arr)-1) fmt.Println(arr) }
以上所述就是小编给大家介绍的《归并排序的 Go 语言实现和优化》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- MergeSort归并排序和利用归并排序计算出数组中的逆序对
- 归并排序与快速排序
- F# 插入排序 和归并排序
- F# 插入排序 和归并排序
- 算法之常见排序算法-冒泡排序、归并排序、快速排序
- 深入浅出排序算法(2)-归并排序
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
劫持
玛丽•K. 斯温格尔(Mari K. Swingle) / 邓思渊 / 中信出版集团股份有限公司 / 2018-5-1 / CNY 59.00
《劫持》是一本探讨人与科技的关系的书,基于一位心理学博士20年的临床经验及其作为神经认知科学研究者的脑—电研究成果。在这本面向大众的科普书中,作者以深入浅出的方式,探讨了手机、电脑等便携式数字设备及让人“永不下线”的互联网对现代人尤其是青少年大脑的影响,从神经认知科学和精神分析的角度,有力地证明了数字媒介与大脑和人类行为的关系,探讨了手机等如何对人的大脑进行劫持或操控,并给出了自己作为从业医师的实......一起来看看 《劫持》 这本书的介绍吧!