sort 包源码解读
前言
我们的代码业务中很多地方需要我们自己进行排序操作，go 标准库中是提供了 sort 包是实现排序功能的，这里来看下生产级别的排序功能是如何实现的。
go version go1.16.13 darwin/amd64
如何使用
先来看下 sort 提供的主要功能
- 对基本数据类型切片的排序支持
- 自定义 Less 排序比较器
- 自定义数据结构的排序
- 判断基本数据类型切片是否已经排好序
- 基本数据元素查找
基本数据类型切片的排序
sort 包中已经实现了对 []int, []float, []string 这几种类型的排序
看下输出
是否排好序了 false
[1 2 3 4 5 6]
[6 5 4 3 2 1]
是否排好序了 true
查找是否存在 4
[1 2 3 4 5 6]
[a c d f r s]
[0.11 1.33 4.22 4.78 6.77 8.99]
sort 本身不是稳定排序，需要稳定排序使用sort.Stable，同时排序默认是升序，降序可使用sort.Reverse
自定义 Less 排序比较器
如果我们需要进行的排序的内容是一些复杂的结构，例如下面的栗子，是个结构体，根据结构体中的某一个属性进行排序，这时候可以通过自定义 Less 比较器实现
使用 sort.Slice，sort.Slice中提供了 less 函数，我们，可以自定义这个函数，然后通过sort.Slice进行排序，sort.Slice不是稳定排序，稳定排序可使用sort.SliceStable
看下输出
[{Michael 17} {Jenny 26} {Bob 31} {John 42}]
[{John 42} {Bob 31} {Jenny 26} {Michael 17}]
[{John 42} {Bob 31} {Jenny 26} {Michael 17}]
自定义数据结构的排序
对自定义结构的排序，除了可以自定义 Less 排序比较器之外，sort 包中也提供了sort.Interface接口，我们只要实现了sort.Interface中提供的三个方法，即可通过 sort 包内的函数完成排序，查找等操作
来看下如何使用
输出
[{Michael 17} {Jenny 26} {Bob 31} {John 42}]
当然 sort 包中已经实现的[]int, []float, []string 这几种类型的排序也是实现了sort.Interface接口
对于上面的三种排序，第一种和第二种基本上就能满足我们的额需求了，不过第三种灵活性更强。
分析下源码
先来看下什么是稳定性排序
栗如：对一个数组进行排序，如果里面有重复的数据，排完序时候，相同的数据的相对索引位置没有发生改变，那么就是稳定排序。
也就是里面有两个5，5。排完之后第一个5还在最前面，没有和后面的重复数据5发生过位置的互换，那么这就是稳定排序。
不稳定排序
sort 中的排序算法用到了，quickSort(快排),heapSort(堆排序),insertionSort(插入排序),shellSort(希尔排序)
先来分析下这几种排序算法的使用
可以看下调用 Sort 进行排序，最终都会调用 quickSort
再来看下 quickSort 的实现
对于这几种排序算法的使用，sort 包中是混合使用的
1、如果切片长度大于12的时候使用快排，使用快排的时候，如果满足了使用堆排序的条件没这个排序对于后面的数据的处理，又会转换成堆排序；
2、切片长度小于12了，就使用 shell 排序，shell 排序只处理一轮数据，后面数据的排序使用插入排序；
堆排序和插入排序就是正常的排序处理了
稳定排序
sort 包中也提供了稳定的排序，通过调用sort.Stable来实现
对于稳定排序，用到了插入排序和归并排序
1、首先会将数据按照每20个一组进行分块，对每个块中的数据使用插入排序完成排序；
2、然后下面使用归并排序，对排序的数据块进行两两归并排序，完成一次排序，扩大数据块为之前的2倍，直到完成所有的排序。
查找
sort 中的 查找功能最终是调用 search 函数来实现的
sort 中查找相对比较简单，使用的是二分查找
Interface
sort 包提供了 Interface 的接口，我们可以自定义数据结构，然后实现 Interface 对应的接口，就能使用 sort 包中的方法
看源码可以看到 sort 包中已有的对 []int 等数据结构的排序，也是实现了 Interface
这种思路挺好的，之后可以借鉴下，对于可变部分提供抽象接口，让用户根据自己的场景有实现。
对于基础的排序，查找只要实现了 Interface 的方法，就能拥有这些基础的能力了。
总结
sort 对于排序算法的实现，是结合了多种算法，最终实现了一个高性能的排序算法
抽象出了 IntSlice 接口，用户可以自己去实现对应的方法，然后就能拥有 sort 中提供的能力了
参考
【文中示例代码】https://github.com/boilingfrog/Go-POINT/blob/master/golang/sort/sort_test.go
【Golang sort 排序】https://blog.csdn.net/K346K346/article/details/118314382
【John Tukey’s median of medians】https://www.johndcook.com/blog/2009/06/23/tukey-median-ninther/
【code_reading】https://github.com/Junedayday/code_reading/blob/master/sort/sort.go
【go中的sort包】https://boilingfrog.github.io/2022/03/06/go中的sort包/