golang sort底层排序
嘻嘻发布于2022-07-29
最后更新于2022年7月19日
浏览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)
}
}
最终发现底层使用是快速排序,但是是在快速排序的基础上进行优化了,以提升排序的综合性能。