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

公众号：灰子学技术

---