go 实现归并排序
0 / 0 / 创建于 4年前 /
Runtoweb3 的个人博客
归并排序：如果要排序一个数组，我们先把数组从中间分成前后两部分， 然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
复杂度是 O(nlogn)，非原地排序，比较耗空间。
func main() {
s := []int{6,7,8,10,4,6,99}
res := mergeSort(s)
fmt.Println(res)
}
func mergeSort(s []int) []int{
len := len(s)
if len == 1 {
return s //最后切割只剩下一个元素
}
m := len/2
leftS := mergeSort(s[:m])
rightS := mergeSort(s[m:])
return merge(leftS, rightS)
}
//把两个有序切片合并成一个有序切片
func merge(l []int, r []int) []int{
lLen := len(l)
rLen := len(r)
res := make([]int, 0)
lIndex,rIndex := 0,0 //两个切片的下标，插入一个数据，下标加一
for lIndex<lLen && rIndex<rLen {
if l[lIndex] > r[rIndex] {
res = append(res, r[rIndex])
rIndex++
}else{
res = append(res, l[lIndex])
lIndex++
}
}
if lIndex < lLen { //左边的还有剩余元素
res = append(res, l[lIndex:]...)
}
if rIndex < rLen {
res = append(res, r[rIndex:]...)
}
return res
}
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号