golang标准库之sort

简介

标准库sort实现了4种排序方法，插入排序、堆排序、快排和归并排序，但是并没有暴露给用户接口。sort包会根据数据选择最优的排序方法(其实只使用了3种，归并排序除外)。

接口

用户需要实现以下接口才能使用sort包的排序功能。

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

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

func IsSorted(data Interface) bool { // 当前排序与Less()方法排序一致返回True
    n := data.Len()
    for i := n - 1; i > 0; i-- {
        if data.Less(i, i-1) {
            return false
        }
    }
    return true
}

内置类型支持

对于常用的类型(整型切片、float64切片、String切片)，sort包提供了内置的接口实现

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

func (p IntSlice) Sort() { Sort(p) }

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

func isNaN(f float64) bool {
    return f != f
}

func (p Float64Slice) Sort() { Sort(p) }

type StringSlice []string

func (p StringSlice) Len() int           { return len(p) }
func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p StringSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func (p StringSlice) Sort() { Sort(p) }

使用举例如下：

package main

import (
    "fmt"
    "sort"
)

func main() {
    instance := sort.IntSlice{1, 5, 8, 9, 7, 1}
    sort.Sort(instance)
    fmt.Println(instance) // [1 1 5 7 8 9]
    sort.Sort(sort.Reverse(instance))
    fmt.Println(instance) // [9 8 7 5 1 1]
}

自定义类型排序

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    age  int
    name string
    sex  string
}

type PersonSlice []Person

func (p PersonSlice) Len() int {
    return len(p)
}

func (p PersonSlice) Less(i, j int) bool {
    return p[i].age < p[j].age
}

func (p PersonSlice) Swap(i, j int) {
    p[i], p[j] = p[j], p[i]
}

func (p PersonSlice) Sort() {
    sort.Sort(p)
}

func main() {
    instance := PersonSlice{{12, "Jack", "male"}, {15, "Lucy", "famale"}, {13, "Lilei", "male"}}
    instance.Sort()
    fmt.Println(instance) // [{12 Jack male} {13 Lilei male} {15 Lucy famale}]
}

其它封装函数

// 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)) }

举例如下：

package main

import (
    "fmt"
    "sort"
)

func main() {
    num := []int{1, 5, 8, 9, 7, 1}
    fmt.Println(sort.IntsAreSorted(num)) // false
    sort.Ints(num)
    fmt.Println(num, sort.IntsAreSorted(num)) // [1 1 5 7 8 9] true
}

有疑问加站长微信联系（非本文作者）