www.zhblog.net

sort 包


Go 提供了sort包来协助排序、搜寻任务,对于[]int[]float64[]string,可以透过IntsFloat64sStrings来由小而大排序,可以使用IntsAreSortedFloat64sAreSortedStringsAreSorted来看看是否已经排序。

若想在已由小而大排序的[]int[]float64[]string中进行搜寻,可以使用SearchIntsSearchFloat64sSearchStrings函数,搜寻结果将返回找到搜寻值的索引位置,没有搜寻到的话,返回的会是可以安插搜寻值的索引位置。例如:

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
}

如果想要由大而小排序呢?可以透过SliceSliceStable,指定一个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]
}

实际上,SliceSliceStable可用于任意的结构,例如:

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还提供了SortStable函数,乍看很奇怪:

func Sort(data Interface)
func Stable(data Interface)

Interface的定义是:

type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

这是给有序、具索引的数据结构实现的行为,任何具有Interface行为的数据结构,都可以透过SortStable函数排序,sort包提供的实现有IntSliceFloat64SliceStringSlice,以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]
}

实际上,IntsFloat64sStrings函数,内部也只是转换为IntSliceFloat64SliceStringSlice,然后调用Sort罢了:

func Ints(a []int) { Sort(IntSlice(a)) }
func Float64s(a []float64) { Sort(Float64Slice(a)) }
func Strings(a []string) { Sort(StringSlice(a)) }

对于一个实现了Interface的数据结构,除了可以使用SortStable函数外,若需要反向排序,可以有个简单方式,透过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方法的ij对调罢了:

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}]
}




展开阅读全文

评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 心情