【博客大赛】浅析go切片与排序
切片是Go语言中引入的用于在大多数场合替代数组的语法元素。切片是一种长度可变的同类型元素序列，它原则上不支持存储不同类型的元素，当然了作为打工人是非常清楚“原则上”的潜台词就是“某种情况下允许” special := []interface{}{“hello go”, 2021, 4.15} 这种允许的情况有机会我们另外讨论，这个不是本次的讨论范围，本文就事论事，还不至于深入到原理。 正所谓有序列的地方就有排序的需求。在各种排序算法都已经成熟的今天，我们完全可以针对特定元素类型的切片手写排序函数/方法，但多数情况下不推荐这么做，因为Go标准库内置了sort包可以很好地帮助我们实现原生类型元素切片以及自定义类型元素切片的排序任务，但话又说回来，工程项目中我们大概率都是拿来主义的，也只有是在平常刷题练习中才会自己考虑实现相关的算法。 对于sort Go 的排序思路和 C 和 C++ 有些差别。 C 默认是对数组进行排序， C++ 是对一个序列进行排序， Go 则更宽泛一些，待排序的可以是任何对象， 虽然很多情况下是一个slice (分片, 类似于数组)，或是包含 slice 的一个对象。 这个包实现了四种基本排序算法：插入排序、归并排序、堆排序和快速排序。但是这四种排序方法是不公开的，它们只被用于sort 包内部使用。因此在对数据集合排序时不必考虑应当选择哪一种排序方法，只要实现了 sort.Interface 定义的三个方法： 获取数据集合长度的Len() 方法 比较两个元素大小的Less() 方法 交换两个元素位置的Swap()方法 完成之后可以顺利对数据集合进行排序【无时不刻在等待泛型的出现啊，重复写真的烦:)】 sort 包会根据实际数据自动选择高效的排序算法。 除此之外，为了方便对常用数据类型的操作，sort 包提供了对[]int切片、[]float64 切片和[]string 切片完整支持，主要包括： 对基本数据类型切片的排序支持 基本数据元素查找 判断基本数据类型切片是否已经排好序 对排好序的数据集合逆序 数据集合排序 前面已经提到过，对数据集合（包括自定义数据类型的集合）排序需要实现 sort.Interface 接口的三个方法，我们看以下该接口的定义： type Interface interface { // 获取数据集合元素个数 Len() int // 如果 i 索引的数据小于 j 索引的数据，返回 true，且不会调用下面的 Swap()，即数据升序排序。 Less(i, j int) bool // 交换 i 和 j 索引的两个元素的位置 Swap(i, j int) } 数据集合实现了这三个方法后，即可调用该包的Sort() 方法进行排序。Sort() 方法定义如下： func Sort(data Interface) Sort() 方法使用的惟一参数就是待排序的数据集合。 此外该包还提供了一个方法可以判断数据集合是否已经排好顺序，毕竟方法的内部实现依赖于我们自己实现的 Len() 和 Less() 方法： func IsSorted(data Interface) bool { n := data.Len() for i := n - 1; i > 0; i-- { if data.Less(i, i-1) { return false } } return true } 最后一个方法：Search() func Search(n int, f func(int) bool) int 该方法会使用“二分查找”算法来找出能使f(x)(0<=x<n) 返回 ture 的最小值 i。 前提条件 : f(x)(0<=x<i) 均返回false,f(x)(i<=x<n) 均返回ture。 如果不存在 i 可以使 f(i) 返回 ture, 则返回 n。 Search() 函数一个常用的使用方式是搜索元素 x 是否在已经升序排好的切片 s 中： x := 11 s := []int{3, 6, 8, 11, 45} // 注意已经升序排序 pos := sort.Search(len(s), func(i int) bool { return s[i] >= x }) if pos < len(s) && s[pos] == x { fmt.Println(x, " 在 s 中的位置为：", pos) } else { fmt.Println("s 不包含元素 ", x) } 排序原理 截至目前Go 1.15版本，Go还不支持泛型。因此，为了支持任意元素类型的切片的排序，标准库sort包定义了一个Interface接口和一个接受该接口类型参数的Sort函数： type Interface interface { Len() int Less(i, j int) bool Swap(i, j int) } func Sort(data Interface) { n := data.Len() quickSort(data, 0, n, maxDepth(n)) } 为了应用这个排序函数Sort，我们需要让被排序的切片类型实现sort.Interface接口，以整型切片为例 type IntSlice []int func (p IntSlice) Len() int { return len(p) } func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] } func (p IntSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } func main() { sl := IntSlice([]int{89, 14, 8, 9, 17, 56, 95, 3}) fmt.Println(sl) // [89 14 8 9 17 56 95 3] sort.Sort(sl) fmt.Println(sl) // [3 8 9 14 17 56 89 95] } 从sort.Sort函数的实现来看，它使用的是快速排序quickSort。我们知道快速排序是在所有数量级为O(nlogn)的排序算法中其平均性能最好的算法，但在某些情况下其性能却并非最佳，Go sort包中的quickSort函数也没有严格拘泥于仅使用快排算法，而是以快速排序为主，并根据目标状况在特殊条件下选择了其他不同的排序算法，包括堆排序(heapSort)、插入排序(insertionSort)等。 sort.Sort函数不保证排序是稳定的，要想使用稳定排序，需要使用sort.Stable函数。 sort包的“语法糖”排序函数 我们看到，直接使用sort.Sort函数对切片进行排序是比较繁琐的。如果仅仅排序一个原生的整型切片都这么繁琐(要实现三个方法），那么sort包是会被喷惨的。还好，对于以常见原生类型为元素的切片，sort包提供了类“语法糖”的简化函数，比如：sort.Ints、sort.Float64s和sort.Strings等。上述整型切片的排序代码可以直接改造成下面这个样子： func main() { sl := []int{89, 14, 8, 9, 17, 56, 95, 3} fmt.Println(sl) // [89 14 8 9 17 56 95 3] sort.Ints(sl) fmt.Println(sl) // [3 8 9 14 17 56 89 95] } 原生类型有“语法糖”可用了，那么对于自定义类型作为元素的切片，是不是每次都得实现Interface接口的三个方法呢？Go团队也想到了这个问题! 所以在Go 1.8版本中加入了sort.Slice函数，我们只需传入一个比较函数实现即可： type Lang struct { Name string Rank int } func main() { langs := []Lang{ {"rust", 2}, {"go", 1}, {"swift", 3}, } sort.Slice(langs, func(i, j int) bool { return langs[i].Rank < langs[j].Rank }) fmt.Printf("%v\n", langs) // [{go 1} {rust 2} {swift 3}] } 同理，如果要进行稳定排序，则用sort.SliceStable替换上面的sort.Slice。 总结 本文主要是通过对go中切片的分析，由于go中的排序不同于c、c++、python这些语言的排序习惯，又由于其不支持泛型，且正处于野蛮生长期，我们在学习应用的过程中，也难得的可以体验其发育带来痛苦，正因为没有体会相同的痛苦，就不能感同身受，成熟的语言如java、python用多了，一直用别人的轮子，实在体会不到轮子内部的精妙之处，我们在学习的过程中可以自己实现相关的排序算法，见证社区的发展，反而可以一步步推演内核的进化，进而触类旁通猜测其他语言的设计思想，不胜荣幸。 参考资料 https://books.studygolang.com/The-Golang-Standard-Library-by-Example/chapter03/03.1.html https://golang.org/pkg/sort/ https://tonybai.com/2020/11/26/slice-sort-in-go/ https://itimetraveler.github.io/2016/09/07/%E3%80%90Go%E8%AF%AD%E8%A8%80%E3%80%91%E5%9F%BA%E6%9C%AC%E7%B1%BB%E5%9E%8B%E6%8E%92%E5%BA%8F%E5%92%8C%20slice%20%E6%8E%92%E5%BA%8F/
