參考golang 對(duì)自定義類(lèi)型排序

一、簡(jiǎn)介

sort 包 在內(nèi)部實(shí)現(xiàn)了四種基本的排序算法：插入排序（insertionSort）、歸并排序（symMerge）、堆排序（heapSort）和快速排序（quickSort）； sort 包會(huì)依據(jù)實(shí)際數(shù)據(jù)自動(dòng)選擇最優(yōu)的排序算法。所以我們寫(xiě)代碼時(shí)只需要考慮實(shí)現(xiàn) sort.Interface 這個(gè)類(lèi)型就可以了。

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)
}
// 內(nèi)部實(shí)現(xiàn)的四種排序算法
// 插入排序
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)

二、常用類(lèi)型內(nèi)置排序方法

對(duì)常見(jiàn)類(lèi)型int,float64,string，官方提供了內(nèi)置的排序：

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

注釋中寫(xiě)得清楚，這樣實(shí)現(xiàn)這三個(gè)接口，遞增排序。從打印結(jié)果來(lái)看，確實(shí)是遞增的。

對(duì)于未提供的內(nèi)置類(lèi)型排序，sort模塊提供了一個(gè)非常靈活的函數(shù)sort.Slice(slice interface{}, less func(i, j int) bool),第一個(gè)參數(shù)是要排序的切片.第二個(gè)參數(shù)是一個(gè)函數(shù),函數(shù)接收兩個(gè)index值,返回 slice[ I] < slice[j]這個(gè)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)
}

三、自定義一個(gè)排序

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

type Persons []Person
// 獲取此 slice 的長(zhǎng)度
func (p Persons) Len() int { return len(p) }
// 根據(jù)元素的年齡降序排序 （此處按照自己的業(yè)務(wù)邏輯寫(xiě)） 
func (p Persons) Less(i, j int) bool {
    return p[i].Age > p[j].Age
}
// 交換數(shù)據(jù)
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方法中，變成大于號(hào)了，所以是降序排列了。

當(dāng)我們對(duì)某一個(gè)結(jié)構(gòu)體中多個(gè)字段進(jìn)行排序時(shí)怎么辦，難道每排序一個(gè)就寫(xiě)下這三個(gè)方法么，當(dāng)然不是。我們可以利用嵌套結(jié)構(gòu)體來(lái)解決這個(gè)問(wèn)題。因?yàn)榍短捉Y(jié)構(gòu)體可以繼承父結(jié)構(gòu)體的所有屬性和方法。比如我想對(duì)上面 Person 的 Name 字段和 Age 對(duì)要排序，我們可以利用嵌套結(jié)構(gòu)體來(lái)改進(jìn)一下。

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

type Persons []Person

// Len()方法和Swap()方法不用變化
// 獲取此 slice 的長(zhǎng)度
func (p Persons) Len() int { return len(p) }

// 交換數(shù)據(jù)
func (p Persons) Swap(i, j int) { p[i], p[j] = p[j], p[i] }

// 嵌套結(jié)構(gòu)體  將繼承 Person 的所有屬性和方法
// 所以相當(dāng)于SortByName 也實(shí)現(xiàn)了 Len() 和 Swap() 方法
type SortByName struct{ Persons }

// 根據(jù)元素的姓名長(zhǎng)度降序排序 （此處按照自己的業(yè)務(wù)邏輯寫(xiě)）
func (p SortByName) Less(i, j int) bool {
    return len(p.Persons[i].Name) > len(p.Persons[j].Name)
}

type SortByAge struct{ Persons }

// 根據(jù)元素的年齡降序排序 （此處按照自己的業(yè)務(wù)邏輯寫(xiě)）
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函數(shù)專(zhuān)門(mén)用于slice的排序，使用極簡(jiǎn)單方便

package main

import (
    "fmt"
    "sort"
)

/*slice 簡(jiǎn)單排序示例*/
func main() {
    //定義一個(gè)年齡列表
    ageList := []int{1, 3, 7, 7, 8, 2, 5}

    //排序，實(shí)現(xiàn)比較方法即可
    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]

參考 golang sort.Slice

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.可以參考何時(shí)使用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函數(shù)設(shè)計(jì)學(xué)習(xí)，同時(shí)使用了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     }