golang 归并排序

夜空中乄最亮的星 · · 271 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

归并排序的时间复杂度为: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]

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:夜空中乄最亮的星

查看原文:golang 归并排序

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

271 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传