归并排序-木庄网络博客

本文摘自网络，作者，侵删。

排序简介

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

先把n个元素分成n/2个元素的子序列，一直分到元素最小的序列；
然后分别对最小子序列排序，再把子序列合并排序。

图解参考https://www.cnblogs.com/chengxiao/p/6194356.html

复杂度

最佳情况：T(n) = O(nlogn)
最坏情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)
空间复杂度：O(n)
稳定性：稳定
排序方式：Out-place

golang实现

package main

import "fmt"

// 归并排序
func MergeSort(arr []int, a, b int)  {
    if b-a <= 1 {
        return
    }

    c := (a + b)/2
    MergeSort(arr, a, c)
    MergeSort(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{33,11,55,7,44,1}
    MergeSort(arr, 0, len(arr))
    fmt.Println(arr)
}

本文来自：简书

感谢作者：樹澤

查看原文：归并排序

相关阅读 >>

用 Go stl 查询 db 引发的内存泄露

Golang如何创建目录

记录Golang recover的一个小坑

详解Golang发送邮件（qq邮箱）

Golang怎么解析json格式

[译]Go语言内存布局

模块二 Go语言进阶技术-panic函数、recover函数以及defer语句(下)

聊聊nacos-coredns-plugin的domain