当前位置：首页 > news >正文

Go 排序包 sort

news 文章来源：https://blog.csdn.net/qq_42702981/article/details/129011078 2024/11/26 19:34:02

写在前面的使用总结：

排序结构体

实现Len，Less，Swap三个函数

package main  import (  "fmt"  "sort")  type StuScore struct {  name  string  score int  
}  type StuScores []StuScore  func (s StuScores) Len() int {  return len(s)  
}  func (s StuScores) Less(i, j int) bool {  return s[i].score < s[j].score  
}  func (s StuScores) Swap(i, j int) {  s[i], s[j] = s[j], s[i]  
}  func main() {  stus := StuScores{  {"mike ", 98},  {"jj", 91},  {"hello", 96},  {"simple", 90},  }  fmt.Println("Default:\n\t", stus)  sort.Sort(stus)  fmt.Println("IS sorted?\n\t", sort.IsSorted(stus))  fmt.Println("Sorted:\n\t", stus)  
}

排序int切片

s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
sort.Ints(s)
fmt.Println(s) // 将会输出[1 2 3 4 5 6]

排序float64切片

Float := []float64{1.2, 3.4, 8.2, 1.1}  sort.Float64s(Float)  
fmt.Println(Float) //[1.1 1.2 3.4 8.2]  
fmt.Println(sort.Float64sAreSorted(Float))//true  
fmt.Println(sort.SearchFloat64s(Float, 1.2))// 1

排序string切片

Strings := []string{"1", "4", "a", "0", "2"}  sort.Strings(Strings)  
fmt.Println(Strings)  
fmt.Println(sort.StringsAreSorted(Strings))  
fmt.Println(sort.SearchStrings(Strings, "a"))  /*  
[0 1 2 4 a]  
true  
4  
*/

简介

基本实现了插入排序，归并排序，堆排序和快速排序。当然这四种排序方法是不分开的，它们是在sort包的内部被使用。所以使用时，不用考虑使用那种排序方法。
sort会自动选择合适的排序方法保证高效性。

使用：

只要实现了 sort.Interface 定义的三个方法：获取数据集合长度的 Len() 方法、比较两个元素大小的 Less() 方法和交换两个元素位置的 Swap() 方法，就可以顺利对数据集合进行排序。

数据集合排序

前面说了，对数据集合排序（包括自定义数据类型集合）排序需要实现sort.Interface接口的三个方法，我们看看该接口的定义：

type Interface interface{//获取数据集合元素个数Len() int//如果i索引的数据小于j索引的数据，返回true，且不会调用下面的Swap(),即数据升序排序Less(i,j int) bool //交换i和j索引的两个元素的位置Swap(i,j int )}

数据集合实现了这三个方法后，即可调用该包的Sort（）方法进行排序，Sort（）方法定义如下：

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
}

下面是一个使用sort包对学生成绩进行排序的实例：

package main  import (  "fmt"  "sort")  type StuScore struct {  name  string  score int  
}  type StuScores []StuScore  func (s StuScores) Len() int {  return len(s)  
}  func (s StuScores) Less(i, j int) bool {  return s[i].score < s[j].score  
}  func (s StuScores) Swap(i, j int) {  s[i], s[j] = s[j], s[i]  
}  func main() {  stus := StuScores{  {"mike ", 98},  {"jj", 91},  {"hello", 96},  {"simple", 90},  }  fmt.Println("Default:\n\t", stus)  sort.Sort(stus)  fmt.Println("IS sorted?\n\t", sort.IsSorted(stus))  fmt.Println("Sorted:\n\t", stus)  
}

该示例实现的是升序排序，如果要得到降序排序结果，其实只要修改 Less() 函数：

//Less(): 成绩降序排序 , 只将小于号修改为大于号
func (s StuScores) Less(i, j int) bool {return s[i].score > s[j].score
}

此外，sort包提供了 Reverse() 方法，可以允许将数据按 Less() 定义的排序方式逆序排序，而不必修改 Less() 代码。方法定义如下：

func Reverse(data Interface) Interface

我们可以看到 Reverse() 返回的一个 sort.Interface 接口类型，整个 Reverse() 的内部实现比较有趣：

// 定义了一个 reverse 结构类型，嵌入 Interface 接口
type reverse struct {Interface
}//reverse 结构类型的 Less() 方法拥有嵌入的 Less() 方法相反的行为
//Len() 和 Swap() 方法则会保持嵌入类型的方法行为
func (r reverse) Less(i, j int) bool {return r.Interface.Less(j, i)
}// 返回新的实现 Interface 接口的数据类型
func Reverse(data Interface) Interface {return &reverse{data}
}

了解内部原理后，可以在学生成绩排序示例中使用 Reverse() 来实现成绩升序排序：

sort.Sort(sort.Reverse(stus))
fmt.Println(stus)

最后一个方法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)
}

官方文档还给出了一个猜数字的小程序：

func GuessingGame() {var s stringfmt.Printf("Pick an integer from 0 to 100.\n")answer := sort.Search(100, func(i int) bool {fmt.Printf("Is your number <= %d? ", i)fmt.Scanf("%s", &s)return s != "" && s[0] == 'y'})fmt.Printf("Your number is %d.\n", answer)
}

sort包对于内部数据类型的排序

sort包原生支持[]int,[]float64,[]string三种内建数据类型切片的排序操作，我们不用自己实现Len（），Less（），Swap（）方法

IntSlice类型及`[]int`排序

由于[]int切片排序内部实现及使用方法和[]float64,[]string类似，这里就描述其中一部分。

sort排序IntSlice类型，并且实现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] }
//IntSlice 类型定义了 Sort() 方法，包装了 sort.Sort() 函数
func (p IntSlice) Sort() { Sort(p) }
//IntSlice 类型定义了 SearchInts() 方法，包装了 SearchInts() 函数
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

并且提供了sort.Ints()方法使用了该IntSlice类型：

func Ints(a []int){Sort(IntSlice(a)) }

使用对[]int切片进行排序更常使用sort.Ints()，而不是IntSlice类型：

s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
sort.Ints(s)
fmt.Println(s) // 将会输出[1 2 3 4 5 6]

如果要使用降序排序，显然要用前面提到的 Reverse() 方法：

s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s) // 将会输出[6 5 4 3 2 1]

如果要查找整数 x 在切片 a 中的位置，相对于前面提到的 Search() 方法，sort包提供了 SearchInts():

func SearchInts(a []int, x int) int

注意，SearchInts() 的使用条件为：切片 a 已经升序排序 以下是一个错误使用的例子：

s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
fmt.Println(sort.SearchInts(s, 2)) // 将会输出 0 而不是 1

Float64Slice类型和`[]float64`排序

实现与 Ints 类似，只看一下其内部实现：

type Float64Slice []float64func (p Float64Slice) Len() int           { return len(p) }
func (p Float64Slice) Less(i, j int) bool { return p[i] < p[j] || isNaN(p[i]) && !isNaN(p[j]) }
func (p Float64Slice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p Float64Slice) Sort() { Sort(p) }
func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }

与 Sort()、IsSorted()、Search() 相对应的三个方法：

func Float64s(a []float64)  
func Float64sAreSorted(a []float64) bool
func SearchFloat64s(a []float64, x float64) int

要说明一下的是，在上面 Float64Slice 类型定义的 Less 方法中，有一个内部函数 isNaN()。 isNaN() 与_math_包中 IsNaN() 实现完全相同，sort包之所以不使用 math.IsNaN()，完全是基于包依赖性的考虑，应当看到，sort包的实现不依赖与其他任何包。

StringSlice 类型及`[]string` 排序

两个 string 对象之间的大小比较是基于“字典序”的。