Go 标准库之 sort

https://pkg.go.dev/sort

总结

1
2
3
4
5
6
7
8
9
10
11
12
sort.Float64s(fs)       // 将[]float64按升序排序
sort.Float64AreSorted(fs)// 如果[]float64是有序的则返回True
sort.Ints(is)           // 将[]int按升序排序
sort.IntAreSorted(is)   // 如果[]int是有序的则返回true
sort.IsSorted(d)        // 如果sort.Interface的值d是有序的，则返回True
sort.Search(size,fn)    // 在一个排序好的数组中根据函数签名为func(int) bool的函数fn进行搜索，返回第一个使得函数fn返回值为true的索引
sort.SearchFloat64s(fs,f)// 返回有序[]float64切片fs中类型为float64的值f的索引值
sort.SearchInts(is,i)   // 返回有序[]int切片is中类型为int的值i的索引
sort.SearchStrings[ss,s]// 返回有序[]string切片ss中类型为string的值s的索引
sort.Sort(d)            // 排序类型为sort.Interface的切片
sort.Strings(ss)        // 按升序排序[]string类型的切片ss
sort.StringAreSorted(ss)// 如果[]string类型的切片ss是有序的，返回true

1、排序接口

sort包实现了四种基本排序算法：插入排序、归并排序、堆排序、快速排序。 但是这四种排序方法是不公开的，它们只能在 sort 包内部使用。

sort 包会根据实际数据自动选择高效的排序算法，所以在对数据集合排序时不必考虑应当选择哪一种排序方法，只要实现了 sort.Interface 定义的三个方法，就可以顺利对数据集合进行排序。

内置的对 int、float、string 进行排序的方法都实现了这个接口，如果要对自定义的数据进行排序，也要是实现这个接口。

定义如下：

1
2
3
4
5
type Interface interface {
    Len() int	        // 获取当前元素个数
    Less(i, j int) bool	// 如果i索引的数据小于j索引的数据，返回true，并调用 Swap()；false 不调用swap。
    Swap(i, j int)	    // 交换i和j索引的两个元素的位置
}

实例演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package main

import (
	"fmt"
	"sort"
)

type NewInts []uint

func (n NewInts) Len() int {
	return len(n)
}

func (n NewInts) Less(i, j int) bool {
	fmt.Println(i, j, n[i] < n[j], n)
	return n[i] < n[j]
}

func (n NewInts) Swap(i, j int) {
	n[i], n[j] = n[j], n[i]
}

func main() {
	n := []uint{1, 3, 2}
	sort.Sort(NewInts(n))
	fmt.Println(n)
}

2、相关方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func Ints(a []int)
func IntsAreSorted(a []int) bool
func SearchInts(a []int, x int) int
func Float64s(a []float64)
func Float64sAreSorted(a []float64) bool
func SearchFloat64s(a []float64, x float64) int
func SearchFloat64s(a []float64, x float64) bool
func Strings(a []string)
func StringsAreSorted(a []string) bool
func SearchStrings(a []string, x string) int
func Sort(data Interface)
func Stable(data Interface)
func Reverse(data Interface) Interface
func IsSorted(data Interface) bool
func Search(n int, f func(int) bool) int

3、方法介绍

3.1、Sort 排序方法

对数据集合（包括自定义数据类型的集合）排序，需要实现 sort.Interface 接口的三个方法，即：

1
2
3
4
5
6
7
type Interface interface {
    Len() int	// 获取数据集合元素个数
   
    Less(i, j int) bool	// 如果i索引的数据小于j索引的数据，返回true，Swap()，即数据升序排序。
    
    Swap(i, j int)	// 交换i和j索引的两个元素的位置
}

实现了这三个方法后，即可调用 sort.Sort()方法进行排序。 Sort() 方法定义如下：

1
func Sort(data Interface)

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

3.2、Stable 稳定排序方法

相较于 Sort 方法，Stable 方法也用于对一个列表进行排序，但是它额外提供保证排序算法是稳定的，也就是排序前后值相同的两个元素相对位置不发生变化，方法声明和 Sort 类似。

1
func Stable(data Interface)

3.3、IsSorted 是否已排序方法

sort 包提供了 IsSorted 方法，可以判断数据集合是否已经排好顺序。IsSorted() 方法的内部实现依赖于我们自己实现的 Len() 和 Less() 方法：

1
2
3
4
5
6
7
8
9
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
}

3.4、Reverse 逆序排序方法

Reverse 方法用于翻转一个列表并返回翻转后的列表。Reverse将数据按 Less() 定义的排序方式逆序排序，而不必修改 Less() 代码。方法定义如下：

1
func Reverse(data Interface) Interface

看下 Reverse() 的内部实现，可以看到 Reverse() 返回一个 sort.Interface 接口类型的值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//定义了一个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}
}

3.5、Search 查询位置方法

sort 包提供 Search() 方法查询位置，其实现如下：

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

Search() 方法可以在一个有序列表上进行二分查找操作，它接收两个参数，

  • 第一个参数是从第一个元素开始搜索的元素个数；
  • 第二个参数是一个方法，通过接收一个方法f作为参数，找到使得 f(x)==true 的元素

Search() 方法返回能够使 f(i)=true 的最小 i（0<=i<n）值，并且会假定：如果 f(i)=true，则 f(i+1)=true。即对于切片[0:n]，i 之前的切片元素会使 f() 方法返回 false，i 及 i 之后的元素会使 f() 方法返回 true。
但是，当在切片中无法找到时 f(i)=true 的 i 时（此时切片元素都不能使f()方法返回true），Search() 方法会返回 n。

3.6、Slice 对一个 Slice 进行排序

从 Go1.8 开始，Go 在 sort 包中提供了 sort.Slice() 这个更为简便的排序方法。这是实际使用中更为常用的一个方法，方法接收两个参数。

  • 第一个是需要排序的 Slice；
  • 第二个是 Slice 元素比较方法，它类似于前面 sort.Interface 里的 Less 方法。

方法声明如下：

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

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
type HeroKind int
const (
	None HeroKind = iota
	Tank
	Assassin
	Mage
)

type Hero struct {
	Name string
	Kind HeroKind
}

func SortStruct2() {
	heros := []*Hero{
		{"吕布", Tank},
		{"李白", Assassin},
		{"妲己", Mage},
		{"貂蝉", Assassin},
		{"关羽", Tank},
		{"诸葛亮", Mage},
	}
	sort.Slice(
	    heros, 
	    func(i, j int) bool {
            if heros[i].Kind != heros[j].Kind {
                return heros[i].Kind < heros[j].Kind
            }
            return heros[i].Name < heros[j].Name
	    }
	)
	for _, v := range heros {
		fmt.Printf("%+v\n", v)
	}
}

4、sort包支持的内部数据类型

4.1、[]int 排序

sort 包定义了一个 IntSlice 类型，并且实现了 sort.Interface 接口：

1
2
3
4
5
6
7
8
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类型定义了Search()方法，包装了SearchInts()方法
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

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

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

所以，对 []int 切片升序排序，经常使用sort.Ints()，而不是直接使用 IntSlice 类型。

实例演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import (
	"fmt"
	"sort"
)

func main() {
	f := []int{3, 5, 1, 2, 4}
	fmt.Printf("排序前f: %v\n", f)
	sort.Ints(f)
	fmt.Printf("排序后f: %v\n", f)
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package main

import (
	"fmt"
	"sort"
)

func main() {
	f := []int{3, 5, 1, 2, 4}
	fmt.Printf("排序前f: %v\n", f)
	sort.Ints(f)
	fmt.Printf("排序后f: %v\n", f)
	sort.Sort(sort.Reverse(sort.IntSlice(f)))
	fmt.Printf("降序排序后f: %v\n", f)
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package main

import (
	"fmt"
	"sort"
)

func main() {
	f := []int{3, 5, 1, 2, 4}
	fmt.Printf("排序前f: %v\n", f)
	sort.Ints(f)
	fmt.Printf("排序后f: %v\n", f)
	r := sort.SearchInts(f, 3)
	fmt.Printf("3的索引位置为: %v\n", r)
}

注意，SearchInts() 的使用条件为：切片 a 已经升序排序。

4.2、[]float64 排序

实现与 Ints 类似

内部实现：

1
2
3
4
5
6
type Float64Slice []float64
func (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() 相对应的三个方法：

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

实例演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import (
	"fmt"
	"sort"
)

func main() {
	f := []float64{1.1, 4.4, 5.5, 3.3, 2.2}
	fmt.Printf("排序前的f: %v\n", f)
	sort.Float64s(f)
	fmt.Printf("排序后的f: %v\n", f)
}

其他如 Search() 方法与 Ints 类似，不再赘述。

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

4.3、[]string 排序

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

实现与Ints类似

内部实现：

1
2
3
4
5
6
type StringSlice []string
func (p StringSlice) Len() int           { return len(p) }
func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p StringSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p StringSlice) Sort() { Sort(p) }
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }

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

1
2
3
func Strings(a []string)
func StringsAreSorted(a []string) bool
func SearchStrings(a []string, x string) int

实例演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package main

import (
	"fmt"
	"sort"
)

func test1() {
	ls := sort.StringSlice{
		"100",
		"42",
		"41",
		"3",
		"2",
	}
	fmt.Println(ls)
	sort.Strings(ls)
	fmt.Println(ls)
}

func test2() {
	ls := sort.StringSlice{
		"d",
		"ac",
		"c",
		"ab",
		"e",
	}
	fmt.Println(ls)
	sort.Strings(ls)
	fmt.Println(ls)
}

func test3() {
	ls := sort.StringSlice{
		"啊",
		"博",
		"次",
		"得",
		"饿",
		"周",
	}
	fmt.Println(ls)
	sort.Strings(ls)
	fmt.Println(ls)

	for _, v := range ls {
		fmt.Println(v, []byte(v))
	}
}

func main() {
	test1()
	fmt.Println("----------")
	test2()
	fmt.Println("----------")
	test3()
}

4.4、复杂结构: [][]int排序

实例演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main

import (
	"fmt"
	"sort"
)

type testSlice [][]int

func (l testSlice) Len() int           { return len(l) }
func (l testSlice) Swap(i, j int)      { l[i], l[j] = l[j], l[i] }
func (l testSlice) Less(i, j int) bool { return l[i][1] < l[j][1] }

func main() {
	ls := testSlice{
		{1, 4},
		{9, 3},
		{7, 5},
	}

	fmt.Println(ls)
	sort.Sort(ls)
	fmt.Println(ls)
}

4.5、复杂结构体排序 []map[string]float64

实例演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package main
 
import (
    "fmt"
    "sort"
)
 
type testSlice []map[string]float64
 
func (l testSlice) Len() int           { return len(l) }
func (l testSlice) Swap(i, j int)      { l[i], l[j] = l[j], l[i] }
func (l testSlice) Less(i, j int) bool { return l[i]["a"] < l[j]["a"] } // 按照"a"对应的值排序
 
func main() {
    ls := testSlice{
        {"a": 4, "b": 12},
        {"a": 3, "b": 11},
        {"a": 5, "b": 10},
    }
 
    fmt.Println(ls)
    sort.Sort(ls)
    fmt.Println(ls)
}

4.6、复杂结构体：[]struct 排序(常用)

实例演示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package main

import (
	"fmt"
	"sort"
)

type People struct {
	Name string
	Age  int
}

type testSlice []People

func (l testSlice) Len() int           { return len(l) }
func (l testSlice) Swap(i, j int)      { l[i], l[j] = l[j], l[i] }
func (l testSlice) Less(i, j int) bool { return l[i].Age < l[j].Age }

func main() {
	ls := testSlice{
		{Name: "n1", Age: 12},
		{Name: "n2", Age: 11},
		{Name: "n3", Age: 10},
	}

	fmt.Println(ls)
	sort.Sort(ls)
	fmt.Println(ls)
}
Go > Go 标准库
#Go #Go 标准库
Go 标准库之 sort
https://flepeng.github.io/021-Go-32-Go-标准库-Go-标准库之-sort/
作者
Lepeng
发布于
2024年12月3日
许可协议