Go 提供了sort
包来协助排序、搜寻任务,对于[]int
、[]float64
与[]string
,可以透过Ints
、Float64s
、Strings
来由小而大排序,可以使用IntsAreSorted
、Float64sAreSorted
、StringsAreSorted
来看看是否已经排序。
若想在已由小而大排序的[]int
、[]float64
与[]string
中进行搜寻,可以使用SearchInts
、SearchFloat64s
、SearchStrings
函数,搜寻结果将返回找到搜寻值的索引位置,没有搜寻到的话,返回的会是可以安插搜寻值的索引位置。例如:
package main
import (
"fmt"
"sort"
)
func main() {
s := []int{8, 2, 6, 3, 1, 4}
sort.Ints(s)
fmt.Println(sort.IntsAreSorted(s)) // true
fmt.Println(s) // [1 2 3 4 6 8]
fmt.Println(sort.SearchInts(s, 7)) // 5
}
如果想要由大而小排序呢?可以透过Slice
、SliceStable
,指定一个less
函数,该函数接受两个索引,你要返回布尔值表示i
处的值顺序上是否小于j
:
package main
import (
"fmt"
"sort"
)
func main() {
s := []int{8, 2, 6, 3, 1, 4}
sort.Slice(s, func(i, j int) bool {
return s[i] > s[j]
})
fmt.Println(s) // [8 6 4 3 2 1]
}
实际上,Slice
、SliceStable
可用于任意的结构,例如:
package main
import (
"fmt"
"sort"
)
func main() {
family := []struct {
Name string
Age int
} {{"Irene", 12}, {"Justin", 45}, {"Monica", 42}}
// 依年龄由小而大排序
sort.SliceStable(family, func(i, j int) bool {
return family[i].Age < family[j].Age
})
fmt.Println(family) // [{Irene 12} {Monica 42} {Justin 45}]
}
那么怎么搜寻上面的family
呢?例如,找出年龄 45 岁的数据?这可以用Search
,例如:
package main
import (
"fmt"
"sort"
)
func main() {
family := []struct {
Name string
Age int
} {{"Irene", 12}, {"Justin", 45}, {"Monica", 42}}
// 依年龄由小而大排序
sort.SliceStable(family, func(i, j int) bool {
return family[i].Age < family[j].Age
})
fmt.Println(family) // [{Irene 12} {Monica 42} {Justin 45}]
idx := sort.Search(len(family), func (i int) bool {
return family[i].Age == 45
})
fmt.Println(idx)
}
Search
会使用二分搜寻,第二个参数指定的函数要返回布尔值,表示是否符合搜寻条件,若找到第一个符合的话返回索引位置,否则返回第一个参数指定的值。
在Search说明中,还有个猜数字的有趣范例,由程序猜出你心中想的数字:
func GuessingGame() {
var s string
fmt.Printf("Pick an integer from 0 to 100.\n")
answer := sort.Search(100, func(i int) bool {
fmt.Printf("Is your number <= %d? ", i)
fmt.Scanf("%s", &s)
return s != "" && s[0] == 'y'
})
fmt.Printf("Your number is %d.\n", answer)
}
sort
还提供了Sort
、Stable
函数,乍看很奇怪:
func Sort(data Interface)
func Stable(data Interface)
Interface
的定义是:
type Interface interface {
Len() int
Less(i, j int) bool
Swap(i, j int)
}
这是给有序、具索引的数据结构实现的行为,任何具有Interface
行为的数据结构,都可以透过Sort
、Stable
函数排序,sort
包提供的实现有IntSlice
、Float64Slice
、StringSlice
,以IntSlice
的源码实现为例:
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] }
因此,若要对整数排序,也可以如下:
package main
import (
"fmt"
"sort"
)
func main() {
s := sort.IntSlice([]int{8, 2, 6, 3, 1, 4})
sort.Sort(s)
fmt.Println(s) // [1 2 3 4 6 8]
}
实际上,Ints
、Float64s
、Strings
函数,内部也只是转换为IntSlice
、Float64Slice
、StringSlice
,然后调用Sort
罢了:
func Ints(a []int) { Sort(IntSlice(a)) }
func Float64s(a []float64) { Sort(Float64Slice(a)) }
func Strings(a []string) { Sort(StringSlice(a)) }
对于一个实现了Interface
的数据结构,除了可以使用Sort
、Stable
函数外,若需要反向排序,可以有个简单方式,透过Reverse
来包裹。例如:
package main
import (
"fmt"
"sort"
)
func main() {
s := sort.IntSlice([]int{8, 2, 6, 3, 1, 4})
sort.Sort(sort.Reverse(s))
fmt.Println(s) // [8 6 4 3 2 1]
}
有趣的是Reverse
的实现,它不过就是将给原本数据结构Less
方法的i
、j
对调罢了:
type reverse struct {
Interface
}
func (r reverse) Less(i, j int) bool {
return r.Interface.Less(j, i)
}
func Reverse(data Interface) Interface {
return &reverse{data}
}
来自己实现一下Interface
,使用家人的年龄来排序:
package main
import (
"fmt"
"sort"
)
type Person struct {
Name string
Age int
}
type Family []Person
func (f Family) Len() int {
return len(f)
}
func (f Family) Less(i, j int) bool {
return f[i].Age < f[j].Age
}
func (f Family) Swap(i, j int) {
f[i], f[j] = f[j], f[i]
}
func main() {
family := Family{{"Irene", 12}, {"Justin", 45}, {"Monica", 42}}
sort.Sort(family)
fmt.Println(family) // [{Irene 12} {Monica 42} {Justin 45}]
sort.Sort(sort.Reverse(family))
fmt.Println(family) // [{Justin 45} {Monica 42} {Irene 12}]
}