在Go中如何进行排序
共 3032字，需浏览 7分钟
·
2020-12-17 02:14
排序操作在我们日常开发中是经常干的一件事，一些语言会提供开箱即用的工具，比如在 PHP 中关于数组对应的 sort 函数。当然在 Go 中也有对应的实现方式。
介绍与使用
Go 中有一个 sort 内置包，里面提供了一些排序函数用来对任何序列进行排序操作。对于基础的类型，直接提供了对应的排序函数，比如下面展示的几种类型的切片。
package mainimport ("fmt""sort")func main() {numbers := []int{18, 8, 28, 38}sort.Ints(numbers)fmt.Printf("int sort:%v\n", numbers)amounts := []float64{10, 1, 8.88, 2, 6}sort.Float64s(amounts)fmt.Printf("float64 sort:%v\n", amounts)strings := []string{"h", "e", "l", "l", "o"}sort.Strings(strings)fmt.Printf("string sort:%v\n", strings)}
执行这段代码，可以看到各类型的切片已然有序。
当然，不仅仅是切片，我们可以通过 sort.Sort() 和 sort.Stable() 排序任意数据结构。两者最大的区别在于 sort.Sort() 不是稳定排序，而 sort.Stable() 是稳定排序。稳定排序意味着对于相同的元素，能保证他们排序后和排序前的顺序保持一致。
什么情况下可以调用这两个函数？
只要是实现了 sort.Interface 接口的任意类型都可以使用这两个函数进行排序操作，至于原因，待会再解释为什么。我们先来看 sort.Interface 接口。
主要包含三个方法。获取结构的长度 Len()，元素比较返回的布尔值 Less() 以及交换两个元素 Swap()，现在让我们来实现它。
package mainimport ("fmt""sort")type UserInfo struct {Age intName string}type Users []UserInfofunc (users Users) Len() int { return len(users) }func (users Users) Less(i, j int) bool { //正序return users[i].Age < users[j].Age}func (users Users) Swap(i, j int) {users[i], users[j] = users[j], users[i]}func main() {userAll := []UserInfo{{20, "curry"},{18, "wuqinqiang"},{27, "张三"},{10, "李四"},{25, "王武"},}sort.Sort(Users(userAll))fmt.Println(userAll)}
我们定义了一个 UserInfo 的结构体，Users 是一个 UserInfo 结构的切片。(注意：我们这里使用的是切片，但是不要把思维限制在切片上， 可以是实现了sort.Interface 接口的任意类型)。这里 Users 实现方法 Less() 是通过对 age 的大小来实现正序排序。根据元素的比较结果然后使用 Swap() 来实现元素间的互换。
users[i], users[j] = users[j], users[i]元素间的互换可以通过以上的操作来进行，这是 Go 的一些特性。当然有些其他语言也支持。如果使用的是“世界上最好的语言”的话，那么要实现两元素之间的互换，多数人会利用第三方变量，比如:
$a=1;$b=2;$temp=$a;$a=$b;$b=$temp;
有那味道了......。
以上介绍了Go 中 sort 包的一些使用姿势。现在我们开始稍微深入一点点了解一下底层原理。
了解运行原理
我们先进入 sort.Sort() 方法。
// 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) {n := data.Len()quickSort(data, 0, n, maxDepth(n))}
可以看到，首先会调用已经实现的 Len() 计算长度。然后调用了一个 quickSort() (快速排序)的方法，在进入这个方法之前，我们先看看 maxDepth(n) 函数是啥。
// maxDepth returns a threshold at which quicksort should switch// to heapsort. It returns 2*ceil(lg(n+1)).func maxDepth(n int) int { var depth intfor i := n; i > 0; i >>= 1 {depth++}return depth * 2}
从上面的解释来看，此函数返回一个整形阀值，通过这个值来决定是选择快排还是堆排。
这段代码看起来有点蒙，要分成两段来看:上面主要计算构建完全二叉树的深度，最后 *2 的意思是返回最深的完全二叉树的深度。大佬的思路果然还是跟不上，emmm......
再回头看 quickSort() 函数
func quickSort(data Interface, a, b, maxDepth int) {for b-a > 12 { // Use ShellSort for slices <= 12 elementsif 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 <= 12for i := a + 6; i < b; i++ {if data.Less(i, i-6) {data.Swap(i, i-6)}}insertionSort(data, a, b)}}
单看这段代码还是好理解的，如果要比较的元素长度大于 12，那么就在堆排序和快速排序之间做选择。否则的话，就使用希尔排序和插入排序，可以看到希尔排序的间隔为 6。
这个快速排序方法中调用了 Swap() 和 Less() 方法，现在，再回头看之前的 Less()，比较的规则是由你来决定的, sort.Sort() 会根据你定义的比较规则加上当前的数量级来选择相对应的算法进行规则排序。
这里还有一段代码
func quickSort(data Interface, a, b, maxDepth int) {// .........................................................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)}// ....................}
实现快排的方式是递归，在获取分区点的时候返回的是两个值(多返回值是 Go 的特性)。但是代码中，在返回分区点之后，并没有进行左右分区的递归查找，而是根据比较的结果，把数量多的一方放到下次循环中继续切割，小的直接递归。
因为实现的是递归，需要考虑到栈溢出的问题，这里也标明调用 quickSort() 的最高栈深度为 log(b-a)，即 log(n)。
剩下的关于获取分区点 doPivot() 方法的实现，感兴趣的可以自己手摸手看。
再看搜索
既然已经实现了排序，那么排序后咋么获取指定元素所处的位置? sort 包还提供了 Search 方法。下面是实现:
func main() {userAll := []UserInfo{{20, "curry"},{18, "wuqinqiang"},{18, "测试2"},{27, "张三"},{10, "李四"},{25, "王武"},}sort.Sort(Users(userAll))temp:=18//搜索index := sort.Search(len(userAll), func(i int) bool {return userAll[i].Age >= temp})//判断元素是否存在if index < len(userAll) && userAll[index].Age == temp {fmt.Printf("元素:%d处于索引:%d处\n",temp,index)}else{fmt.Printf("元素:%d不存在\n",temp)}}
我们可以进入 sort.Search() 查看，好吧，本质上就是一个二分查找。
func Search(n int, f func(int) bool) int {// Define f(-1) == false and f(n) == true.// Invariant: f(i-1) == false, f(j) == true.i, j := 0, nfor i < j {//获取中位数h := int(uint(i+j) >> 1) // avoid overflow when computing h// i ≤ h < j//这里的f 就是执行我们传进来的//func(i int) bool {// return userAll[i].Age >= temp// }if !f(h) {i = h + 1 // preserves f(i-1) == false} else {j = h // preserves f(j) == true}}// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.return i}
照着这里的逻辑，我们之前 age=18 ，返回的是索引 1，假设我想返回的是相同值的最后一个索引处(对标 LeetCode34)，那么可以自己实现一个自定义的二分查找:
userAll := []UserInfo{{20, "curry"},{18, "wuqinqiang"},{18, "测试2"},{18, "测试3"},{18, "测试4"},{18, "测试5"},{18, "测试6"},{27, "张三"},{10, "李四"},{25, "王武"},}sort.Sort(Users(userAll))temp:=18index := SearchLast(len(userAll)-1, func(i int) bool {return userAll[i].Age <= temp})if index < len(userAll) && userAll[index].Age == temp {fmt.Printf("元素:%d处于索引:%d处\n",temp,index)}else{fmt.Printf("元素:%d不存在\n",temp)}}func SearchLast(n int, f func(int) bool) int {i, j := 0, nlast := -1for i <= j {h := int(uint(i+j) >> 1) // avoid overflow when computing hif f(h) {last, i = h, h+1} else {j = h - 1}}return last}
这篇文章到这里也就结束了，介绍了 sort 包一小部分的东西，还有很多东西我并未提到，一个是自己也还没去用，另一个是有些东西，自己去发现更有乐趣。共勉。
推荐阅读