golang sort包应用

标签：sort 应用 people int fmt golang func 升序

一、sort内置排序函数

函数	作用
func Float64s(x []float64)	对float64类型的切片进行升序排序
func Float64sAreSorted(x []float64) bool	判断float64类型切片x是否按升序排序
func Ints(x []int)	对int类型的切片进行升序排序
func IntsAreSorted(x []int) bool	判断int类型切片x是否按升序排序
func SearchFloat64s(a []float64, x float64) int	切片a必须是已按升序排序，二分查找，若x存在a中，则返回a的位置，否则返回可以插入的位置，可以是len(a)
func SearchInts(a []int, x int) int	同SearchFloat64s，查找的类型为int类型切片
func SearchStrings(a []string, x string) int	同SearchFloat64s，查找切片类型为string

二、sort内置排序函数使用

func Float64s 和 func Float64sAreSorted

package main

import (
	"fmt"
	"math"
	"sort"
)

func main() {
	s := []float64{5.2, -1.3, 0.7, -3.8, 2.6}              // unsorted
	fmt.Println("are sorted: ", sort.Float64sAreSorted(s)) // are sorted:  false
	sort.Float64s(s)
	fmt.Println("are sorted: ", sort.Float64sAreSorted(s)) // are sorted:  true
	fmt.Println(s)                                         // [-3.8 -1.3 0.7 2.6 5.2]

	s = []float64{math.Inf(1), math.NaN(), math.Inf(-1), 0.0} // unsorted
	fmt.Println("are sorted: ", sort.Float64sAreSorted(s))    // are sorted:  false
	sort.Float64s(s)
	fmt.Println("are sorted: ", sort.Float64sAreSorted(s)) // are sorted:  true
	fmt.Println(s)                                         // [NaN -Inf 0 +Inf]

}

func Ints 和 func IntsAreSorted

package main

import (
	"fmt"
	"sort"
)

func main() {
	s := []int{5, 2, 6, 3, 1, 4}                     // unsorted
	fmt.Println("are sort: ", sort.IntsAreSorted(s)) //are sort:  false
	sort.Ints(s)
	fmt.Println("are sort: ", sort.IntsAreSorted(s)) //are sort:  true
	fmt.Println(s)                                   //[1 2 3 4 5 6]
}

func SearchFloat64s

package main

import (
	"fmt"
	"sort"
)

func main() {
	a := []float64{1.0, 2.0, 3.3, 4.6, 6.1, 7.2, 8.0} //已经按升序排好序的切片

	x := 2.0
	i := sort.SearchFloat64s(a, x) //查找存在的元素，返回元素所在的下标
	fmt.Printf("found %g at index %d in %v\n", x, i, a)
	//found 2 at index 1 in [1 2 3.3 4.6 6.1 7.2 8]

	x = 0.5
	i = sort.SearchFloat64s(a, x) //查找元素不存在，返回可以插入的位置
	fmt.Printf("%g not found, can be inserted at index %d in %v\n", x, i, a)
	//0.5 not found, can be inserted at index 0 in [1 2 3.3 4.6 6.1 7.2 8]
}

func SearchInts
效果同SearchFloat64s，查找切片类型为int

package main

import (
	"fmt"
	"sort"
)


func main() {
	a := []int{1, 2, 3, 4, 6, 7, 8}

	x := 2
	i := sort.SearchInts(a, x)
	fmt.Printf("found %d at index %d in %v\n", x, i, a)

	x = 5
	i = sort.SearchInts(a, x)
	fmt.Printf("%d not found, can be inserted at index %d in %v\n", x, i, a)
}

func SearchStrings

package main

import (
	"fmt"
	"sort"
)

func main() {
	//已按升序排好序的切片a
	a := []string{"a", "abb", "acc", "bb", "c", "ca"}

	x := "bb"
	i := sort.SearchStrings(a, x)
	fmt.Printf("found %s at index %d in %v\n", x, i, a)
	//found bb at index 3 in [a abb acc bb c ca]

	x = "aaa"
	i = sort.SearchStrings(a, x)
	fmt.Printf("%s not found, can be inserted at index %d in %v\n", x, i, a)
	//aaa not found, can be inserted at index 1 in [a abb acc bb c ca]
}

三、自定义排序方式

sort包提供了俩种方式自定义结构类型切片排序，调用sort.Sort和sort.Slice

sort.Sort方式，使用sort.Sort函数，结构类型需要sort.Interface接口以提供函数调用
- func (t type) Len() int { ... } //需要返回切片长度
- func (t type) Less(i,j int) bool {...} //返回true, i所在元素排j在前面，false i所在元素排j在后面
- func (t type) Swap(i, j int) {....} // 实现交换

package main

import (
	"fmt"
	"sort"
)
//自定义结构类型
type Person struct {
	Name string
	Age  int
}

func (p Person) String() string {
	return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

// ByAge implements sort.Interface for []Person based on
// the Age field.
type ByAge []Person

// 实现sort.Interface 接口
func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age } //按照Age升序排序

func main() {
	people := []Person{
		{"Bob", 31},
		{"John", 42},
		{"Michael", 17},
		{"Jenny", 26},
	}

	fmt.Println(people)
	//[Bob: 31 John: 42 Michael: 17 Jenny: 26]
	sort.Sort(ByAge(people))
	fmt.Println(people)
	//[Michael: 17 Jenny: 26 Bob: 31 John: 42]
}

sort.Slice方式只需要传入比较函数，这种方式跟其他编程语言（python，C++...)所提供的sort排序方式类似

type Person struct {
	Name string
	Age  int
}
//使用sort.Slice 有无定义sort.Interface接口都会被忽略
func (p Person) String() string {
	return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

func main() {
	people := []Person{
		{"Bob", 31},
		{"John", 42},
		{"Michael", 17},
		{"Jenny", 26},
	}
	sort.Slice(people, func(i, j int) bool {
		return people[i].Age < people[j].Age
	})
	//按照年龄升序
	fmt.Printf("%v\n", people)
	//[Michael: 17 Jenny: 26 Bob: 31 John: 42]

	people = []Person{
		{"Bob", 31},
		{"John", 42},
		{"Michael", 17},
		{"Jenny", 26},
	}
	sort.Slice(people, func(i, j int) bool {
		return people[i].Age > people[j].Age
	})
	//按照年龄降序
	fmt.Printf("%v", people)
	//[John: 42 Bob: 31 Jenny: 26 Michael: 17]
}

四、sort.Sort排序方式封装

当一个结构类型需要多种不同的排序方式时，可以封装一层ByType类型来实现比较接口 Less

package main

import (
	"fmt"
	"sort"
)

type Person struct {
	Name string
	Age  int
}

func (p Person) String() string {
	return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

type Persons []*Person

// 实现sort.Interface 接口
func (p Persons) Len() int      { return len(p) }
func (p Persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }

//封装定义多种比较方式类型
// 按年龄升序方式排序
type ByAge struct{ Persons }

func (b ByAge) Less(i, j int) bool { return b.Persons[i].Age < b.Persons[j].Age }

// 按名称字典序升序
type ByName struct{ Persons }

func (b ByName) Less(i, j int) bool { return b.Persons[i].Name < b.Persons[j].Name }

func main() {
	people := []*Person{
		{"Bob", 31},
		{"John", 42},
		{"Michael", 17},
		{"Jenny", 26},
	}

	//按照年龄升序
	sort.Sort(ByAge{people})
	fmt.Printf("%v\n", people)
	//[Michael: 17 Jenny: 26 Bob: 31 John: 42]

	people = []*Person{
		{"Bob", 31},
		{"John", 42},
		{"Michael", 17},
		{"Jenny", 26},
	}

	//按照名称字典序升序排序
	sort.Sort(ByName{people})
	fmt.Printf("%v", people)
	//[Bob: 31 Jenny: 26 John: 42 Michael: 17]
}

五、自定义搜索函数func Search

func Search(n int, f func(int) bool) int
可以用来实现在升序序列中找到第一个大于等于或大于的元素位置(如C++中的lower_bound,upper_bound函数，或python中的bisect.bisect_left,bisect.bisect_right方法)
或者在降序队列中找到第一个小于等于或小于的元素位置

package main

import (
	"fmt"
	"sort"
)

func main() {
	a := []int{1, 2, 3, 4, 5, 6, 7}
	//在升序队列中找到第一个大于等于3的位置
	x := 3
	pos := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	fmt.Println("pos ", pos) // 2

	//在升序队列中找到第一个大于3的位置
	pos = sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	fmt.Println("pos ", pos) // 3

	//降序排序
	sort.Slice(a, func(i, j int) bool {
		return a[i] > a[j]
	})
	fmt.Println(a) //[7 6 5 4 3 2 1]
	//在降序队列中找到第一个小于等于3的位置
	pos = sort.Search(len(a), func(i int) bool {
		return a[i] <= x
	})
	fmt.Println("pos ", pos) // 4

	//在降序队列中找到第一个小于3的位置
	pos = sort.Search(len(a), func(i int) bool {
		return a[i] < x
	})
	fmt.Println("pos ", pos) // 5
}

六、逆序排序 func Reverse

这里的逆序是相对的，假如定义的升序排序，那么反转后就是降序，定义的降序，反转后就是升序

package main

import (
	"fmt"
	"sort"
)

type Person struct {
	Name string
	Age  int
}

func (p Person) String() string {
	return fmt.Sprintf("%s: %d", p.Name, p.Age)
}

type Persons []*Person

// 实现sort.Interface 接口
func (p Persons) Len() int      { return len(p) }
func (p Persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }

// 按年龄升序方式排序
type ByAge struct{ Persons }

func (b ByAge) Less(i, j int) bool { return b.Persons[i].Age < b.Persons[j].Age }

// 按名称字典序升序
type ByName struct{ Persons }

func (b ByName) Less(i, j int) bool { return b.Persons[i].Name < b.Persons[j].Name }

func main() {
	people := []*Person{
		{"Bob", 31},
		{"John", 42},
		{"Michael", 17},
		{"Jenny", 26},
	}

	//按照年龄升序 逆序后按照年龄降序
	sort.Sort(sort.Reverse(ByAge{people}))
	fmt.Printf("%v\n", people)
	//[John: 42 Bob: 31 Jenny: 26 Michael: 17]

	people = []*Person{
		{"Bob", 31},
		{"John", 42},
		{"Michael", 17},
		{"Jenny", 26},
	}

	//按照名称字典序升序排序, 逆序后按照降序排序
	sort.Sort(sort.Reverse(ByName{people}))
	fmt.Printf("%v", people)
	//[Michael: 17 John: 42 Jenny: 26 Bob: 31]
}

七、总结

一般情况下int或float64类型的切片使用内置函数sort.Ints和sort.Float64s进行排序，以及使用SearchInts和SearchFloats进行查找
自定义的数据类型排序可以使用sort.Sort需要定义sort.Interface接口或者使用sort.Slice函数提供比较函数进行排序
对于同种数据类型多个不同类型排序方式，可以通过封装多个Less接口来进行实现
使用Search函数可以实现C++中upper_bound和lower_bound函数二分查找功能
对于已经定义的排序方式，使用sort.Reverse可以反转排序的方式

八、参考

https://pkg.go.dev/sort

标签：sort,应用,people,int,fmt,golang,func,升序
From： https://www.cnblogs.com/chen-pi/p/17852731.html