我們?cè)贕o語(yǔ)言當(dāng)中使用的數(shù)學(xué)方法都來(lái)自與math包，其中math的子包中包含以下這些包：
math/big: 大整數(shù)的高精度計(jì)算實(shí)現(xiàn)
math/cmplx: 復(fù)數(shù)基本函數(shù)操作
math/rand: 偽隨機(jī)數(shù)生成器
Go在數(shù)據(jù)結(jié)構(gòu)方面主要有三大相關(guān)的標(biāo)準(zhǔn)包：
sort: 包含基本的排序方法
index/suffixary: 該包實(shí)現(xiàn)了后綴數(shù)組相關(guān)算法以支持許多常見的字符串操作
container: 該包實(shí)現(xiàn)了我們數(shù)據(jù)結(jié)構(gòu)當(dāng)中最常用的堆、鏈表和環(huán)的內(nèi)容。

排序

數(shù)據(jù)集合排序

我們?cè)趯?duì)數(shù)據(jù)集合進(jìn)行排序之前，需要實(shí)現(xiàn)sort.Interface接口的三個(gè)方法，來(lái)看一下其定義：

type Interface interface {
    // 獲取元素集合個(gè)數(shù)元素
    Len() int
    // 如果 i 索引的數(shù)據(jù)小于 j 所有的數(shù)據(jù)，返回 true，不會(huì)調(diào)用
    Less(i, j int) bool
    // 交換 i 和 j 索引得兩個(gè)元素的位置
    Swap(i, j int)
}

我們?cè)趯?shí)現(xiàn)了這三個(gè)方法后，就可以調(diào)用Sort()方法來(lái)進(jìn)行排序了。其定義也很簡(jiǎn)單，只需要一個(gè)參數(shù)，也就是待排序的數(shù)據(jù)集合。

func Sort(data interface)

該包中還提供了一個(gè)IsSorted()函數(shù)，用來(lái)判斷數(shù)據(jù)集合是否已經(jīng)拍好順序。

func IsSorted(data interface) {
    n := data.Len()
    for i := n - 1; i > 0; i-- {
        if data.Less(i, i-1) {
            return false
        }
    }
    return true
}

我們來(lái)看一個(gè)具體的例子：

import (
    "fmt"
    "sort"
)

type StuInfo struct {
    name string
    score int
}

type StuInfos []StuInfo

func (s StuInfos) Len() int {
    return len(s)
}

func (s StuInfos) Less(i, j int) bool {
    return s[i].score < s[j].score
}

func (s StuInfos) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

func main() {
    stus := StuInfos{
        {"Alice", 95},
        {"Bob", 91},
        {"Cindy", 96},
        {"David", 90},
    }
    fmt.Println("=====Original=====")
    for _, stu := range stus {
        fmt.Println(stu.name, ": " , stu.score)
    }
    fmt.Println()

    sort.Sort(stus)

    fmt.Println("=====After Sort=====")
    for _, stu := range stus {
        fmt.Println(stu.name, ": ", stu.score)
    }

    fmt.Println("Has been sorted?", sort.IsSorted(stus))
}
/** The result is: 
David :  90
Bob :  91
Alice :  95
Cindy :  96
Has been sorted? true
 */

在這個(gè)程序當(dāng)中，我們使用的是升序排序，那如果我們想要使用降序該怎么辦呢？
也很簡(jiǎn)單，只需要修改Less()函數(shù)即可。

func (s StuInfos) Less(i, j int) bool {
    return s[i].score > s[j].score
}

但其實(shí)還有一種方法，也很簡(jiǎn)單，那么就是Reverse()函數(shù)，這個(gè)函數(shù)我們?cè)趯W(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)或者其他語(yǔ)言的時(shí)候會(huì)經(jīng)常對(duì)反轉(zhuǎn)函數(shù)這么命名，那么有了這個(gè)函數(shù)我們就不需要再修改Less()函數(shù)了。

func Reverse(data interface) Interface

在這里需要注意的是，Reverse()函數(shù)返回的是一個(gè)接口。
那么這樣一來(lái)，我們就可以在剛才那個(gè)例子中使用Reverse()來(lái)實(shí)現(xiàn)成績(jī)升序排序：

sort.Sort(sort.Reverse(stus))
for _, stu := range stus {
    fmt.Println(stu.name, ": ", stu.score)
}

最后還有一個(gè)方法：Search()，該方法使用“二分查找” 算法來(lái)搜索某指定切片[0:n],定義如下：

func Search(n int, f func(int) bool) int

Search()函數(shù)的一個(gè)常用方式是搜索元素x是否已經(jīng)在升序排好的切片s中：

x := 11
s := []int{3, 6, 8, 11, 45}
pos := sort.Search(len(s), func(i int) bool {return s[i] >= x })
if pos < len(s) && s[pos] == x {
    fmt.Println("The position of ", x, "is: ", pos)
} else {
    fmt.Println(x, " is not in slice.")
}

切片排序

我們知道sort包中是原生支持[]int、[]float64、[]string類型的，也就意味著這三種切片類型接口的內(nèi)部實(shí)現(xiàn)是不需要我們自己去設(shè)置的。
1）[]int排序
sort包定義了一個(gè)IntSlice類型，并且實(shí)現(xiàn)了sort.Interface接口。在提供的sort.Ints()方法中就使用了這個(gè)IntSlice類型：

func Ints(a []int) { Sort(IntSlice(a)) }

所以，對(duì)[]int切片排序時(shí)會(huì)更常使用sort.Ints()，而不是直接使用IntSlice類型。
如果要查找整數(shù)x在切片a中的位置，相對(duì)于前面提到的Search()方法，sort包提供了SearchInts()：

func SearchInts(a []int, x int) int

2）[]float64排序
實(shí)現(xiàn)與Ints類似，與Sort()，IsSorted()，Search()相對(duì)應(yīng)的三個(gè)方法：

func Float64s(a []float64)
func Float64AreSorted(a []float64) bool 
func SearchFloat64s(a []float64, x float64) int

3）[]stirng排序
兩個(gè)string對(duì)象之間的大小比較是基于"字典序"的，實(shí)現(xiàn)仍然與Ints類似，與Sort()，IsSorted()，Search()相對(duì)應(yīng)的三個(gè)方法：

func Strings(a []string)
func StringsAreSorted(a []string) bool 
func SearchStrings(a []string, x string) int

container

這個(gè)包實(shí)現(xiàn)了三個(gè)我們?cè)跀?shù)據(jù)當(dāng)中會(huì)經(jīng)常用到的三種數(shù)據(jù)結(jié)構(gòu)：堆、鏈表和環(huán)。

堆

這里的堆使用的數(shù)據(jù)結(jié)構(gòu)是使用的最小二叉樹的存儲(chǔ)方法，定義如下：

type Interface interface {
    sort.Interface
    Push(x interface{})
    Pop() interface{}
}

從第二行代碼我們看出來(lái)，堆的定義是繼承自sort.Interface的。我們前面說(shuō)過(guò)，實(shí)現(xiàn)一個(gè)sort.Interface是需要實(shí)現(xiàn)三個(gè)方法的，再加上堆本身的兩個(gè)方法，因此我們?cè)谑褂枚训臅r(shí)候，是需要實(shí)現(xiàn)五個(gè)方法的。結(jié)合前面所講的，我們可以試著來(lái)實(shí)現(xiàn)一下這五個(gè)方法：

type IntHeap []int

func (h IntHeap) Len() int {
    return len(h)
}
func (h IntHeap) Less(i, j int) bool {
    return h[i] < h[j]
}
func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(h)
    x := old[n-1]
    *h = old[0: n-1]
    return x
}

鏈表

鏈表其實(shí)就是一個(gè)有prev和next指針的數(shù)組，它維護(hù)了兩個(gè)type，要注意，這里就不再是接口了。

type Element struct {
    next, prev *Element
    list *List
    Value interface{}
}
type List struct {
    root Element
    len int
}

除了定義之外，我們?cè)趤?lái)看一下list都對(duì)應(yīng)著哪些方法：

type Element
    func (e *Element) Next() *Element
    func (e *Element) Prev() *Element
type List
    func New() *List
    func (l *List) Back() *Element
    func (l *List) Prev() *Element
    func (l *List) Init() *List
    func (l *List) InsertAfter(v interface{}, mark *Element) *Element  // 在某個(gè)元素后插入
    func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 在某個(gè)元素之前插入
    func (l *List) Len() int
    func (l *List) MoveAfter(e, mark *Element) // 把e元素移動(dòng)到mark之后
    func (l *List) MoveBefore(e, mark *Element) // 把e元素移動(dòng)到mark之前
    func (l *List) MoveToBack(e *Element) // 把e元素移動(dòng)到鏈表最后
    func (l *List) MoveToFront(e *Element) // 把e元素移動(dòng)到鏈表最前面
    func (l *List) PushBack(v interface{}) *Element // 在鏈表最后插入元素
    func (l *List) PushBackList(other *List) // 在鏈表最后插入接上新鏈表
    func (l *List) PushFront(v interface{}) *Element // 在鏈表頭部插入元素
    func (l *List) PushFrontList(other *List) // 在鏈表最前面插入接上新鏈表
    func (l *List) Remove(e *Element) interface{} // 刪除某個(gè)元素

環(huán)

環(huán)是數(shù)據(jù)結(jié)構(gòu)當(dāng)中最好用的一種數(shù)據(jù)結(jié)構(gòu)，而且環(huán)的尾部就是頭部，所以每個(gè)元素實(shí)際上就可以代表自身的這個(gè)環(huán)。因此我們只需要保持一個(gè)結(jié)構(gòu)就可以：

type Ring struct {
    next, prev *Ring
    Value interface{}
}

我們?cè)诔跏蓟h(huán)的時(shí)候一定要定義好環(huán)的大小，而且，環(huán)結(jié)構(gòu)還提供了一個(gè)Do的方法，可以對(duì)整個(gè)環(huán)進(jìn)行遍歷，并對(duì)每個(gè)元素執(zhí)行相應(yīng)的功能。

package main

import (
    "container/ring"
    "fmt"
)

func main() {
    ring := ring.New(3)
    for i := 1; i <= 3; i++ {
        ring.Value = i
        ring = ring.Next()
    }

    sum := 0
    ring.Do(func (p interface{}){
        sum += p.(int)
    })
    fmt.Println("The result is: ", sum)
}
/**
The result is:  6
 */

我們可以看出，Do方法對(duì)于遍歷環(huán)中每一個(gè)元素并執(zhí)行相應(yīng)功能的操作十分方便。
ring也提供了一些相應(yīng)的方法：

type Ring
    func Next(n int) *Ring
    func (r *Ring) Do(f func(interface{}))
    func (r *Ring) Len() int
    func (r *Ring) Link(s *Ring) *Ring
    func (r *Ring) Move(n int) *Ring // 指針從當(dāng)前元素開始向后移動(dòng)或者向前移動(dòng)（n可以為負(fù)數(shù)）
    func (r *Ring) Next() *Ring
    func (r *Ring) Prev() *Ring
    func (r *Ring) Unlink(n int) *Ring // 從當(dāng)前元素開始，刪除n個(gè)元素