golang的sort研究

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

年前没钱,等发工资。就这么在公司耗着不敢回家,无聊看了下golang的sort源码

type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    Swap(i, j int)
}

只有实现这个接口才可以调用sort.Sort()进行排序哒

贴上源码实现,这就是常用的排序,时间复杂度是O(n*log(n))。。那就是快排、堆排序之类的啦

// Sort sorts data.
// It makes one call to data.Len to determine n, and O(n*log(n)) calls to
// data.Less and data.Swap. The sort is not guaranteed to be stable.
func Sort(data Interface) {
    // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
    n := data.Len()
    maxDepth := 0
    for i := n; i > 0; i >>= 1 {
        maxDepth++
    }
    maxDepth *= 2
    quickSort(data, 0, n, maxDepth)
}

它用的是quicksort。然而,它还有个maxDepth。让我很恼火。这不多余的变量么。然后就去看quicksort的实现。我了个擦。第一次见这么写快排的

func quickSort(data Interface, a, b, maxDepth int) {
    for b-a > 12 { // Use ShellSort for slices <= 12 elements
        if maxDepth == 0 {
            heapSort(data, a, b)
            return
        }
        maxDepth--
        mlo, mhi := doPivot(data, a, b)
        // Avoiding recursion on the larger subproblem guarantees
        // a stack depth of at most lg(b-a).
        if mlo-a < b-mhi {
            quickSort(data, a, mlo, maxDepth)
            a = mhi // i.e., quickSort(data, mhi, b)
        } else {
            quickSort(data, mhi, b, maxDepth)
            b = mlo // i.e., quickSort(data, a, mlo)
        }
    }
    if b-a > 1 {
        // Do ShellSort pass with gap 6
        // It could be written in this simplified form cause b-a <= 12
        for i := a + 6; i < b; i++ {
            if data.Less(i, i-6) {
                data.Swap(i, i-6)
            }
        }
        insertionSort(data, a, b)
    }
}

解释下变量,a:起始位置,b:结束位置 ,maxDepth:深度,这个参数在Sort()中计算好了,是通过右移算出来的。so。这就是所有元素构建的完全二叉树的深度哈。这狗日的要在快排里用heapsort了,算完了理论上构建的完全二叉树的深度后。它maxDepth *= 2 来了这一手,让我抽根烟冷静冷静。它得到的是这些元素组成的最深的二叉树的深度,高手啊。然后带quicksort的代码中来瞅瞅。当需要排序的元素大于12个的时候。。快排啊。就是这里还判断了深度是否为0,一头雾水啊,这是在搞什么?这个for循环有两个退出条件,1:b-a<12了。2:maxDepth==0。so,为嘛会有maxDepth==0啊。此时的待排序元素可是大于12的,嗯,原来这是两种计数。本质上木有任何关系,


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

本文来自:博客园

感谢作者:guhao123

查看原文:golang的sort研究

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

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