《Go语言四十二章经》第二十九章 排序(sort)

栏目: Go · 发布时间: 5年前

内容简介:《Go语言四十二章经》第二十九章 排序(sort)作者:李骁Go语言标准库sort包中实现了3种基本的排序算法:插入排序、快排和堆排序。和其他语言中一样,这三种方式都是不公开的,他们只在sort包内部使用。所以用户在使用sort包进行排序时无需考虑使用那种排序方式,sort.Interface定义的三个方法:获取数据集合长度的Len()方法、比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法,就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。

《Go语言四十二章经》第二十九章 排序(sort)

作者:李骁

29.1 sort包介绍

Go语言标准库sort包中实现了3种基本的 排序 算法:插入排序、快排和堆排序。和其他语言中一样,这三种方式都是不公开的,他们只在sort包内部使用。所以用户在使用sort包进行排序时无需考虑使用那种排序方式,sort.Interface定义的三个方法:获取数据集合长度的Len()方法、比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法,就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。

type Interface
type Interface interface {

    Len() int    // Len 为集合内元素的总数  
    Less(i, j int) bool //如果index为i的元素小于index为j的元素,则返回true,否则false
    Swap(i, j int)  // Swap 交换索引为 i 和 j 的元素
}

sort包里面已经实现了[]int, []float64, []string的排序。

任何实现了 sort.Interface 的类型(一般为集合),均可使用该包中的方法进行排序。这些方法要求集合内列出元素的索引为整数。

package main

import (
	"fmt"
	"sort"
)

func main() {
	a := []int{3, 5, 4, -1, 9, 11, -14}
	sort.Ints(a)
	fmt.Println(a)
	ss := []string{"surface", "ipad", "mac pro", "mac air", "think pad", "idea pad"}
	sort.Strings(ss)
	fmt.Println(ss)
	sort.Sort(sort.Reverse(sort.StringSlice(ss)))
	fmt.Printf("After reverse: %v\n", ss)
}
程序输出:
[-14 -1 3 4 5 9 11]
[idea pad ipad mac air mac pro surface think pad]
After reverse: [think pad surface mac pro mac air ipad idea pad]

默认结果都是升序排列,如果我们想对一个 sortable object 进行逆序排序,可以自定义一个type。但 sort.Reverse 帮你省掉了这些代码。

package main

import (
	"fmt"
	"sort"
)

func main() {
	a := []int{4, 3, 2, 1, 5, 9, 8, 7, 6}
	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	fmt.Println("After reversed: ", a)
}
程序输出:
After reversed:  [9 8 7 6 5 4 3 2 1]

相关方法:

// 将类型为float64的slice以升序方式排序
func Float64s(a []float64)   

// 判定是否已经进行排序func Ints(a []int)
func Float64sAreSorted(a []float64) bool 

// Ints 以升序排列 int 切片。
func Ints(a []int)                  

// 判断 int 切片是否已经按升序排列。
func IntsAreSorted(a []int) bool 

//IsSorted 判断数据是否已经排序。包括各种可sort的数据类型的判断.
func IsSorted(data Interface) bool    


//Strings 以升序排列 string 切片。
func Strings(a []string)

//判断 string 切片是否按升序排列
func StringsAreSorted(a []string) bool

// search使用二分法进行查找,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(而不是返回-1)。
//
// Search 常用于在一个已排序的,可索引的数据结构中寻找索引为 i 的值 x,例如数组或切片。
// 这种情况下实参 f一般是一个闭包,会捕获所要搜索的值,以及索引并排序该数据结构的方式。
func Search(n int, f func(int) bool) int   

// SearchFloat64s 在float64s切片中搜索x并返回索引如Search函数所述. 
// 返回可以插入x值的索引位置,如果x不存在,返回数组a的长度切片必须以升序排列
func SearchFloat64s(a []float64, x float64) int  

// SearchInts 在ints切片中搜索x并返回索引如Search函数所述. 返回可以插入x值的
// 索引位置,如果x不存在,返回数组a的长度切片必须以升序排列
func SearchInts(a []int, x int) int 

// SearchFloat64s 在strings切片中搜索x并返回索引如Search函数所述. 返回可以
// 插入x值的索引位置,如果x不存在,返回数组a的长度切片必须以升序排列
func SearchStrings(a []string, x string) int

// 其中需要注意的是,以上三种search查找方法,其对应的slice必须按照升序进行排序,
// 否则会出现奇怪的结果.

// Sort 对 data 进行排序。它调用一次 data.Len 来决定排序的长度 n,调用 data.Less 
// 和 data.Swap 的开销为O(n*log(n))。此排序为不稳定排序。他根据不同形式决定使用
// 不同的排序方式(插入排序,堆排序,快排)。
func Sort(data Interface)

// Stable对data进行排序,不过排序过程中,如果data中存在相等的元素,则他们原来的
// 顺序不会改变,即如果有两个相等元素num, 他们的初始index分别为i和j,并且i<j,
// 则利用Stable对data进行排序后,i依然小于j.直接利用sort进行排序则不能够保证这一点。
func Stable(data Interface)

29.2 自定义sort.Interface排序

如果是具体的某个结构体的排序,就需要自己实现Interface了。

package main

import (
	"fmt"
	"sort"
)

type person struct {
	Name string
	Age  int
}

type personSlice []person

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

func main() {
	a := personSlice{
		{
			Name: "AAA", 
			Age:  55, 
		}, 
		{
			Name: "BBB", 
			Age:  22, 
		}, 
		{
			Name: "CCC", 
			Age:  0, 
		}, 
		{
			Name: "DDD", 
			Age:  22, 
		}, 
		{
			Name: "EEE", 
			Age:  11, 
		}, 
	}
	sort.Sort(a)
	fmt.Println("Sort:", a)

	sort.Stable(a)
	fmt.Println("Stable:", a)

}
程序输出:

Sort: [{CCC 0} {EEE 11} {BBB 22} {DDD 22} {AAA 55}]
Stable: [{CCC 0} {EEE 11} {BBB 22} {DDD 22} {AAA 55}]

29.3 sort.Slice

利用sort.Slice 函数,而不用提供一个特定的 sort.Interface 的实现,而是 Less(i,j int) 作为一个比较回调函数,可以简单地传递给 sort.Slice 进行排序。

package main

import (
	"fmt"
	"sort"
)

type Peak struct {
	Name      string
	Elevation int // in feet
}

func main() {
	peaks := []Peak{
		{"Aconcagua", 22838}, 
		{"Denali", 20322}, 
		{"Kilimanjaro", 19341}, 
		{"Mount Elbrus", 18510}, 
		{"Mount Everest", 29029}, 
		{"Mount Kosciuszko", 7310}, 
		{"Mount Vinson", 16050}, 
		{"Puncak Jaya", 16024}, 
	}

	// does an in-place sort on the peaks slice, with tallest peak first
	sort.Slice(peaks, func(i, j int) bool {
		return peaks[i].Elevation >= peaks[j].Elevation
	})
	fmt.Println(peaks)

}
程序输出:
[{Mount Everest 29029} {Aconcagua 22838} {Denali 20322} {Kilimanjaro 19341} {Mount Elbrus 18510} {Mount Vinson 16050} {Puncak Jaya 16024} {Mount Kosciuszko 7310}]

本书《Go语言四十二章经》内容在github上同步地址:https://github.com/ffhelicopter/Go42

本书《Go语言四十二章经》内容在简书同步地址: https://www.jianshu.com/nb/29056963

虽然本书中例子都经过实际运行,但难免出现错误和不足之处,烦请您指出;如有建议也欢迎交流。


以上所述就是小编给大家介绍的《《Go语言四十二章经》第二十九章 排序(sort)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Algorithms in C (Computer Science Series)

Algorithms in C (Computer Science Series)

Robert Sedgewick / Addison-Wesley Professional / 1990-01-11 / USD 59.99

This new version of the best-selling book, Algorithms, SecondEdition, provides a comprehensive collection of algorithmsimplemented in C. A variety of algorithms are described in eachofthe following ar......一起来看看 《Algorithms in C (Computer Science Series)》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换