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 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)
}

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)
 }
}

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

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传