Go 数据结构和算法篇(七):归并排序
一、实现原理
今天介绍比前面三种排序算法性能更好的排序算法 —— 归并排序。
所谓归并排序,指的是如果要排序一个数据序列,我们可以先把该序列从中间分成前后两部分,然后对这两部分分别做排序操作,再将排好序的两部分合并在一起,这样整个数据序列就都有序了。
归并排序使用了分治思想,分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。说到这里,可能你会联想起我们之前讲到的一个编程技巧 —— 递归,没错,归并排序就是通过递归来实现的。这个递归的公式是每次都将传入的待排序数据序列一分为二,直到变成不能继续分割的最小区间单元,然后将最小区间单元数据排序后合并起来,最终返回的就是排序好的数据序列了。图示如下:
归并排序图示
由于涉及到递归,所以归并排序从理解上要比前面三个排序要困难一些,还是建议通过这个动态图帮助理解:https://visualgo.net/zh/sorting(在界面顶部选择归并排序,然后在左下角点击执行即可)。
二、示例代码
通过上面的分析,我们知道归并=递归+合并,对应的 Go 实现代码如下:
package main
import (
"fmt"
)
// 归并排序
func mergeSort(nums []int) []int {
if len(nums) <= 1 {
return nums
}
// 获取分区位置
p := len(nums) / 2
// 通过递归分区
left := mergeSort(nums[0:p])
right := mergeSort(nums[p:])
// 排序后合并
return merge(left, right)
}
// 排序合并
func merge(left []int, right []int) []int {
i, j := 0, 0
m, n := len(left), len(right)
// 用于存放结果集
var result []int
for {
// 任何一个区间遍历完,则退出
if i >= m || j >= n {
break
}
// 对所有区间数据进行排序
if left[i] <= right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
// 如果左侧区间还没有遍历完,将剩余数据放到结果集
if i != m {
for ; i < m; i++ {
result = append(result, left[i])
}
}
// 如果右侧区间还没有遍历完,将剩余数据放到结果集
if j != n {
for ; j < n; j++ {
result = append(result, right[j])
}
}
// 返回排序后的结果集
return result
}
func main() {
nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
sortedNums := mergeSort(nums)
fmt.Println(sortedNums)
}
运行上述代码,打印结果如下:
三、性能分析
最后我们来看下归并排序的性能:
- 归并排序不涉及相等元素位置交换,是稳定的排序算法;
- 时间复杂度是 O(nlogn),要优于冒泡排序和插入排序的 O(n2);
- 归并排序需要额外的空间存放排序数据,不是原地排序,最多需要和待排序数据序列同样大小的空间,所以空间复杂度是 O(n)。
归并排序的时间复杂度推导过程
归并的思路是将一个复杂的问题 a 递归拆解为子问题 b 和 c,再将子问题计算结果合并,最终得到问题的答案,这里我们将归并排序总的时间复杂度设为 T(n)
,则 T(n) = 2*T(n/2) + n
,其中 T(n/2)
是递归拆解的第一步对应子问题的时间复杂度,n
则是排序合并函数的时间复杂度(一个循环遍历),依次类推,我们可以推导 T(n)
的计算逻辑如下:
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= ...
= 2^k*T(n/2^k) + k*n
递归到最后,T(n/2k)≈T(1),也就是 n/2k = 1,计算归并排序的时间复杂度,就演变成了计算 k 的值,2k = n,所以 k=log2n,我们把 k
的值带入上述 T(n)
的推导公式,得到:
T(n) = n*T(1) + n*log2n = n(C + log2n)
注:上述公式中 2 是下标,即 log2n。
把常量和低阶忽略,所以 T(n) = nlogn
。
(本文完)
相关文章
- go实现常见排序算法
- 封面选的好,绅士少不了!别闹了,还是好好刷Go易错的知识点吧~
- Go 1.18 让写测试的代码量骤减,你会开始写测试吗?
- Go 语言为什么建议 append 追加新元素使用原切片变量接收返回值?
- 前后端分离项目(gin+gorm+vue3)腾讯云部署详细教程(go,mysql,nginx安装)
- go语言 ssh_websshpro
- Go 数据结构和算法篇(三):队列
- Go 数据结构和算法篇(五):插入排序
- Go 数据结构和算法篇(十一):字符串匹配之 BF 算法
- Go 数据结构和算法篇(十四):哈希表、哈希函数、哈希冲突和哈希算法
- 从CPU角度理解Go中的结构体内存对齐
- 「Go工具箱」将文件大小转换成Kb、Mb、Gb就用这个库:go-humanize
- 「Go工具箱」一个简单、易用的多错误管理包:go-multierror
- 避坑:Go并发编程时,如何避免发生竞态条件和数据竞争
- Go语言go mod包依赖管理工具使用详解
- Go语言圣经-Panic异常,Recover捕获异常习题详解编程语言
- Go语言表达式求值器
- Linux上构建Go开发环境(linux安装go环境)
- 如何在Linux上安装Go语言?——简单易懂的指南(linux安装go语言)
- 便捷使用Go编程连接Redis(go连接redis)
- 使用Go语言实现Redis数据库(用go实现redis)
- 提升Go读取Oracle的速度(go读取oracle速度)
- 一步一步学习Go读取Oracle数据库(go读取oracle)
- 新技术Go语言解析Oracle数据库日志(go解析oracle日志)
- Redis集群搭建Go的艰难之路(redis集群搭建go)