Go语言学习笔记—golang标准库sort包

---

前言

sort包提供了排序切片和用户自定义数据集以及相关功能的函数。

[]int[]float64[]string

主要包括：

• 对基本数据类型切片的排序支持。
• 基本数据元素查找。
• 判断基本数据类型切片是否已经排好序。
• 对排好序的数据集合逆序

一 排序接口

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

实例演示：

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)
}

运行结果：

[Running] go run "c:\Users\Mechrevo\Desktop\go_pro\test.go"
1 0 false [1 3 2]
2 1 true [1 3 2]
1 0 false [1 2 3]
[1 2 3]

[Done] exited with code=0 in 1.105 seconds

二 相关函数汇总

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.1 Sort排序方法

sort.Interface

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

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

func Sort(data Interface)

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

3.2 IsSorted是否已排序方法

sort包提供了IsSorted方法，可以判断数据集合是否已经排好顺序。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
}

3.3 Reverse逆序排序方法

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

func Reverse(data Interface) Interface

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

//定义了一个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.4 Search查询位置方法

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

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

Search()方法会使用“二分查找”算法，来搜索某指定切片[0:n]，并返回能够使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。

四 sort包支持的内部数据类型

[]int

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类型定义了Search()方法，包装了SearchInts()函数
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

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

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

sort.Ints()

实例演示：

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)
}

运行结果：

[Running] go run "c:\Users\Mechrevo\Desktop\go_pro\test.go"
排序前f: [3 5 1 2 4]
排序后f: [1 2 3 4 5]

[Done] exited with code=0 in 1.005 seconds

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

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)
}

运行结果：

[Running] go run "c:\Users\Mechrevo\Desktop\go_pro\test.go"
排序前f: [3 5 1 2 4]
排序后f: [1 2 3 4 5]
降序排序后f: [5 4 3 2 1]

[Done] exited with code=0 in 0.934 seconds

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

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)
}

运行结果：

[Running] go run "c:\Users\Mechrevo\Desktop\go_pro\test.go"
排序前f: [3 5 1 2 4]
排序后f: [1 2 3 4 5]
3的索引位置为: 2

[Done] exited with code=0 in 0.957 seconds

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

[]float64

实现与Ints类似

内部实现：

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()相对应的三个方法：

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

实例演示：

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)
}

运行结果：

[Running] go run "c:\Users\Mechrevo\Desktop\go_pro\test.go"
排序前的f: [1.1 4.4 5.5 3.3 2.2]
排序后的f: [1.1 2.2 3.3 4.4 5.5]

[Done] exited with code=0 in 1.414 seconds

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

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

[]string

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

实现与Ints类似

内部实现：

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()相对应的三个方法：

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

实例演示：

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()
}

运行结果：

[Running] go run "c:\Users\Mechrevo\Desktop\go_pro\test.go"
[100 42 41 3 2]
[100 2 3 41 42]
----------
[d ac c ab e]
[ab ac c d e]
----------
[啊 博 次 得 饿 周]
[博 周 啊 得 次 饿]
博 [229 141 154]
周 [229 145 168]
啊 [229 149 138]
得 [229 190 151]
次 [230 172 161]
饿 [233 165 191]

[Done] exited with code=0 in 1.102 seconds

[][]int

实例演示：

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)
}

运行结果：

[Running] go run "c:\Users\Mechrevo\Desktop\go_pro\test.go"
[[1 4] [9 3] [7 5]]
[[9 3] [1 4] [7 5]]

[Done] exited with code=0 in 0.931 seconds

[]map[string]int [{"k":0}, {"k1":1}, {"k2":2}]

实例演示：

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)
}

运行结果：

[Running] go run "c:\Users\Mechrevo\Desktop\go_pro\test.go"
[map[a:4 b:12] map[a:3 b:11] map[a:5 b:10]]
[map[a:3 b:11] map[a:4 b:12] map[a:5 b:10]]

[Done] exited with code=0 in 1.456 seconds

[]struct

实例演示：

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)
}

运行结果：

[Running] go run "c:\Users\Mechrevo\Desktop\go_pro\test.go"
[{n1 12} {n2 11} {n3 10}]
[{n3 10} {n2 11} {n1 12}]

[Done] exited with code=0 in 1.048 seconds