golang实现归并排序

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

归并排序的操作步骤如下:

  1. 首先将数组一份为二,分别为左数组和右数组
  2. 若左数组的长度大于1,那么对左数组实施归并排序
  3. 若右数组的长度大于1, 那么对右数组实施归并排序
  4. 将左右数组进行合并

代码如下:

package main

import (
    "fmt"
)

// mergerSort
func mergerSort(arr []int, a, b int) {
    if b-a <= 1 {
        return
    }

    c := (a + b) / 2
    mergerSort(arr, a, c)
    mergerSort(arr, c, b)

    arrLeft := make([]int, c-a)
    arrRight := make([]int, b-c)
    copy(arrLeft, arr[a:c])
    copy(arrRight, arr[c:b])
    i := 0
    j := 0
    for k := a; k < b; k++ {
        if i >= c-a {
            arr[k] = arrRight[j]
            j++
        } else if j >= b-c {
            arr[k] = arrLeft[i]
            i++
        } else if arrLeft[i] < arrRight[j] {
            arr[k] = arrLeft[i]
            i++
        } else {
            arr[k] = arrRight[j]
            j++
        }
    }
}

func main() {
    // 测试代码
    arr := []int{9, 8, 7, 6, 5, 1, 2, 3, 4, 0}
    fmt.Println(arr)
    mergerSort(arr, 0, len(arr))
    fmt.Println(arr)
}

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

本文来自:简书

感谢作者:IT孤独者

查看原文:golang实现归并排序

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

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