說明

歸并排序是建立在歸并操作上的一種有效的排序。該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。

邏輯

分：將一個無序數(shù)列分解為有序序列，既將一個無序數(shù)列分解為一個個單個元素的數(shù)列。

治：將兩個有序數(shù)列合并成一個有序數(shù)列。

分治完成后，即得到一個完整的有序數(shù)列。

代碼

package arithmetic

import (
    "math"
)

//InterfaceSort 排序接口 
type InterfaceSort interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

//InterfaceSortMerge 歸并排序接口
type InterfaceSortMerge interface {
    InterfaceSort
    GetElement(i int) interface{}
    SetElement(element interface{}, i int)
}

//SortMerge 歸并排序
func SortMerge(slice InterfaceSortMerge) {
    tmpSlice := make([]interface{}, slice.Len(), slice.Len())
    divideAndConquer(slice, 0, slice.Len()-1, tmpSlice)
}

func divideAndConquer(slice InterfaceSortMerge, bg int, ed int, tmpSlice []interface{}) {

    if bg >= ed {
        return
    }

    md := (bg + ed) / 2
    divideAndConquer(slice, bg, md, tmpSlice)
    divideAndConquer(slice, md+1, ed, tmpSlice)
    conquer(slice, bg, md, ed, tmpSlice)
}

func conquer(slice InterfaceSortMerge, bg int, md int, ed int, tmpSlice []interface{}) {

    var l = bg
    var r = md + 1
    var i = 0
    for l <= md && r <= ed {
        if slice.Less(l, r) {
            tmpSlice[i] = slice.GetElement(l)
            l++
            i++
        } else {
            tmpSlice[i] = slice.GetElement(r)
            r++
            i++
        }
    }
    for l <= md {
        tmpSlice[i] = slice.GetElement(l)
        l++
        i++
    }
    for r <= ed {
        tmpSlice[i] = slice.GetElement(r)
        r++
        i++
    }
    i = 0
    for bg <= ed {
        slice.SetElement(tmpSlice[i], bg)
        i++
        bg++
    }
}

代碼說明

面向?qū)ο髮崿F(xiàn)，結(jié)構(gòu)體實現(xiàn)相關(guān)接口即可調(diào)用該函數(shù)。

排序結(jié)果通過參數(shù)返回。

divideAndConquer 遞歸調(diào)用，將數(shù)列分治。

conquer 為治程序，將兩個數(shù)列合并。

測試代碼

package  main

import (
    "AZframework/arithmetic"
    "fmt"
)

//IntSlice []int
type IntSlice []int

func (s IntSlice) Len() int           { return len(s) }
func (s IntSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }

//GetElement 歸并接口
func (s IntSlice) GetElement(i int) interface{} { return s[i] }

//SetElement 歸并接口
func (s IntSlice) SetElement(element interface{}, i int) { s[i] = element.(int) }

func main() {
    sliceC = IntSlice{5, 5, 4, 3, 2, 1, 1}
    arithmetic.SortMerge(sliceC)
    fmt.Printf("SortMerge slice = %v \n", sliceC)
}

日志輸出

SortMerge slice = [1 1 2 3 4 5 5]