文档章节

外排序之归并排序

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
粉丝 31
博文 74
码字总数 23007
作品 0
武汉
程序员

暂无文章

可爱的python测试开发库(python测试开发工具库汇总)

欢迎转载,转载请注明来源: github地址 谢谢点赞 本文地址 相关书籍下载 测试开发 Web UI测试自动化 splinter - web UI测试工具,基于selnium封装。 链接 selenium - web UI自动化测试。 链...

python测试开发人工智能安全
今天
2
0
Shiro | 实现权限验证完整版

写在前面的话 提及权限,就会想到安全,是一个十分棘手的话题。这里只是作为学校Shiro的一个记录,而不是,权限就应该这样设计之类的。 Shiro框架 1、Shiro是基于Apache开源的强大灵活的开源...

冯文议
今天
1
0
linux 系统的运行级别

运行级别 运行级别 | 含义 0 关机 1 单用户模式,可以想象为windows 的安全模式,主要用于修复系统 2 不完全的命令模式,不含NFS服务 3 完全的命令行模式,就是标准的字符界面 4 系统保留 5 ...

Linux学习笔记
今天
2
0
学习设计模式——命令模式

任何模式的出现,都是为了解决一些特定的场景的耦合问题,以达到对修改封闭,对扩展开放的效果。命令模式也不例外: 命令模式是为了解决命令的请求者和命令的实现者之间的耦合关系。 解决了这...

江左煤郎
今天
3
0
字典树收集(非线程安全,后续做线程安全改进)

将500W个单词放进一个数据结构进行存储,然后进行快速比对,判断一个单词是不是这个500W单词之中的;来了一个单词前缀,给出500w个单词中有多少个单词是该前缀. 1、这个需求首先需要设计好数据结...

算法之名
昨天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部