合并排序-golang

合并排序

先对数组进行拆分，拆分成一个个单独的数字，然后再对拆分的数组进行合并。整体思路就是天下大事，分久必合。

image.png

如图所示，先对数组进行拆分，然后通过比较合并数组，因为每个合并的数组都是排好序的，因此可以通过遍历进行数组的合并。

代码

package main

import "fmt"

func mergeSort(a []int) []int {
    if len(a) < 2 {
        return a
    }
    m := (len(a)) / 2
    f := mergeSort(a[:m])
    s := mergeSort(a[m:])
    return merge(f, s)
}
func merge(f []int, s []int) []int {
    var i, j int
    size := len(f) + len(s)
    a := make([]int, size, size)
    for z := 0; z < size; z++ {
        lenF := len(f)
        lenS := len(s)
        if i > lenF-1 && j <= lenS-1 {
            a[z] = s[j]
            j++
        } else if j > lenS-1 && i <= lenF-1 {
            a[z] = f[i]
            i++
        } else if f[i] < s[j] {
            a[z] = f[i]
            i++
        } else {
            a[z] = s[j]
            j++
        }
    }
    return a
}
func main() {
    a := []int{75, 12, 34, 45, 0, 123, 32, 56, 32, 99, 123, 11, 86, 33}
    fmt.Println(a)
    fmt.Println(mergeSort(a))
}

时空复杂度

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。