一、简介
sort 包 在内部实现了四种基本的排序算法：插入排序（insertionSort）、归并排序（symMerge）、堆排序（heapSort）和快速排序（quickSort）； sort 包会依据实际数据自动选择最优的排序算法。所以我们写代码时只需要考虑实现 sort.Interface 这个类型就可以了。
func Sort(data Interface) {
// Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached.
n := data.Len()
maxDepth := 0
for i := n; i > 0; i >>= 1 {
maxDepth++
}
maxDepth *= 2
quickSort(data, 0, n, maxDepth)
}
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less reports whether the element with
// index i should sort before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
// 内部实现的四种排序算法
// 插入排序
func insertionSort(data Interface, a, b int)
// 堆排序
func heapSort(data Interface, a, b int)
// 快速排序
func quickSort(data Interface, a, b, maxDepth int)
// 归并排序
func symMerge(data Interface, a, m, b int)
二、常用类型内置排序方法
对常见类型int,float64,string，官方提供了内置的排序：
// Ints sorts a slice of ints in increasing order.
func Ints(a []int) { Sort(IntSlice(a)) }
// Float64s sorts a slice of float64s in increasing order
// (not-a-number values are treated as less than other values).
func Float64s(a []float64) { Sort(Float64Slice(a)) }
// Strings sorts a slice of strings in increasing order.
func Strings(a []string) { Sort(StringSlice(a)) }
// IntsAreSorted tests whether a slice of ints is sorted in increasing order.
func IntsAreSorted(a []int) bool { return IsSorted(IntSlice(a)) }
// Float64sAreSorted tests whether a slice of float64s is sorted in increasing order
// (not-a-number values are treated as less than other values).
func Float64sAreSorted(a []float64) bool { return IsSorted(Float64Slice(a)) }
// StringsAreSorted tests whether a slice of strings is sorted in increasing order.
func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) }
比如可以这样用：
b := []float64{1.1, 2.3, 5.3, 3.4}
sort.Float64s(b)
fmt.Println(b)
-----------
[1.1 2.3 3.4 5.3]
看一下Float64Slice:
// Float64Slice attaches the methods of Interface to []float64, sorting in increasing order
// (not-a-number values are treated as less than other values).
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] }
注释中写得清楚，这样实现这三个接口，递增排序。从打印结果来看，确实是递增的。
对于未提供的内置类型排序，sort模块提供了一个非常灵活的函数sort.Slice(slice interface{}, less func(i, j int) bool),第一个参数是要排序的切片.第二个参数是一个函数,函数接收两个index值,返回 slice[ I] < slice[j]这个bool值.
func main() {
a := []uint64{5, 9, 8, 3, 1, 100, 0}
fmt.Println(a)
sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })
fmt.Println(a)
}
三、自定义一个排序
package main
import (
"fmt"
"sort"
)
type Person struct {
Name string
Age int
}
type Persons []Person
// 获取此 slice 的长度
func (p Persons) Len() int { return len(p) }
// 根据元素的年龄降序排序 （此处按照自己的业务逻辑写）
func (p Persons) Less(i, j int) bool {
return p[i].Age > p[j].Age
}
// 交换数据
func (p Persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func main() {
persons := Persons{
{
Name: "test1",
Age: 20,
},
{
Name: "test2",
Age: 22,
},
{
Name: "test3",
Age: 21,
},
}
fmt.Println("排序前")
for _, person := range persons {
fmt.Println(person.Name, ":", person.Age)
}
sort.Sort(persons)
fmt.Println("排序后")
for _, person := range persons {
fmt.Println(person.Name, ":", person.Age)
}
}
注意Less方法中，变成大于号了，所以是降序排列了。
当我们对某一个结构体中多个字段进行排序时怎么办，难道每排序一个就写下这三个方法么，当然不是。我们可以利用嵌套结构体来解决这个问题。因为嵌套结构体可以继承父结构体的所有属性和方法。比如我想对上面 Person 的 Name 字段和 Age 对要排序，我们可以利用嵌套结构体来改进一下。
package main
import (
"fmt"
"sort"
)
type Person struct {
Name string
Age int
}
type Persons []Person
// Len()方法和Swap()方法不用变化
// 获取此 slice 的长度
func (p Persons) Len() int { return len(p) }
// 交换数据
func (p Persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
// 嵌套结构体 将继承 Person 的所有属性和方法
// 所以相当于SortByName 也实现了 Len() 和 Swap() 方法
type SortByName struct{ Persons }
// 根据元素的姓名长度降序排序 （此处按照自己的业务逻辑写）
func (p SortByName) Less(i, j int) bool {
return len(p.Persons[i].Name) > len(p.Persons[j].Name)
}
type SortByAge struct{ Persons }
// 根据元素的年龄降序排序 （此处按照自己的业务逻辑写）
func (p SortByAge) Less(i, j int) bool {
return p.Persons[i].Age > p.Persons[j].Age
}
func main() {
persons := Persons{
{
Name: "test123",
Age: 20,
},
{
Name: "test1",
Age: 22,
},
{
Name: "test12",
Age: 21,
},
}
fmt.Println("排序前")
for _, person := range persons {
fmt.Println(person.Name, ":", person.Age)
}
sort.Sort(SortByName{persons})
fmt.Println("排序后")
for _, person := range persons {
fmt.Println(person.Name, ":", person.Age)
}
}
四、sort.Slice
sort包中有sort.Slice函数专门用于slice的排序，使用极简单方便
package main
import (
"fmt"
"sort"
)
/*slice 简单排序示例*/
func main() {
//定义一个年龄列表
ageList := []int{1, 3, 7, 7, 8, 2, 5}
//排序，实现比较方法即可
sort.Slice(ageList, func(i, j int) bool {
return ageList[i] < ageList[j]
})
fmt.Printf("after sort:%v", ageList)
}
//输出 after sort:[1 2 3 5 7 7 8]
1.其中使用到了反射（reflect）包
241 // Slice sorts the provided slice given the provided less function.
242 //
243 // The sort is not guaranteed to be stable. For a stable sort, use
244 // SliceStable.
245 //
246 // The function panics if the provided interface is not a slice.
247 func Slice(slice interface{}, less func(i, j int) bool) {
248 rv := reflect.ValueOf(slice)
249 swap := reflect.Swapper(slice)
250 length := rv.Len()
251 quickSort_func(lessSwap{less, swap}, 0, length, maxDepth(length))
252 }
2.使用了闭包
swap := reflect.Swapper(slice)
// Swapper returns a function that swaps the elements in the provided
10 // slice.
11 //
12 // Swapper panics if the provided interface is not a slice.
13 func Swapper(slice interface{}) func(i, j int) {
14 v := ValueOf(slice)
15 if v.Kind() != Slice {
16 panic(&ValueError{Method: "Swapper", Kind: v.Kind()})
17 }
..................此处省略部分代码
62 tmp := unsafe_New(typ) // swap scratch space
63
64 return func(i, j int) {
65 if uint(i) >= uint(s.Len) || uint(j) >= uint(s.Len) {
66 panic("reflect: slice index out of range")
67 }
68 val1 := arrayAt(s.Data, i, size)
69 val2 := arrayAt(s.Data, j, size)
70 typedmemmove(typ, tmp, val1)
71 typedmemmove(typ, val1, val2)
72 typedmemmove(typ, val2, tmp)
73 }
74 }
3.可以参考何时使用panic
250 length := rv.Len()
1019 // Len returns v's length.
1020 // It panics if v's Kind is not Array, Chan, Map, Slice, or String.
1021 func (v Value) Len() int {
1022 k := v.kind()
1023 switch k {
1024 case Array:
1025 tt := (*arrayType)(unsafe.Pointer(v.typ))
1026 return int(tt.len)
1027 case Chan:
1028 return chanlen(v.pointer())
1029 case Map:
1030 return maplen(v.pointer())
1031 case Slice:
1032 // Slice is bigger than a word; assume flagIndir.
1033 return (*sliceHeader)(v.ptr).Len
1034 case String:
1035 // String is bigger than a word; assume flagIndir.
1036 return (*stringHeader)(v.ptr).Len
1037 }
1038 panic(&ValueError{"reflect.Value.Len", v.kind()})
1039 }
4.quickSort函数设计学习，同时使用了heapsort、insertionSort和单次希尔排序
135 // Auto-generated variant of sort.go:quickSort
136 func quickSort_func(data lessSwap, a, b, maxDepth int) {
137 for b-a > 12 {
138 if maxDepth == 0 {
139 heapSort_func(data, a, b)
140 return
141 }
142 maxDepth--
143 mlo, mhi := doPivot_func(data, a, b)
144 if mlo-a < b-mhi {
145 quickSort_func(data, a, mlo, maxDepth)
146 a = mhi
147 } else {
148 quickSort_func(data, mhi, b, maxDepth)
149 b = mlo
150 }
151 }
152 if b-a > 1 {
153 for i := a + 6; i < b; i++ {
154 if data.Less(i, i-6) {
155 data.Swap(i, i-6)
156 }
157 }
158 insertionSort_func(data, a, b)
159 }
160 }
5.合法性处理
// Swapper returns a function that swaps the elements in the provided
10 // slice.
11 //
12 // Swapper panics if the provided interface is not a slice.
13 func Swapper(slice interface{}) func(i, j int) {
14 ...........省略部分代码
18 // Fast path for slices of size 0 and 1. Nothing to swap.
19 switch v.Len() {
20 case 0:
21 return func(i, j int) { panic("reflect: slice index out of range") }
22 case 1:
23 return func(i, j int) {
24 if i != 0 || j != 0 {
25 panic("reflect: slice index out of range")
26 }
27 }
28 }
网友评论