切片是Go语言中引入的用于在大多数场合替代数组的语法元素。切片是一种长度可变的同类型元素序列，它原则上不支持存储不一样类型的元素，固然了做为打工人是很是清楚“原则上”的潜台词就是“某种状况下容许”html
special := []interface{}{“hello go”, 2021, 4.15}
这种容许的状况有机会咱们另外讨论，这个不是本次的讨论范围，本文就事论事，还不至于深刻到原理。java
正所谓有序列的地方就有排序的需求。在各类排序算法都已经成熟的今天，咱们彻底能够针对特定元素类型的切片手写排序函数/方法，但多数状况下不推荐这么作，由于Go标准库内置了sort包能够很好地帮助咱们实现原生类型元素切片以及自定义类型元素切片的排序任务，但话又说回来，工程项目中咱们大几率都是拿来主义的，也只有是在日常刷题练习中才会本身考虑实现相关的算法。python
Go 的排序思路和 C 和 C++ 有些差异。 C 默认是对数组进行排序， C++ 是对一个序列进行排序， Go 则更宽泛一些，待排序的能够是任何对象， 虽然不少状况下是一个slice (分片, 相似于数组)，或是包含 slice 的一个对象。c++
这个包实现了四种基本排序算法：插入排序、归并排序、堆排序和快速排序。可是这四种排序方法是不公开的，它们只被用于sort 包内部使用。所以在对数据集合排序时没必要考虑应当选择哪种排序方法，只要实现了 sort.Interface 定义的三个方法：git
Len() 方法Less() 方法Swap()方法完成以后能够顺利对数据集合进行排序【无时不刻在等待泛型的出现啊，重复写真的烦:)】github
sort 包会根据实际数据自动选择高效的排序算法。 除此以外，为了方便对经常使用数据类型的操做，sort 包提供了对[]int切片、[]float64 切片和[]string 切片完整支持，主要包括：golang
前面已经提到过，对数据集合（包括自定义数据类型的集合）排序须要实现 sort.Interface 接口的三个方法，咱们看如下该接口的定义：算法
type Interface interface {
// 获取数据集合元素个数
Len() int
// 若是 i 索引的数据小于 j 索引的数据，返回 true，且不会调用下面的 Swap()，即数据升序排序。
Less(i, j int) bool
// 交换 i 和 j 索引的两个元素的位置
Swap(i, j int)
}
数据集合实现了这三个方法后，便可调用该包的Sort() 方法进行排序。Sort() 方法定义以下：swift
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.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用多了，一直用别人的轮子，实在体会不到轮子内部的精妙之处，咱们在学习的过程当中能够本身实现相关的排序算法，见证社区的发展，反而能够一步步推演内核的进化，进而举一反三猜想其余语言的设计思想，不胜荣幸。