Go Sort

2021-03-23 本文已影响0人 JunChow520

二分查找
顺时针查找

很多语言中排序算法都是和序列数据类型关联，同时排序函数和具体类型元素关联。相比之下，Golang的sort.Sort函数不会对具体的序列和它的元素做任何假设。相反它使用了一个接口类型sort.Interface来指定通用的排序算法和可能被排序到的序列类型之间的约定。这个接口的实现由序列的具体表示和它希望排序的元素决定，序列的表示经常会是一个切片。

算法

sort包内部实现了四种基本的排序算法

插入排序insertionSort`
归并排序symMerge
堆排序heapSort
快速排序quickSort

sort包内置的四种排序方法是不公开的，只能被用于sort包内部使用。因此，对数据集合排序时，不必考虑应当选择哪一种，只需要实现sort.Interface接口定义三个接口即可。

接口

sort包会依据实际数据自动选择最优的排序算法，编写代码时只需要考虑实现sort.Interface接口。

sort操作的对象通常是一个slice，需满足三个基本的接口，并且能使用整数来索引。一个内置的排序算法需要实现三个方法：

Len() 序列的长度
Less(i,j int) bool 表示两个元素比较的结构
Swap(i,j int) 交换两个元素的方式

type Interface interface{
  Len() int //返回集合中的元素个数
  Less(i,j int) bool//i>j 返回索引i和元素是否比索引j的元素小
  Swap(i,j int)//交换i和j的值
}

实现了sort.Interface类型的数据集合后，即可调用sort包的Sort()方法进行排序。

sort.Sort

Sort()方法唯一的参数就是待排序的数据集合。

func sort.Sort(data sort.Interface)

例如：对[]int整数切片序列按照从小到大升序排序

$ vim ./test/obj_test.go

package test

import (
    "sort"
    "testing"
)

type IntSlice []int

func (s IntSlice) Len() int           { return len(s) }
func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }
func (s IntSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func TestSort(t *testing.T) {
    s := []int{4, 5, 1, 7, 2, 9}
    sort.Sort(IntSlice(s))
    t.Log(s)
}

$ go test -v -run TestSort ins_test.go
=== RUN   TestSort
    ins_test.go:19: [1 2 4 5 7 9]
--- PASS: TestSort (0.00s)
PASS
ok      command-line-arguments  0.309s

例如：自定义结构体类型切片排序

sort.IsSorted

sort包提供了IsSorted方法可以判断数据集合是否已经排列好顺序
sort包的IsSorted方法内部实现依赖于自定义实现的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.Reverse

sort包提供了Reverse()方法，允许将数据按Less()定义的排序方式逆序排序，而无需修改Less()代码。

func Reverse(data Interface) Interface

类型排序

升序排序
Golang中sort包定义了常见类型的排序方法

类型	实现sort.Interface的类型	直接排序方法	排序方式
字符串 string	StringSlice	sort.Strings(s []string)	按字符串ASCII值升序排序
整型 int	IntSlice	sort.Ints(s []int)	按数值升序排序
双精度浮点 float64	Float64Slice	sort.Float64(s []float64)	按数值升序排序

Golang提供了sort.Ints()函数对int整数切片序列从小到大升序排序

s := []int{4, 5, 1, 7, 2, 9}
sort.Ints(s)
fmt.Printf("%v\n", s) // [1 2 4 5 7 9]

Golang提供了sort.Float64()函数对float64浮点数切片序列从小到大升序排序

s := []float64{1.4, 0.5, 2.1, 5.7, 2.2, 1.9}
sort.Float64s(s)
fmt.Printf("%v\n", s) // [0.5 1.4 1.9 2.1 2.2 5.7]

Golang提供了sort.Strings()函数对string字符串切片序列从小到大升序排序

s := []string{"x", "hi", "fee", "carl"}
sort.Strings(s)
fmt.Printf("%v\n", s) // [carl fee hi x]

降序排序

Golang中对某个类型的对象排序使用sort.Sort(obj)方法
需要对类型绑定三个方法：Len()求长度、Less(i,j)比较元素大小、Swap(i,j)交换元素
sort包下三个类型IntSlice、Float64Slice、StringSlice分别实现了三个方法，对应排序的是[]int、[]float64、[]string。若期望逆序排序，只需将对应的Less函数修改。
Golang的sort包使用sort.Reverse(slice)来调换slice.Interface.Less比较函数
使用sort.Reverse进行逆序排序，若想对一个sortable object可排序对象进行逆序排序，可自定义一个type类型。

例如：对整型切片序列从大到小降序排序

Golang对[]int定义了IntSlice类型实现了的排序接口

s := []int{2, 4, 3, 5, 7, 6, 1, 0}
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Printf("%v\n", s) // [7 6 5 4 3 2 1 0]

例如：对浮点数切片序列从大到小降序排序

Golang对[]float64定义了Float64Slice类型实现了排序接口

s := []float64{2.1, 1.4, 4.3, 2.5, 1.7, 0.6, 2.1, 0.5}
sort.Sort(sort.Reverse(sort.Float64Slice(s)))
fmt.Printf("%v\n", s)//[4.3 2.5 2.1 2.1 1.7 1.4 0.6 0.5]

例如：对字符串切片序列从大到小降序排序

Golang对[]string定义了StringSlice类型实现了排序接口

s := []string{"o", "eh", "wow", "oops"}
sort.Sort(sort.Reverse(sort.StringSlice(s)))
fmt.Printf("%v\n", s)//[wow oops o eh]

sort.Strings

例如：对字典的键名升序排序

m := map[string]interface{}{"id": 1, "name": "admin", "pid": 0}

keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
sort.Strings(keys)

for i, v := range keys {
    fmt.Println(i, v)
}

0 id
1 name
2 pid

sort.Search

sort.Search函数可以在一个有序列表上进行二分查找操作

index := func Search(n int, f func(int) bool) int

参数	类型	描述
n	int	从第一个元素开始搜索的元素个数
f	func	通过接收一个函数作为参数，找到`f(x)=true`的元素。

Search函数采用二分法搜索找到[0, n)区间内最小且满足f(i) = true的index索引值，i的取值范围0 <= i < n。若无法找到index则返回为n。

二分查找法

在一个有序的数列中，将中间元素与查找元素相比较。
若相等则直接返回
若中间元素大于查找元素，则在中间元素右侧继续使用二分查找法。
若中间元素小于查找元素，则在中间元素左侧继续使用二分查找法。

二分查找

例如：二分位为真则先前查询

data := []int{10, 25, 11, 24, 17, 26}
index := sort.Search(len(data), func(i int) bool { return data[i] > 23 })
fmt.Println(index, data[index]) // 1 25

例如：二分位为假则向后查询

data := []int{10, 22, 11, 24, 17, 26}
index := sort.Search(len(data), func(i int) bool { return data[i] > 23 })
fmt.Println(index, data[index]) // 3 24

例如：为什么？

data := []int{10, 25, 11, 22, 17, 26}
index := sort.Search(len(data), func(i int) bool { return data[i] > 23 })
fmt.Println(index, data[index]) // 5 26