golang实现归并排序

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

  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)
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这...
    Winterfell_Z阅读 5,893评论 0 13
  • 1 初级排序算法 排序算法关注的主要是重新排列数组元素,其中每个元素都有一个主键。排序算法是将所有元素主键按某种方...
    深度沉迷学习阅读 1,431评论 0 1
  • 一、 单项选择题(共71题) 对n个元素的序列进行冒泡排序时,最少的比较次数是( )。A. n ...
    貝影阅读 9,179评论 0 10
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,214评论 0 52
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,270评论 0 2