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包/ 到此这篇关于详解go语言中sort如何排序的文章就介绍到这了,更多相关go语言 sort排序内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！