merge sort in golang

rufidmx · · 1462 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

package main

import (
	"fmt"
)

var tmp [len(src)]int
var src = [7]int{2, 4, 9, 7, 6, 1, 9}

//对排序好的分数组进行合并
func Merge(left, m, right int) {
	i := left
	j := left //标示把排序好的数放到临时数组的那个index
	w := m + 1

	//比较,把比较小的数字放到临时数组中去
	for i <= m && w <= right {
		if src[i] >= src[w] {
			tmp[j] = src[w]
			w += 1
		} else {
			tmp[j] = src[i]
			i += 1
		}
		j += 1
	}

	//把剩余数组中的数字依次copy到临时数组中去
	for i <= m {
		tmp[j] = src[i]
		i += 1
		j += 1
	}
	for w <= right {
		tmp[j] = src[w]
		w += 1
		j += 1
	}

	//把临时数组的数据copy到原数组中
	for left <= right {
		src[left] = tmp[left]
		left += 1
	}
}

func MergeSort(left, right int) {
	if left >= right {
		return
	}

	m := (left + right) / 2
	MergeSort(left, m)
	MergeSort(m+1, right)
	Merge(left, m, right)
}

func main() {
	MergeSort(0, len(src)-1)
	fmt.Println(src)
}
归并排序是经典的divide conquer算法。基本思想很简单,但是写代码的时候,要小心各种边界值和index的变换。



有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:rufidmx

查看原文:merge sort in golang

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1462 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传