(2)Go实现递归排序及改进

递归排序的思想是分治法，即将问题划分为若干相互独立的个小问题，这些问题和该问题具有相同的特征，将这些小问题解决后，该问题也解决了。
按照这种思想，递归排序分为自上而下，自下而上2种
如下图示：

自上而下
自下而上

递归排序的实现
// 递归排序: 自上向下
func MergerSort1(arr []int) (resp []int) {
    l1 := len(arr)
    if l1 < 2 {
        return arr
    }
    mid := l1 / 2
    return Merger(MergerSort1(arr[:mid]), MergerSort1(arr[mid:]))
}

// 递归排序和插入排序相结合的排序
func MergerSort2(arr []int) (resp []int) {
    l1 := len(arr)

    if l1 < 100 {
        return InsertionSort(arr, l1)
    }

    mid := l1 / 2
    return Merger(MergerSort2(arr[:mid]), MergerSort2(arr[mid:]))
}

// 递归排序:自下向上
func MergerSortBU(arr []int) []int {
    l1 := len(arr)

    if l1 < 100 {
        return InsertionSort(arr, l1)
    }

    for sz := 1; sz < l1; sz += sz {
        for i := 0; i < l1-sz; i += sz + sz {
            copy(arr[i:min(i+sz+sz, l1)], Merger(
                arr[i:i+sz],
                arr[i+sz:min(i+sz+sz, l1)]))
        }
    }
    return arr
}

func Merger(arr1, arr2 []int) (resp []int) {
    l1 := len(arr1)
    l2 := len(arr2)

    i, j := 0, 0
    for i < l1 || j < l2 {
        switch {
        case j == l2:
            resp = append(resp, arr1[i])
            i++
        case i == l1:
            resp = append(resp, arr2[j])
            j++
            // 能到这里说明i<l1,j<l2
        case arr1[i] <= arr2[j]:
            resp = append(resp, arr1[i])
            i++
        default: // arr2[i] > arr2[j]
            resp = append(resp, arr2[j])
            j++
        }
    }
    return resp
}

// 插入排序
func InsertionSort(s []int, l int) []int {
    for i := 1; i < l; i++ {
        buf := s[i]
        var j int
        for j = i; j > 0 && s[j-1] > buf; j-- {
            s[j] = s[j-1]
        }
        s[j] = buf
    }
    return s
}

func min(i1, i2 int) int {
    if i1 > i2 {
        return i2
    }
    return i1
}

测试
const count = 1000

func main() {
    nums2 := [count]int{}
    for i := 0; i < count; i++ {
        nums2[i] = rand.Intn(count)
    }

    for i := 0; i < 4; i++ {
        nums3 := nums2
        nums := nums3[:]
        t := time.Now()
        switch i {
        case 0:
            nums = merger.InsertionSort(nums, count)
            fmt.Println("插入排序花费时间:", t.Sub(time.Now()))
            isTrue(nums)
        case 1:
            nums = merger.MergerSort1(nums)
            fmt.Println("递归排序花费时间:", t.Sub(time.Now()))
            isTrue(nums)
        case 2:
            nums = merger.MergerSort2(nums)
            fmt.Println("递归插入结合自上而下花费时间:", t.Sub(time.Now()))
            isTrue(nums)
        case 3:
            nums = merger.MergerSortBU(nums)
            fmt.Println("递归结合插入自下向上花费时间:", t.Sub(time.Now()))
            isTrue(nums)
        }
        fmt.Println("----")
    }
}

func isTrue(nums []int) {
    b := true
    for i := 1; i < count; i++ {
        if nums[i-1] > nums[i] {
            fmt.Println("排序错误", nums[i-1], nums[i])
            b = false
            break
        }
    }
    if b {
        fmt.Println("排序正确")
    }
}
// 分别令count=100，1000，10000
1）count=100
插入排序花费时间: -3.818µs
排序正确
----
递归排序花费时间: -46.523µs
排序正确
----
递归插入结合自上而下花费时间: -4.383µs
排序正确
----
递归结合插入自下向上花费时间: -29.861µs
排序正确

2）count=1000
插入排序花费时间: -221.893µs
排序正确
----
递归排序花费时间: -409.8µs
排序正确
----
递归插入结合自上而下花费时间: -110.996µs
排序正确
----
递归结合插入自下向上花费时间: -403.085µs

3）count=10000
插入排序花费时间: -22.420067ms
排序正确
----
递归排序花费时间: -8.385759ms
排序正确
----
递归插入结合自上而下花费时间: -6.942241ms
排序正确
----
递归结合插入自下向上花费时间: -6.024227ms
排序正确

结论：在数据量较小时，插入排序速度较快，在数据量大时候，递归排序较快，因此两者可以结合起来，
在数据量较大时，用递归排序，在数据量较小时，用插入排序，两者结合速度比单一的递归排序更快些，
而递归排序自上而下和自下而上两种速度差不多。

时间复杂度分析 //
插入排序为O(n^2)，递归排序时间复杂度为nlogn