golang使用sort包排序 - Golang教程网

sort包实现了四种基本排序算法：插入排序、归并排序、堆排序和快速排序。但是，这四种排序方法不是公开的，它们只在sort包内部被使用。所以，在对数据集合排序时，不必考虑应当选择哪一种排序方法，只要实现了sort.Interface定义的三个方法，就可以顺利对数据集合进行排序。sort.Interface接口定义的三个方法为：获取数据集合长度的Len()方法、比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法。根据实际数据，sort包会自动选择高效的排序算法。除此之外，为了方便对常用数据类型的操作，sort包提供了对[]int切片、[]float64切片和[]string切片的完整支持，主要包括：

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

2.1 实现排序接口的三个基本方法

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

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

2.2 Sort排序方法

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

 func Sort(data Interface)

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

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

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

2.5 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、[]float64和[]string三种内建数据类型切片的排序操作，我们不必自己实现相关的Len()、Less()和Swap()方法。

3.1 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类型定义了Search()方法，包装了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} // 未排序的切片数据
sort.Ints(s) //升序排序后的s为[1 2 3 4 5 6]
fmt.Println(sort.SearchInts(s, 3)) //将会输出2

3.2 Float64Slice类型及[]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

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

3.3 StringSlice类型及[]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

4. 代码示例

4.1 自定义结构体升序排序

package main

import (
	"fmt"
	"sort"
)

//学生成绩结构体
type StuScore struct {
	//姓名
	name  string
	//成绩
	score int
}

type StuScores []StuScore

//Len()
func (s StuScores) Len() int {
	return len(s)
}

//Less():成绩将有低到高排序（升序）
func (s StuScores) Less(i, j int) bool {
	return s[i].score < s[j].score
}

//Swap()
func (s StuScores) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func main() {
	stus := StuScores{
		{"alan", 95},
		{"hikerell", 91},
		{"acmfly", 96},
		{"leao", 90}}

	fmt.Println("Default:")
	// 原始顺序
	for _, v := range stus {
		fmt.Println(v.name, ":", v.score)
	}
	fmt.Println()

	//StuScores已经实现了sort.Interface接口
	sort.Sort(stus)

	fmt.Println("ASC Sorted:")
	// 排好序后的结构
	for _, v := range stus {
		fmt.Println(v.name, ":", v.score)
	}
	fmt.Println()
	
	// 判断是否已经升序排好，将会打印true
	fmt.Println("IS Sorted ASC?", sort.IsSorted(stus))

	// 查找指定值是否在升序的slice中
	xStu := StuScore{
		name:"alan",
		score:95,
	}
	// 搜索
	pos := sort.Search(len(stus), func(i int) bool { return stus[i].score >= xStu.score })
	fmt.Printf("pos=%v\n", pos)
	if (pos < len(stus)) && (stus[pos].score == xStu.score) {
		fmt.Println(xStu, "在s中的位置为：", pos)
	} else {
		fmt.Printf("s不包含元素, xStu=%v\n", xStu)
	}
}

运行结果如下所示：

Default:
alan : 95
hikerell : 91
acmfly : 96
leao : 90

ASC Sorted:
leao : 90
hikerell : 91
alan : 95
acmfly : 96

IS Sorted ASC? true
pos=2
{alan 95} 在s中的位置为： 2

4.2 自定义结构体降序排序

在4.1节的基础上，实现自定义结构体降序排序，有两种方式：第一种方式是修改Less方法，第二种方式是使用Reverse方法。

4.2.1 修改Less方法

代码示例：

package main

import (
	"fmt"
	"sort"
)

//学生成绩结构体
type StuScore struct {
	//姓名
	name  string
	//成绩
	score int
}

type StuScores []StuScore

//Len()
func (s StuScores) Len() int {
	return len(s)
}

//Less():成绩将有低到高排序（降序）
func (s StuScores) Less(i, j int) bool {
	return s[i].score > s[j].score
}

//Swap()
func (s StuScores) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func main() {
	stus := StuScores{
		{"alan", 95},
		{"hikerell", 91},
		{"acmfly", 96},
		{"leao", 90}}

	fmt.Println("Default:")
	// 原始顺序
	for _, v := range stus {
		fmt.Println(v.name, ":", v.score)
	}
	fmt.Println()

	//StuScores已经实现了sort.Interface接口
	sort.Sort(stus)

	fmt.Println("DESC Sorted:")
	// 排好序后的结构
	for _, v := range stus {
		fmt.Println(v.name, ":", v.score)
	}
	fmt.Println()

	// 判断是否已经排好顺序，将会打印true
	fmt.Println("IS Sorted DESC?", sort.IsSorted(stus))

	// 查找指定值是否在降序的slice中
	xStu := StuScore{
		name:"alan",
		score:995,
	}
	// 搜索
	pos := sort.Search(len(stus), func(i int) bool { return stus[i].score >= xStu.score })
	fmt.Printf("pos=%v\n", pos)
	if (pos < len(stus)) && (stus[pos].score == xStu.score) {
		fmt.Println(xStu, "在s中的位置为：", pos)
	} else {
		fmt.Printf("s不包含元素, xStu=%v\n", xStu)
	}
}

运行结果：

Default:
alan : 95
hikerell : 91
acmfly : 96
leao : 90

DESC Sorted:
acmfly : 96
alan : 95
hikerell : 91
leao : 90

IS Sorted DESC? true
pos=4
s不包含元素, xStu={alan 995}

4.2.2 使用Reverse方法

代码示例：

package main

import (
	"fmt"
	"sort"
)

//学生成绩结构体
type StuScore struct {
	//姓名
	name  string
	//成绩
	score int
}

type StuScores []StuScore

//Len()
func (s StuScores) Len() int {
	return len(s)
}

//Less():成绩将有低到高排序（升序）
func (s StuScores) Less(i, j int) bool {
	return s[i].score < s[j].score
}

//Swap()
func (s StuScores) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func main() {
	stus := StuScores{
		{"alan", 95},
		{"hikerell", 91},
		{"acmfly", 96},
		{"leao", 90}}

	fmt.Println("Default:")
	// 原始顺序
	for _, v := range stus {
		fmt.Println(v.name, ":", v.score)
	}
	fmt.Println()

	//StuScores已经实现了sort.Interface接口
	sort.Sort(stus)

	fmt.Println("ASC Sorted:")
	// 排好序后的结构
	for _, v := range stus {
		fmt.Println(v.name, ":", v.score)
	}
	fmt.Println()

	// 判断是否升序排序
	fmt.Println("IS Sorted ASC?", sort.IsSorted(stus))
	fmt.Println()

	// 反转排序结果
	fmt.Println("Reverse Sorted(DESC):")
	sort.Sort(sort.Reverse(stus))
	for _, v := range stus {
		fmt.Println(v.name, ":", v.score)
	}

	// 判断是否降序排序
	fmt.Println("IS Sorted ASC?", sort.IsSorted(stus))

	// 查找指定值是否在降序的slice中
	xStu := StuScore{
		name:"alan",
		score:95,
	}
	// 降序搜索
	pos := sort.Search(len(stus), func(i int) bool { return stus[i].score <= xStu.score })
	fmt.Printf("pos=%v\n", pos)
	if (pos < len(stus)) && (stus[pos].score == xStu.score) {
		fmt.Println(xStu, "在s中的位置为：", pos)
	} else {
		fmt.Printf("s不包含元素, xStu=%v\n", xStu)
	}

}

运行结果：

Default:
alan : 95
hikerell : 91
acmfly : 96
leao : 90

ASC Sorted:
leao : 90
hikerell : 91
alan : 95
acmfly : 96

IS Sorted ASC? true

Reverse Sorted(DESC):
acmfly : 96
alan : 95
hikerell : 91
leao : 90
IS Sorted ASC? false
pos=1
{alan 95} 在s中的位置为：1

4.3 查找整形数在升序切片中的位置

代码示例：

package main

import (
        "fmt"
        "sort"
)

func main()  {
        //查找指定值是否在升序的slice中
        x := 4
        s := []int{4, 7, 9, 13, 49} //注意已经升序排序
        xpos := sort.Search(len(s), func(i int) bool { return s[i] >= x })
        fmt.Printf("pos=%v\n", xpos)
        if (xpos < len(s)) && (s[xpos] == x) {
                fmt.Println(x, "在s中的位置为：", xpos)
        } else {
                fmt.Println("s不包含元素", x)
        }
}

运行结果：

pos=0
4 在s中的位置为： 0