Go Sort
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 的排序算法会根据结果集的大小选择相对优秀的排序算法完成排序。
总结
本文我们主要介绍了 Go 语言 sort 包中排序和查询相关方法的使用，以及 sort.go 源码的逻辑剖析。如果大家对文章内容有任何疑问或建议，欢迎私信交流。
我把Go语言基础知识相关文章的Demo都放到了下面这个仓库中，方便大家互相交流学习。https://gitee.com/jialj/golang-learn (之前的 github 账号被封了，换到了gitee)
相关链接
https://golang.google.cn/pkg/sort/
https://www.johndcook.com/blog/2009/06/23/tukey-median-ninther/
https://learnku.com/articles/30404