外排序之归并排序
外排序之归并排序
golang_yh 发表于2年前
外排序之归并排序
  • 发表于 2年前
  • 阅读 195
  • 收藏 1
  • 点赞 1
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

摘要: golang每天刷刷小算法
package main

import (
	"fmt"
)

//外排序之归并排序,归并排序最大特点是用了一个O(N)存储空间

func mergeSort(r []int) []int {
	length := len(r)
	if length <= 1 {
		return r
	}
	num := length / 2
	left := mergeSort(r[:num])
	right := mergeSort(r[num:])
	return merge(left, right)
}
func merge(left, right []int) (result []int) {
	l, r := 0, 0
	for l < len(left) && r < len(right) {
		if left[l] < right[r] {
			result = append(result, left[l])
			l++
		} else {
			result = append(result, right[r])
			r++
		}
	}
	result = append(result, left[l:]...)
	result = append(result, right[r:]...)
	return
}

func main() {
	arr := []int{4, 1, 2, 9, 17, 5}
	arr1 := mergeSort(arr)
	fmt.Printf("main.arr:%v\n", arr1)
}

输出结果:

main.arr:[1 2 4 5 9 17]


共有 人打赏支持
粉丝 30
博文 86
码字总数 24924
×
golang_yh
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: