归并排序及go语言实现

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

归并排序的基本思想

将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。

综上可知:

归并排序其实要做两件事:

(1)“分解”——将序列每次折半划分。


(2)“合并”——将划分后的序列段两两合并后排序。

归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。

如 设有数列{6,202,100,301,38,8,1}

初始状态:6,202,100,301,38,8,1

第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;

第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;

第三次归并后:{1,6,8,38,100,202,301},比较次数:4;

总的比较次数为:3+4+4=11,;

package algomithms

import "fmt"

type MergeSort struct {
}

func (object MergeSort) Sort(values []int) {
 mergeSort(values)
}

func mergeSort(values []int) {
 length := len(values)
 gap := 1
 for gap < length {
  fmt.Println("  --merge by gap ", gap)
  mergebygap(values, gap)
  gap = gap * 2
  fmt.Println("    --the tuple is ", values)
 }
}

func mergebygap(values []int, gap int) {
 length := len(values)
 for i := 0; i < length; i += 2 * gap {
  mergeTwoValues(values, i, gap)
 }
}

func mergeTwoValues(values []int, start int, gap int) {

 // fmt.Println("    ---- try to merge", values[start:start+gap], "and ", values[start+gap:start+2*gap])
 length := len(values)
 if start+gap >= length {
  return
 }
 slice := make([]int, 2*gap)
 lpos, rpos, slicepos := start, start+gap, 0
 for lpos < start+gap && (rpos < start+2*gap && rpos < length) {
  if values[lpos] <= values[rpos] {
   slice[slicepos] = values[lpos]
   lpos++
  } else {
   slice[slicepos] = values[rpos]
   rpos++
  }
  slicepos++
 }
 if lpos != start+gap {
  for lpos < start+gap {
   slice[slicepos] = values[lpos]
   lpos++
   slicepos++
  }
 } else if rpos != start+2*gap && rpos != length {
  for rpos < start+2*gap && rpos < length {
   slice[slicepos] = values[rpos]
   rpos++
   slicepos++
  }
 }
 for i := 0; i < slicepos; i++ {
  values[i+start] = slice[i]
 }
 fmt.Println("    ----  merge result is ", slice[:slicepos])
 // fmt.Println("    ----  merge result is ", values[start:start+2*gap])
}

 


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

本文来自:CSDN博客

感谢作者:zhaoguoguang

查看原文:归并排序及go语言实现

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

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