文档章节

外排序之归并排序

smart_w
 smart_w
发布于 2016/01/31 18:15
字数 151
阅读 199
收藏 1
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]


© 著作权归作者所有

共有 人打赏支持
smart_w
粉丝 32
博文 74
码字总数 23007
作品 0
武汉
程序员
私信 提问

暂无文章

Spring boot 各种常用注解总结(不断完善中)

@Configuration把一个类作为一个IoC容器,它的某个方法头上如果注册了@Bean,就会作为这个Spring容器中的Bean。 @Scope注解 作用域 @Lazy(true) 表示延迟初始化 @Service用于标注业务层组件、...

覃大光
8分钟前
0
1
《让家庭教育回归生活》读书笔记3000字范文

《让家庭教育回归生活》读书笔记3000字范文: 以前,只知道新东方是教英语的,也培训挖掘机司机,一直不知道他们还研究家庭教育。读了《让家庭教育回归生活》一书,才知道他们的家庭教育高峰...

原创小博客
20分钟前
0
0
spring学习笔记(二)spring 事件的使用

spring 中的事件 spring事件通过订阅发布 可以解耦操作 可以同步 可以异步 步骤 编写事件 通过继承org.springframework.context.ApplicationEvent 来编写事件 public ApplicationEvent(Obj...

NotFound403
昨天
13
0
特斯拉车主成功破解了自己Model 3汽车

据汽车博客Electrek消息,一位特斯拉车主成功破解了自己Model 3汽车,还在此基础上运行了Ubuntu。 这位叫trsohmers的网友表示,“功劳大多要归到Ingineerix的头上,他花了数月才找到初始的那...

linuxCool
昨天
4
0
Gitbook : random errors when using gitbook plugin on running "gitbook serve"

在执行gitbook serve时,会有不定的失败错误 参考问题 :#1309 解决方案: 更新gitbook版本,这个问题似乎是3版本的问题 , 官方也不打算在这个版本解决了。 更新 到最新版本后, 不再出现问...

ol_O_O_lo
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部