Go Sort

发表于 2年以前 | 总阅读数：470 次

Hi，今天和大家一起学习 Go 语言的包：sort。

sort 包中主要包含了排序和搜索的方法。

排序方法

Ints、Float64s、Strings

sort 包中定义了常见类型的排序方法：

func Ints(x []int)    // 对 int 类型的切片排序
func Float64s(x []float64)    // 对 float64 类型的切片排序
func Strings(x []string)    // 对 string 类型的切片排序

以Ints为例,我们要排序一个 int 类型的数组，代码如下：

arr := []int{1, 6, 3, 1}
sort.Ints(arr)
fmt.Println(arr) // [1 1 3 6]

Float64s 和 Strings 的使用方法与 Ints 相同。

默认的排序方法只支持递增排序。

其它类型

如果不属于 int、float64、string 三种类型的切片，可以使用 Sort 方法排序。

Sort 方法接收 sort.Interface 接口类型的参数。sort.Interface 定义了三个方法：

type Interface interface {
        // 获取集合中元素的长度
 Len() int
        // 下标i、j位置的元素是否要互换位置。
 Less(i, j int) bool
        // 交换下标i、j位置的元素。
 Swap(i, j int)
}

一个具体的例子：

import (
 "fmt"
 "sort"
)

//Student 学生，包含姓名和学号两个字段
type Student struct {
 name   string
 number int
}

//StudentByNumber 按照学生的学号排序
type StudentByNumber []Student

//Len 返回学生人数
func (s StudentByNumber) Len() int {
 return len(s)
}

//Less 比较下标为i、j的元素是否需要交换位置
func (s StudentByNumber) Less(i, j int) bool {
 return s[i].number < s[j].number
}

//Swap 交换下标i、j元素的位置
func (s StudentByNumber) Swap(i, j int) {
 s[i], s[j] = s[j], s[i]
}

func main() {
 arr := []Student{
  {name: "Tom", number: 002},
  {name: "Jerry", number: 006},
  {name: "Bob", number: 001},
  {name: "Albert", number: 004},
 }
 sort.Sort(StudentByNumber(arr))
 fmt.Println(arr) // [{Bob 1} {Tom 2} {Albert 4} {Jerry 6}]
}

逆序

通过 sort.Reverse 实现逆序。接着上面的例子，加入下两行代码把 arr 逆序：

sort.Sort(sort.Reverse(StudentByNumber(arr)))
fmt.Println(arr) // [{Jerry 6} {Albert 4} {Tom 2} {Bob 1}]

看源码得知，调用 Reverse 方法时，会调用实现类型的 Less 方法，通过互换i和j的位置达到逆序的效果。

// Less returns the opposite of the embedded implementation's Less method.
func (r reverse) Less(i, j int) bool {
 return r.Interface.Less(j, i)
}

我个人感觉 Reverse 方法的实现使用起来不够“显而易见”，需要使用者摸索一下；但是也很好的复用了 Less 方法。

IntSlice、Float64Slice、StringSlice

sort 包中，除了对外提供Ints、Float64s、Strings方法外，还对外提供了对应的三种类型 IntSlice、Float64Slice、StringSlice。

这三种类型都分别实现了 sort.Interface 接口。

其实Ints、Float64s、Strings方法都是对传入参数类型进行了强制转换：

// Ints sorts a slice of ints in increasing order.
func Ints(x []int) { Sort(IntSlice(x)) }

当我们调用 Reverse 方法时，可以使用上面的三种类型：

sort.Sort(sort.Reverse(IntSlice(arr)))

Stable 方法

Sort 使用的是不稳定的排序算法，如果希望使用稳定的排序算法，需要调用 Stable 方法。

简单理解稳定的排序算法：对于两个相等的值，排序前后的相对位置相同，这样的排序算法称为稳定的排序算法。

Stable 的使用方式和 Sort 方法相同，就不再举例了。

Search 方法

Search 方法的作用是完成二分查找。

func Search(n int, f func(int) bool) int

Search 方法接收两个参数:n int, f func(int) bool，n代表二分查找会从[0,n)开始。f方法返回值为true时，代表找到了满足条件的元素，Search函数返回此时的索引。当有多个相同元素时，返回最左侧元素的索引。当没有找到对应元素时，返回 n。

e.g

import (
 "fmt"
 "sort"
)

func main() {

 a := []int{1, 3, 6, 6, 15, 21, 28, 36, 45, 55}

 i := sort.Search(len(a), func(i int) bool { return a[i] >= 6 })
 fmt.Println("i=", i) // i= 2 返回第一个匹配的元素下标

 j := sort.Search(len(a), func(i int) bool { return a[i] >= 100 })
 fmt.Println("j=", j) // j= 10 没有找到匹配元素
}

sort 包还提供了另外三个Search开头的方法：SearchFloat64s、SearchInts、SearchStrings。

func SearchInts(a []int, x int) int

以 SearchInts 为例，SearchInts接受参数 a []int, x int，在切片a中查找元素值为x的元素，当有多个相同元素时，返回最左侧元素的索引。当没有找到对应元素时，返回切片a的长度。不过调用此方法有个前提条件 a 必须是有序的。

源码分析

sort 包中排序的逻辑在 sort.go 文件中，查找逻辑在 search.go 文件中。我们主要分析 sort.go 文件的源码。

sort.go 文件中首先定义了 Interface：

// An implementation of Interface can be sorted by the routines in this package.
// The methods refer to elements of the underlying collection by integer index.
type Interface interface {
 // Len is the number of elements in the collection.
 Len() int

 // Less reports whether the element with index i
 // must sort before the element with index j.
 //
 // If both Less(i, j) and Less(j, i) are false,
 // then the elements at index i and j are considered equal.
 // Sort may place equal elements in any order in the final result,
 // while Stable preserves the original input order of equal elements.
 //
 // Less must describe a transitive ordering:
 //  - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
 //  - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
 //
 // Note that floating-point comparison (the < operator on float32 or float64 values)
 // is not a transitive ordering when not-a-number (NaN) values are involved.
 // See Float64Slice.Less for a correct implementation for floating-point values.
 Less(i, j int) bool

 // Swap swaps the elements with indexes i and j.
 Swap(i, j int)
}

所有需要排序的切片元素都需要实现此接口的三个方法。

Sort 方法

接着我们从 Sort(data Interface)方法开始梳理：

// Sort sorts data in ascending order as determined by the Less method.
// 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))
}

Sort 方法调用了 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)
 }
}

通过代码可以到，当元素个数大于12和小于12时，分别采用了不同的排序算法。

「大于12时」：如果 maxDepth参数递减为0，调用 heapSort(data, a, b)采用堆排序，在maxDepth大于零时，调用doPivot(data, a, b)方法，然后根据 mlo-a < b-mhi决定对长度较小的一段递归调用 quickSort。在maxDepth递减为0时，表示快速排序递归了很多轮还没有出结果，遇到了比较坏的情况，此时采用堆排序更高效。

doPivot(data, a, b)方法实现了快速排序的核心逻辑：

func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
 m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
 if hi-lo > 40 {
  // Tukey's ``Ninther,'' median of three medians of three.
  s := (hi - lo) / 8
  medianOfThree(data, lo, lo+s, lo+2*s)
  medianOfThree(data, m, m-s, m+s)
  medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
 }
 medianOfThree(data, lo, m, hi-1)

 // Invariants are:
 // data[lo] = pivot (set up by ChoosePivot)
 // data[lo < i < a] < pivot
 // data[a <= i < b] <= pivot
 // data[b <= i < c] unexamined
 // data[c <= i < hi-1] > pivot
 // data[hi-1] >= pivot
 pivot := lo
 a, c := lo+1, hi-1

 for ; a < c && data.Less(a, pivot); a++ {
 }
 b := a
 for {
  for ; b < c && !data.Less(pivot, b); b++ { // data[b] <= pivot
  }
  for ; b < c && data.Less(pivot, c-1); c-- { // data[c-1] > pivot
  }
  if b >= c {
   break
  }
  // data[b] > pivot; data[c-1] <= pivot
  data.Swap(b, c-1)
  b++
  c--
 }
 // If hi-c<3 then there are duplicates (by property of median of nine).
 // Let's be a bit more conservative, and set border to 5.
 protect := hi-c < 5
 if !protect && hi-c < (hi-lo)/4 {
  // Lets test some points for equality to pivot
  dups := 0
  if !data.Less(pivot, hi-1) { // data[hi-1] = pivot
   data.Swap(c, hi-1)
   c++
   dups++
  }
  if !data.Less(b-1, pivot) { // data[b-1] = pivot
   b--
   dups++
  }
  // m-lo = (hi-lo)/2 > 6
  // b-lo > (hi-lo)*3/4-1 > 8
  // ==> m < b ==> data[m] <= pivot
  if !data.Less(m, pivot) { // data[m] = pivot
   data.Swap(m, b-1)
   b--
   dups++
  }
  // if at least 2 points are equal to pivot, assume skewed distribution
  protect = dups > 1
 }
 if protect {
  // Protect against a lot of duplicates
  // Add invariant:
  // data[a <= i < b] unexamined
  // data[b <= i < c] = pivot
  for {
   for ; a < b && !data.Less(b-1, pivot); b-- { // data[b] == pivot
   }
   for ; a < b && data.Less(a, pivot); a++ { // data[a] < pivot
   }
   if a >= b {
    break
   }
   // data[a] == pivot; data[b-1] < pivot
   data.Swap(a, b-1)
   a++
   b--
  }
 }
 // Swap pivot into middle
 data.Swap(pivot, b-1)
 return b - 1, c
}

在doPivot方法中medianOfThree方法是一种快速寻找中位数办法。

「小于12时」：以 gap 等于6作为增量做希尔排序，最后对data做插入排序。

Stable 方法

func Stable(data Interface) {
 stable(data, data.Len())
}

func stable(data Interface, n int) {
 blockSize := 20 // must be > 0
 a, b := 0, blockSize
 for b <= n {
  insertionSort(data, a, b)
  a = b
  b += blockSize
 }
 insertionSort(data, a, n)

 for blockSize < n {
  a, b = 0, 2*blockSize
  for b <= n {
   symMerge(data, a, a+blockSize, b)
   a = b
   b += 2 * blockSize
  }
  if m := a + blockSize; m < n {
   symMerge(data, a, m, n)
  }
  blockSize *= 2
 }
}

稳定排序的实现比较简单，先以20个为一组进行插入排序，再进行归并排序。

总体来讲 Go 的排序算法会根据结果集的大小选择相对优秀的排序算法完成排序。