golang 归并排序

归并排序的时间复杂度为:O(nlogn)

func HeapSort(data []int) []int {
    len := len(data)
    if len <=1 {
        return data
    }
    //将待排序的数组划分为左右2部分，递归的进行
    mid :=len/2
    left :=data[:mid]
    right :=data[mid:]
    left= HeapSort(left)
    right= HeapSort(right)
    //对划分后的两部分进行排序
    return Sort(left,right)
}

func Sort(left []int,right []int) []int {
    llen :=len(left)
    rlen :=len(right)
    var tmp []int

    i,j:=0,0

    for  {
        //如果left先遍历结束，则将right剩余部分追加到tmp中
        if i >=llen{
            tmp =append(tmp,right[j:]...)
            break
        }
        //如果right部分先遍历结束，则将left剩余部分追加到tmp中
        if j >=rlen{
            tmp =append(tmp,left[i:]...)
            break
        }
        //比较left和right将较小的元素存入tmp
        if left[i] < right[j]  {
            tmp =append(tmp,left[i])
            i++
        }else{
            tmp =append(tmp,right[j])
            j++
        }
    }
    return tmp
}


//测试：
func main() {
    arr :=[]int{0,1,5,2,3,8,0,4,9,2}
    r:=HeapSort(arr)
    fmt.Println(r)
}
输出：[0 0 1 2 2 3 4 5 8 9]