一、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可以反转排序的方式