sort.png

Sort

Sort 是每个编程语言中必不可少的方法，并且对新手来说是比较适合入门学习的内容，那么今天我们来看一下 Go 中的 sort 标准库，了解 Go 中是怎么实现 Sort 方法的。

在源码中，Sort 方法传入的是一个实现了 Interface 接口的实例，从命名上不难看出，Len 用来获取数据的长度，Less 用来比较两个元素的大小，Swap 用来交换两个元素的位置。Sort 方法首先调用 Len 方法获取数据的长度，之后使用 quickSort（快速排序） 来对数据进行排序。

  1. func Sort(data Interface) {
  2.     n := data.Len()
  3.     quickSort(data, 0, n, maxDepth(n))
  4. }
  6. // ...
  8. type Interface interface {
  9.     // Len is the number of elements in the collection.
  10.     Len() int
  12.     // Less reports whether the element with index i
  13.     // must sort before the element with index j.
  14.     //
  15.     // If both Less(i, j) and Less(j, i) are false,
  16.     // then the elements at index i and j are considered equal.
  17.     // Sort may place equal elements in any order in the final result,
  18.     // while Stable preserves the original input order of equal elements.
  19.     //
  20.     // Less must describe a transitive ordering:
  21.     //  - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
  22.     //  - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
  23.     //
  24.     // Note that floating-point comparison (the < operator on float32 or float64 values)
  25.     // is not a transitive ordering when not-a-number (NaN) values are involved.
  26.     // See Float64Slice.Less for a correct implementation for floating-point values.
  27.     Less(i, j int) bool
  29.     // Swap swaps the elements with indexes i and j.
  30.     Swap(i, j int)
  31. }

继续看 quickSort 方法，我们会发现有各种不同的排序方法，在不同的情况下分别使用。在 L2 ～ L18 中定义了元素数量大于 12 个时使用的排序算法，其中 L8 ～ L17 为快速排序逻辑，并且在每次迭代后使 maxDepth（快速排序最大迭代深度） 减 1，直到 maxDepth 为 0 后使用堆排序。

在 L19 ～ L28 中定义了元素数量小于等于 12 时使用的排序算法，在 L22 ～ L26 先进行一轮 gap（间隔）为 6 的 shellSort（希尔排序），紧接着执行 insertionSort（插入排序）。

  1. func quickSort(data Interface, a, b, maxDepth int) {
  2.     for b-a > 12 { // Use ShellSort for slices <= 12 elements
  3.         if maxDepth == 0 {
  4.             heapSort(data, a, b)
  5.             return
  6.         }
  7.         maxDepth--
  8.         mlo, mhi := doPivot(data, a, b)
  9.         // Avoiding recursion on the larger subproblem guarantees
  10.         // a stack depth of at most lg(b-a).
  11.         if mlo-a < b-mhi {
  12.             quickSort(data, a, mlo, maxDepth)
  13.             a = mhi // i.e., quickSort(data, mhi, b)
  14.         } else {
  15.             quickSort(data, mhi, b, maxDepth)
  16.             b = mlo // i.e., quickSort(data, a, mlo)
  17.         }
  18.     }
  19.     if b-a > 1 {
  20.         // Do ShellSort pass with gap 6
  21.         // It could be written in this simplified form cause b-a <= 12
  22.         for i := a + 6; i < b; i++ {
  23.             if data.Less(i, i-6) {
  24.                 data.Swap(i, i-6)
  25.             }
  26.         }
  27.         insertionSort(data, a, b)
  28.     }
  29. }

下图为整个 Sort 方法的大体流程，可能对于初学者来说并不了解以上提到的几种排序方法，以及快速排序的 maxDepth 还有希尔排序的 gap，不过没关系，让我们从简到难一一梳理各个排序算法，最后再回头看 Sort 方法其实并没有那么复杂。
图片.png

InsertionSort && ShellSort

我们首先来看 insertionSort （插入排序），插入排序的核心思想是把第 n + 1 项在已经排好序的前 n 项中找位置插入，我们来看下图。

图片.png
从上图可以看出，insertionSort 的具体做法是先把第 n + 1 个元素保存为一个 key 值然后依次与前 n 个元素比较，如果比 key 大则向前移一位，如果比 key 小则把 key 插入上一个位置，然后进行下一轮比较，以下是 Go 中 insertionSort 的实现。

  1. // insertionSort sorts data[a:b] using insertion sort.
  2. func insertionSort(data Interface, a, b int) {
  3.     for i := a + 1; i < b; i++ {
  4.         for j := i; j > a && data.Less(j, j-1); j-- {
  5.             data.Swap(j, j-1)
  6.         }
  7.     }
  8. }

接下来是 shellSort（希尔排序），如果理解了插入排序，那么只需要知道 shellSort 是 insertionSort 的变种就可以了，insertionSort 的 gap（元素比较的间隔）永远是 1，即每次与前 1 项比较，而 shellSort 的 gap 则是动态变化的，关于 gap 变化的规则，我们一般取 n/2 然后每次循环之后再除 2，当然面对不同的数据，还有更高效的方法，有兴趣的朋友可以自己去了解一下，而Go 中的实现稍有不同，我们先看图和源码。

图片.png

  1. if b-a > 1 {
  2.     // Do ShellSort pass with gap 6
  3.     // It could be written in this simplified form cause b-a <= 12
  4.     for i := a + 6; i < b; i++ {
  5.         if data.Less(i, i-6) {
  6.             data.Swap(i, i-6)
  7.         }
  8.     }
  9.     insertionSort(data, a, b)
  10. }

从上图可以看出，shellSort 的 gap 最终也会等于 1，此时与插入排序无异, Go 中规定只要元素数量小于等于 12，那么初始 gap 固定取 6，并且只进行一轮 shellSort 然后进行 insertionSort，但是为什么要这么做呢？我们来做几组测试。

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. type Interface interface {
  8.     Len() int
  9.     Less(i, j int, cnt *int) bool
  10.     Swap(i, j int, cnt *int)
  11. }
  13. type IntSlice []int
  15. func (x IntSlice) Len() int {
  16.     return len(x)
  17. }
  19. func (x IntSlice) Less(i, j int, cnt *int) bool {
  20.     *cnt++
  21.     return x[i] < x[j]
  22. }
  24. func (x IntSlice) Swap(i, j int, cnt *int) {
  25.     *cnt++
  26.     x[i], x[j] = x[j], x[i]
  27. }
  29. func realityShellSort(data Interface, a, b int) {
  30.     cmpCnt := 0
  31.     swapCnt := 0
  32.     n := data.Len()
  34.     if n < 2 {
  35.         return
  36.     }
  38.     gap := n / 2
  39.     for gap > 0 {
  40.         for i := gap; i < n; i++ {
  41.             j := i
  42.             for j >= gap && data.Less(j, j-gap, &cmpCnt) {
  43.                 data.Swap(j, j-gap, &swapCnt)
  44.                 j = j - gap
  45.             }
  46.         }
  47.         gap = gap / 2
  48.     }
  50.     fmt.Printf("realityShellSort cmpCnt: %d, swapCnt: %d\n", cmpCnt, swapCnt)
  51. }
  53. func shellSort(data Interface, a, b int) {
  54.     cmpCnt := 0
  55.     swapCnt := 0
  57.     for i := a + 6; i < b; i++ {
  58.         if data.Less(i, i-6, &cmpCnt) {
  59.             data.Swap(i, i-6, &swapCnt)
  60.         }
  61.     }
  63.     fmt.Printf("shellSort cmpCnt: %d, swapCnt: %d\n", cmpCnt, swapCnt)
  64. }
  66. func insertionSort(data Interface, a, b int) {
  67.     cmpCnt := 0
  68.     swapCnt := 0
  70.     for i := a + 1; i < b; i++ {
  71.         for j := i; j > a && data.Less(j, j-1, &cmpCnt); j-- {
  72.             data.Swap(j, j-1, &swapCnt)
  73.         }
  74.     }
  76.     fmt.Printf("insertionSort cmpCnt: %d, swapCnt: %d\n", cmpCnt, swapCnt)
  77. }
  79. func main() {
  80.     random := []int{6, 11, 1, 12, 5, 4, 10, 2, 9, 7, 8, 3}
  81.     desc := []int{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
  82.     partSorted := []int{1, 12, 3, 4, 5, 6, 7, 8, 9, 10, 11, 2}
  84.     fmt.Printf("realityShellSort: \nRandom: \n")
  85.     realityShellSort(IntSlice(random), 0, len(random))
  86.     fmt.Println()
  88.     fmt.Printf("Desc: \n")
  89.     realityShellSort(IntSlice(desc), 0, len(desc))
  90.     fmt.Println()
  92.     fmt.Printf("PartSorted: \n")
  93.     realityShellSort(IntSlice(partSorted), 0, len(partSorted))
  94.     fmt.Println()
  96.     random = []int{6, 11, 1, 12, 5, 4, 10, 2, 9, 7, 8, 3}
  97.     desc = []int{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
  98.     partSorted = []int{1, 12, 3, 4, 5, 6, 7, 8, 9, 10, 11, 2}
  100.     fmt.Printf("\ninsertionSort: \nRandom: \n")
  101.     insertionSort(IntSlice(random), 0, len(random))
  102.     fmt.Println()
  104.     fmt.Printf("Desc: \n")
  105.     insertionSort(IntSlice(desc), 0, len(desc))
  106.     fmt.Println()
  108.     fmt.Printf("PartSorted: \n")
  109.     insertionSort(IntSlice(partSorted), 0, len(partSorted))
  110.     fmt.Println()
  112.     random = []int{6, 11, 1, 12, 5, 4, 10, 2, 9, 7, 8, 3}
  113.     desc = []int{12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
  114.     partSorted = []int{1, 12, 3, 4, 5, 6, 7, 8, 9, 10, 11, 2}
  116.     fmt.Printf("\nshellSort && insertionSort: \nRandom: \n")
  117.     shellSort(IntSlice(random), 0, len(random))
  118.     insertionSort(IntSlice(random), 0, len(random))
  119.     fmt.Println()
  121.     fmt.Printf("Desc: \n")
  122.     shellSort(IntSlice(desc), 0, len(desc))
  123.     insertionSort(IntSlice(desc), 0, len(desc))
  124.     fmt.Println()
  126.     fmt.Printf("PartSorted: \n")
  127.     shellSort(IntSlice(partSorted), 0, len(partSorted))
  128.     insertionSort(IntSlice(partSorted), 0, len(partSorted))
  129. }
  131. //             realityShellSort: 
  132. //             Random: 
  133. // L85:     realityShellSort cmpCnt: 44, swapCnt: 23
  134. // 
  135. //             Desc: 
  136. // L89:        realityShellSort cmpCnt: 39, swapCnt: 24
  137. // 
  138. //             PartSorted: 
  139. // L93:        realityShellSort cmpCnt: 41, swapCnt: 19
  140. // 
  141. // 
  142. //             insertionSort: 
  143. //             Random: 
  144. // L101:    insertionSort cmpCnt: 47, swapCnt: 37
  145. // 
  146. //             Desc: 
  147. // L105:    insertionSort cmpCnt: 66, swapCnt: 66
  148. // 
  149. //             PartSorted: 
  150. // L109:    insertionSort cmpCnt: 30, swapCnt: 19
  151. // 
  152. // 
  153. //             shellSort && insertionSort: 
  154. //             Random: 
  155. // L119:    shellSort cmpCnt: 6, swapCnt: 3
  156. // L118:    insertionSort cmpCnt: 31, swapCnt: 22
  157. // 
  158. //             Desc: 
  159. // L122:    shellSort cmpCnt: 6, swapCnt: 6
  160. // L123:    insertionSort cmpCnt: 36, swapCnt: 30
  161. // 
  162. //             PartSorted: 
  163. // L127:    shellSort cmpCnt: 6, swapCnt: 2
  164. // L128:    insertionSort cmpCnt: 28, swapCnt: 17

以上为测试用例，我们使用单独的 shellSort、insertionSort 以及 Go 中 shell 与 insertion 混用的排序方法对随机分布、倒序、相对有序三种不同的数据进行排序，并且统计比较次数与交换次数，输出结果如上 L131 ～ L164，但是显然不够直观，我们做图观察。下图中，每一组从上到下数据种类依次为随机、倒序、相对有序。

bar-stack.png
首先，我们可以看到 insertionSort 出现了两个极端，在倒序的情况下，比较与交换次数均远远大于另外两种排序方法，而在相对有序的情况下，insertionSort 又是步骤最少的。再观察 shellSort 方法，在面对随机与倒序数据时都优于 iInsertionSort，所以我们就不难理解为什么在 Go 的源码中为什么要先进行一轮 shellSort 再进行 insertionSort 了，首先进行 shellSort 把数据处理为相对有序的状态，此时 insertionSort 效率最高，所以使用 insertionSort 完成排序。

本周的内容，对 sort 包中部分排序逻辑进行了讲解，如这部分内容对初学者比较友好，果不明白的话可以尝试自己画图或者用编写测试代码的方式来辅助理解，由于篇幅原因，关于 quickSort 和 heapSort 的内容我们下周再继续进行讲解。