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