golang的sort研究

guhao123 · · 3101 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

年前没钱，等发工资。就这么在公司耗着不敢回家，无聊看了下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的，嗯，原来这是两种计数。本质上木有任何关系，

有疑问加站长微信联系（非本文作者）