Go-归并排序

归并排序

• 算法实现

func merge(list []int, left, mid, right int) {
    lLen := mid - left + 1
    rLen := right - mid
    length := lLen + rLen
    result := make([]int, length)
    // 左边起始位置：left 右边起始位置mid + 1
    // 真实位置： 起始位置 + 索引位置
    for idx, lIdx, rIdx := 0, 0, 0; idx < length; idx++ {
        if lIdx >= lLen {
            result[idx] = list[mid+1+rIdx]
            rIdx++
        } else if rIdx >= rLen {
            result[idx] = list[left+lIdx]
            lIdx++
        } else if list[left+lIdx] > list[mid+1+rIdx] {
            result[idx] = list[mid+1+rIdx]
            rIdx++
        } else {
            result[idx] = list[left+lIdx]
            lIdx++
        }
    }
    // 写回去
    for idx := 0; idx < length; idx++ {
        list[left+idx] = result[idx]
    }
}

func MergeSort(list []int, left, right int) {
    if left < right {
        mid := (left + right) / 2
        MergeSort(list, left, mid)
        MergeSort(list, mid+1, right)
        merge(list, left, mid, right)
    }
}

• 测试代码

func main() {
    list := []int{8, 4, 8, 2, 9, 10, -3, 3, 20, 15, -1}
    function.MergeSort(list, 0, len(list)-1)
    fmt.Println(list)
}

• 排序结果

[-3 -1 2 3 4 8 8 9 10 15 20]

• 时间复杂度

O (nlogn)

• 空间复杂度

就是 n + logn，所以是线性空间复杂度

O (n)