golang sort底层排序

golang里面有一个sort的包,用来给定的数据序列进行排序,那你知道其底层使用是哪种排序算法吗?插入排序,选择排序,快速排序,还是shell排序?

在sort里面最后排序都是使用Sort函数,看下Sort函数的源码:(源码路径:/src/sort/sort.go)

// 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) {
    n := data.Len()
    quickSort(data, 0, n, maxDepth(n))
}

从函数中发现使用的快速排序,那么我们再看下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)
    }
}

最终发现底层使用是快速排序,但是是在快速排序的基础上进行优化了,以提升排序的综合性能。

golang 快速排序
golang逗号模式
标签:

发表我的评论

电子邮件地址不会被公开。 必填项已用*标注

45 + 56 =

ajax-loader