Go之sort

一、sort介绍:

Go的pkg提供了一个排序的包sort,用于对slices和用户自定义的类型进行排序操作。原文参考:

Package sort provides primitives for sorting slices and user-defined collections.

https://golang.org/pkg/sort

该包实现了四种基本排序算法:插入排序、归并排序、堆排序和快速排序,但是这四种排序方法是不公开的,它们只被用于 sort 包内部使用。

我们在对数据集合排序时不必考虑应当选择哪一种排序方法,只要实现了 sort.Interface 定义的三个方法,sort 包会根据实际数据自动选择高效的排序算法:

type Interface interface { // Len is the number of elements in the collection. Len() int // 方法1: 获取数据集合长度的 Len() 方法 // Less reports whether the element with // index i should sort before the element with index j. Less(i, j int) bool // 方法2: 比较两个元素大小的 Less() 方法 // Swap swaps the elements with indexes i and j. Swap(i, j int) // 方法3: 和交换两个元素位置的 Swap() 方法}

除此之外,为了方便对常用数据类型的操作,sort 包提供了对[]int 切片、[]float64 切片和[]string 切片完整支持,主要包括下面内容,下面以[]int为例来讲解:(备注:这里的排序是升序)

func Ints(a []int) // 对基本数据类型切片的排序支持

func SearchInts(a []int, x int) int // 基本数据元素查找

func IsSorted(data Interface) bool // 判断基本数据类型切片是否已经排好序

func Reverse(data Interface) Interface // 对排好序的数据集合逆序

二、基本类型int,float64,string的排序

sort实现的是升序操作,对于这三种类型,只需要调用它们的sort方法即可,如果想要进行降序操作,需要主动调用Reverse()方法,例子如下:

package main
import ( "fmt" "sort")
func main() { s1 := []int{-1, 8, 6, 3, 1, 4} // int unsorted sort.Ints(s1) // 升序 fmt.Println(s1) v1 := sort.SearchInts(s1, 6) fmt.Println(v1) sort.Sort(sort.Reverse(sort.IntSlice(s1))) fmt.Println(s1) // 降序
 s2 := []float64{5.9, -1.2, 0.2, -3.7, 2.6} // unsorted sort.Float64s(s2) fmt.Println(s2) // float64 v2 := sort.SearchFloat64s(s2, 0.2) fmt.Println(v2) sort.Sort(sort.Reverse(sort.Float64Slice(s2))) fmt.Println(s2) // 降序
 s3 := []string{"Go", "C++", "Go+", "Alpha", "C", "Delta"} sort.Strings(s3) fmt.Println(s3) v3 := sort. SearchStrings(s3, "C++") fmt.Println(v3) sort.Sort(sort.Reverse(sort.StringSlice(s3))) fmt.Println(s3) // 降序}

执行结果:

[-1 1 3 4 6 8]4[8 6 4 3 1 -1][-3.7 -1.2 0.2 2.6 5.9]2[5.9 2.6 0.2 -1.2 -3.7][Alpha C C++ Delta Go Go+]2[Go+ Go Delta C++ C Alpha]

三、自定义数据结构的排序

对于自定义数据结构的排序,就需要先实现一些方法才行,例如:Len,Less和Swap。原因是如下所示:

“struct 包含多个属性,sort并不知道你想以哪一个属性或哪几个属性作为衡量大小的标准。如果你能帮助程序完成比较,并将结果返回, sort 包内的方法就可以完成排序,判断,查找等。“

1.方法一:

当然,sort也提供了下面几个API来实现数据结构的排序操作,如下所示,我们可以通过这几个API实现数据结构的排序。

func Slice(slice interface{}, less func(i, j int) bool) //The sort is not guaranteed to be stable. For a stable sort, use SliceStable.

func SliceStable(slice interface{}, less func(i, j int) bool)

func Search(n int, f func(int) bool) int

例子如下:

package mainimport ( "fmt" "sort")type Student struct { Name string Grade int}func main() { student := []Student{ {"Go", 7}, {"Alice", 55}, {"Ve", 24}, {"Bob", 75}, } // 1.sort.Slice的使用 sort.Slice(student, func(i, j int) bool { return student[i].Grade < student[j].Grade }) // 按成绩升序排序 fmt.Println("Slice Sort by grade:", student)
 sort.Slice(student, func(i, j int) bool { return student[i].Grade > student[j].Grade }) // 按成绩降序排序 fmt.Println("Slice Sort by grade:", student)
 // 2.sort.SliceStable的使用 sort.SliceStable(student, func(i, j int) bool { return student[i].Grade < student[j].Grade }) // 按成绩升序排序 fmt.Println("SliceStable Sort by grade:", student)
 sort.SliceStable(student, func(i, j int) bool { return student[i].Grade > student[j].Grade }) // 按成绩降序排序 fmt.Println("SliceStable Sort by grade:", student)}

执行结果:

Slice Sort by grade: [{Go 7} {Ve 24} {Alice 55} {Bob 75}]Slice Sort by grade: [{Bob 75} {Alice 55} {Ve 24} {Go 7}]SliceStable Sort by grade: [{Go 7} {Ve 24} {Alice 55} {Bob 75}]SliceStable Sort by grade: [{Bob 75} {Alice 55} {Ve 24} {Go 7}]

2.方法二

模拟IntSlice来实现sort的排序操作,例子如下所示:

package main
import ( "fmt" "sort")
type Student struct { Name string Grade int}type StudentSlice []Student
func (a StudentSlice) Len() int { // 重写 Len() 方法 return len(a)}func (a StudentSlice) Swap(i, j int) { // 重写 Swap() 方法 a[i], a[j] = a[j], a[i]}func (a StudentSlice) Less(i, j int) bool { // 重写 Less() 方法, 从大到小排序 return a[j].Grade < a[i].Grade}
func main() { student := []Student{ {"Go", 7}, {"Alice", 55}, {"Ve", 24}, {"Bob", 75}, } sort.Sort(StudentSlice(student)) // 升序 fmt.Println(student) sort.Sort(sort.Reverse(StudentSlice(student)))// 降序 fmt.Println(student)
}

执行结果:

[{Bob 75} {Alice 55} {Ve 24} {Go 7}][{Go 7} {Ve 24} {Alice 55} {Bob 75}]

参考文档:

https://golang.org/pkg/sort
https://books.studygolang.com/The-Golang-Standard-Library-by-Example/chapter03/03.1.html

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/

原文:https://mp.weixin.qq.com/s/2aZIldsDYTvt1tkdlh4d9g

公众号:灰子学技术

• 编辑
• 预览