golang 归并排序（Merge Sort）算法思想及其实现

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 

1 算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

2 动图演示

3：golang代码

func merger(a []int, b []int) []int {
	var alen int = len(a)
	var blen int = len(b)
	var ablen int = alen + blen
	var l int = 0
	var r int = 0
	var res []int = make([]int, ablen)
	for i := 0; i < ablen; i++ {
		if l >= alen {
			res[i] = b[r]
			r++
		} else if r >= blen {
			res[i] = a[l]
			l++
		} else if a[l] < b[r] || a[l] == b[r] {
			res[i] = a[l]
			l++
		} else {
			res[i] = b[r]
			r++
		}
	}
	return res
}

//归并排序
func mergeSort(arrs []int) []int {
	if len(arrs) < 2 {
		return arrs
	}

	var mid int = len(arrs) / 2

	var left []int = mergeSort(arrs[0:mid])
	var right []int = mergeSort(arrs[mid:])

	return merger(left, right)
}

4：测试性能代码对 归并排序 插入排序  选择排序 算法对比代码

package main

import (
	"fmt"
	"math/rand"

	"time"
)

func main() {
	arrs := randomArrInt(50000, 100000) //随机生成数组

	execSort(arrs, mergeSort, "mergeSort") //归并排序
	execSort(arrs, insertSort, "insertSort") //插入排序
    execSort(arrs, selectionSort, "selectionSort") //选择排序

}


func execSort(arra []int, code func(arrs []int) []int, name string) {
	s := time.Now()
	code(arra)
	e := time.Now()
	fmt.Println(name, ":", e.Sub(s))
}

//随机生成int数组
func randomArrInt(n, end int) []int {
	var newArr []int = make([]int, n)
	var s rand.Source = rand.NewSource(time.Now().Unix())

	var r *rand.Rand = rand.New(s)

	for i := 0; i < n; i++ {
		newArr[i] = r.Intn(end)
	}

	return newArr
}

5：分别随机生成50个 和 50000个长度的数组对比排序时间

50长度的数组：

 

mergeSort : 20.268µs

insertSort : 1.858µs  //用时最短

selectionSort : 2.633µs

50000长度的数组：

mergeSort : 11.583757ms //用时最短

insertSort : 1.210069844s

selectionSort : 1.665799702s

可通过排序耗时的对比，对数组长度的大小选择相对应的排序算法。