# 数据结构和算法
# sort
该包实现了四种基本排序算法：插入排序、归并排序、堆排序和快速排序。 但是这四种排序方法只被用于 sort 包内部使用。
所以在对数据集合排序时不必考虑应当选择哪一种排序方法，想要对数据集合进行排序，只要实现 sort.Interface 定义的三个方法：
- 获取数据集合长度的 Len () 方法
- 比较两个元素大小的 Less () 方法
- 交换两个元素位置的 Swap () 方法
sort 包会根据实际数据自动选择高效的排序算法。
除此之外，为了方便对常用数据类型的操作，sort 包提供了对 [] int 切片、[] float64 切片和 [] string 切片完整支持，主要包括：
- 对基本数据类型切片的排序支持
- 基本数据元素查找
- 判断基本数据类型切片是否已经排好序
- 对排好序的数据集合逆序
# Interface
type Interface interface { | |
// Len 获取数据集合元素个数 | |
Len() int | |
// Less 返回索引 i 的元素是否必须排在索引 j 的元素之前。 | |
Less(i, j int) bool | |
// Swap 交换索引 i 和 j 的元素。 | |
Swap(i, j int) | |
} |
实现了这三个方法后，即可调用该包的 Sort () 方法进行排序。
# Sort
Sort () 方法定义如下：
// Sort 按 Less 方法确定的升序对数据进行排序。 | |
// 调用一次 data.Len 以确定对 data.Less 和 data.Swap 的 n 次调用和 O (n*log (n)) 次调用。 | |
// 不保证排序是稳定的。 | |
func Sort(data Interface) { | |
n := data.Len() | |
if n <= 1 { | |
return | |
} | |
limit := bits.Len(uint(n)) | |
pdqsort(data, 0, n, limit) | |
} |
判断数据集合是否已经排好顺序，该方法的内部实现依赖于我们自己实现的 Len () 和 Less () 方法：
func IsSorted(data Interface) bool { | |
n := data.Len() | |
for i := n - 1; i > 0; i-- { | |
if data.Less(i, i-1) { | |
return false | |
} | |
} | |
return true | |
} |
对学生成绩排序的 demo :
package main | |
import ( | |
"fmt" | |
"sort" | |
) | |
// 学生成绩结构体 | |
type StuScore struct { | |
name string // 姓名 | |
score int // 成绩 | |
} | |
type StuScores []StuScore | |
// Len() | |
func (s StuScores) Len() int { | |
return len(s) | |
} | |
// Less (): 成绩将有低到高排序 | |
func (s StuScores) Less(i, j int) bool { | |
return s[i].score < s[j].score | |
} | |
// Swap() | |
func (s StuScores) Swap(i, j int) { | |
s[i], s[j] = s[j], s[i] | |
} | |
func main() { | |
stus := StuScores{ | |
{"alan", 95}, | |
{"hikerell", 91}, | |
{"acmfly", 96}, | |
{"leao", 90}, | |
} | |
// 打印未排序的 stus 数据 | |
fmt.Println("\nDefault:\n", stus) | |
//StuScores 已经实现了 sort.Interface 接口，所以可以调用 Sort 函数进行排序 | |
sort.Sort(stus) | |
// 判断是否已经排好顺序，将会打印 true | |
fmt.Println("\nIS Sorted?\n", sort.IsSorted(stus)) | |
// 打印排序后的 stus 数据 | |
fmt.Println("\nSorted:\n", stus) | |
} |
输出
Default: | |
[{alan 95} {hikerell 91} {acmfly 96} {leao 90}] | |
IS Sorted? | |
true | |
Sorted: | |
[{leao 90} {hikerell 91} {alan 95} {acmfly 96}] |
# Reverse
提供了 Reverse () 方法，可以允许将数据按 Less () 定义的排序方式逆序排序，而不必修改 Less () 代码。方法定义如下：
// 定义了一个 reverse 结构类型，嵌入 Interface 接口 | |
type reverse struct { | |
Interface | |
} | |
// Less 返回与实现的 Less 方法相反的结果。 | |
func (r reverse) Less(i, j int) bool { | |
return r.Interface.Less(j, i) | |
} | |
// Reverse 返回数据的相反顺序。 | |
func Reverse(data Interface) Interface { | |
return &reverse{data} | |
} |
了解内部原理后，可以在学生成绩排序示例中使用 Reverse () 来实现成绩升序排序
demo:
func main() { | |
stus := StuScores{ | |
{"alan", 95}, | |
{"hikerell", 91}, | |
{"acmfly", 96}, | |
{"leao", 90}, | |
} | |
sort.Sort(sort.Reverse(stus)) | |
fmt.Println("\nSorted:\n", stus) | |
} |
# Search
该方法会使用 “二分查找” 算法来找出能使 f (x)(0<=x<n) 返回 ture 的最小值 i。
前提条件 :
f (x)(0<=x<i) 均返回 false,
f (x)(i<=x<n) 均返回 ture。
如果不存在 i 可以使 f (i) 返回 ture, 则返回 n。
func Search(n int, f func(int) bool) int { | |
// 定义 f (-1) == false and f (n) == true. | |
// 不变式: f (i-1) == false, f (j) == true. | |
i, j := 0, n | |
for i < j { | |
h := int(uint(i+j) >> 1) // 避免计算 h 时溢出 | |
// i ≤ h < j | |
if !f(h) { | |
i = h + 1 // 保留 f (i-1) == false | |
} else { | |
j = h // 保留 f (j) == true | |
} | |
} | |
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i. | |
return i | |
} |
官方还给了一个猜数字的 demo
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) | |
} |
# IntSlice, Float64Slice, StringSlice
sort 包已经支持的内部数据类型排序
sort 包原生支持 [] int、[] float64 和 [] string 三种内建数据类型切片的排序操作，即不必我们自己实现相关的 Len ()、Less () 和 Swap () 方法。
1. IntSlice 类型及 [] int 排序
由于 [] int 切片排序内部实现及使用方法与 [] float64 和 [] string 类似，所以只详细描述该部分。
sort 包定义了一个 IntSlice 类型，并且实现了 sort.Interface 接口：
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] } | |
//IntSlice 类型定义了 Sort () 方法，包装了 sort.Sort () 函数 | |
func (p IntSlice) Sort() { Sort(p) } | |
//IntSlice 类型定义了 SearchInts () 方法，包装了 SearchInts () 函数 | |
func (p IntSlice) Search(x int) int { return SearchInts(p, x) } | |
// SearchInts 搜索 | |
func SearchInts(a []int, x int) int { | |
return Search(len(a), func(i int) bool { return a[i] >= x }) | |
} | |
//sort.Ints () 方法使用了该 IntSlice 类型： | |
func Ints(a []int) { Sort(IntSlice(a)) } |
对 [] int 切片排序更常使用 sort.Ints ()，而不是直接使用 IntSlice 类型：
func main() { | |
s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据 | |
sort.Ints(s) | |
fmt.Println(s) // 将会输出 [1 2 3 4 5 6] | |
} |
如果要查找整数 x 在切片 a 中的位置，相对于前面提到的 Search () 方法，sort 包提供了 SearchInts ():
注意，SearchInts () 的使用条件为：切片已经升序排序
func main() { | |
s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据 | |
sort.Ints(s) | |
fmt.Println(sort.SearchInts(s, 2)) // 1 | |
} |
2. Float64Slice 类型及 [] float64 排序
实现与 Ints 类似，只看一下其内部实现：
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 (p Float64Slice) Sort() { Sort(p) } | |
func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) } |
与 Sort ()、IsSorted ()、Search () 相对应的三个方法：
func Float64s(a []float64) | |
func Float64sAreSorted(a []float64) bool | |
func SearchFloat64s(a []float64, x float64) int |
要说明一下的是，在上面 Float64Slice 类型定义的 Less 方法中，有一个内部函数 isNaN ()。 isNaN () 与 math 包中 IsNaN () 实现完全相同，sort 包之所以不使用 math.IsNaN ()，完全是基于包依赖性的考虑，应当看到，sort 包的实现不依赖与其他任何包。
3. StringSlice 类型及 [] string 排序
两个 string 对象之间的大小比较是基于 “字典序” 的。
实现与 Ints 类似，只看一下其内部实现：
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) } | |
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) } |
与 Sort ()、IsSorted ()、Search () 相对应的三个方法：
func Strings(a []string) | |
func StringsAreSorted(a []string) bool | |
func SearchStrings(a []string, x string) int |
3. StringSlice 类型及 [] string 排序
两个 string 对象之间的大小比较是基于 “字典序” 的。
实现与 Ints 类似，只看一下其内部实现：
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) } | |
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) } |
与 Sort ()、IsSorted ()、Search () 相对应的三个方法：
func Strings(a []string) | |
func StringsAreSorted(a []string) bool | |
func SearchStrings(a []string, x string) int |
# []interface
只要实现了 sort.Interface 接口，即可通过 sort 包内的函数完成排序，查找等操作。
并且 sort 包已经帮我们把 []int , []float64 , []string 三种类型都实现了该接口，我们可以方便的调用。但是这种用法对于其它数据类型的 slice 不友好，可能我们需要为大量的 struct 定义一个单独的 [] struct 类型，再为其实现 sort.Interface 接口，类似这样：
type Person struct { | |
Name string | |
Age int | |
} | |
type Persons []Person | |
func (p Persons) Len() int { | |
panic("implement me") | |
} | |
func (p Persons) Less(i, j int) bool { | |
panic("implement me") | |
} | |
func (p Persons) Swap(i, j int) { | |
panic("implement me") | |
} |
因为排序涉及到比较两个变量的值，而 struct 可能包含多个属性，程序并不知道你想以哪一个属性或哪几个属性作为衡量大小的标准。
如果能帮助程序完成比较，并将结果返回， sort 包内的方法就可以完成排序，判断，查找等。sort 包提供了以下函数：
func Slice(slice interface{}, less func(i, j int) bool) | |
func SliceStable(slice interface{}, less func(i, j int) bool) | |
func SliceIsSorted(slice interface{}, less func(i, j int) bool) bool | |
func Search(n int, f func(int) bool) int |
通过函数签名可以看到，排序相关的三个函数都接收 []interface ，并且需要传入一个比较函数，用于为程序比较两个变量的大小，因为函数签名和作用域的原因，这个函数只能是 匿名函数 。
1. sort.Slice
该函数完成 [] interface 的排序
demo:
func main() { | |
people := []struct { | |
Name string | |
Age int | |
}{ | |
{"Gopher", 7}, | |
{"Alice", 55}, | |
{"Vera", 24}, | |
{"Bob", 75}, | |
} | |
// 按年龄升序排序 | |
sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age }) | |
fmt.Println("Sort by age:", people) | |
// Sort by age: [{Gopher 7} {Vera 24} {Alice 55} {Bob 75}] | |
} |
2. sort.SliceStable
该函数完成 [] interface 的稳定排序，
demo:
func main() { | |
people := []struct { | |
Name string | |
Age int | |
}{ | |
{"Gopher", 7}, | |
{"Alice", 55}, | |
{"Vera", 24}, | |
{"Bob", 75}, | |
} | |
// 按年龄降序排序 | |
sort.SliceStable(people, func(i, j int) bool { return people[i].Age > people[j].Age }) | |
fmt.Println("Sort by age:", people) | |
// By age: [{Bob 75} {Alice 55} {Vera 24} {Gopher 7}] | |
} |
3. sort.SliceIsSorted
该函数判断 [] interface 是否为有序
demo:
func main() { | |
people := []struct { | |
Name string | |
Age int | |
}{ | |
{"Gopher", 7}, | |
{"Alice", 55}, | |
{"Vera", 24}, | |
{"Bob", 75}, | |
} | |
sort.Slice(people, func(i, j int) bool { return people[i].Age > people[j].Age }) | |
fmt.Println("Sort by age:", people) | |
// Sort by age: [{Bob 75} {Alice 55} {Vera 24} {Gopher 7}] | |
fmt.Println("Sorted:", sort.SliceIsSorted(people, func(i, j int) bool { return people[i].Age < people[j].Age })) | |
// Sorted: false | |
} |
# container
该包实现了三个复杂的数据结构：堆，链表，环。
# Heap
堆，这里的堆使用的数据结构是最小二叉树，即根节点比左边子树和右边子树的所有值都小。 go 的堆包只是实现了一个接口：
type Interface interface { | |
sort.Interface | |
Push(x interface{}) // add x as element Len() | |
Pop() interface{} // remove and return element Len() - 1. | |
} |
// 交换节点的操作 | |
func up(h Interface, j int) { | |
for { | |
i := (j - 1) / 2 // parent | |
if i == j || !h.Less(j, i) { | |
break | |
} | |
h.Swap(i, j) | |
j = i | |
} | |
} | |
func down(h Interface, i0, n int) bool { | |
i := i0 | |
for { | |
j1 := 2*i + 1 | |
if j1 >= n || j1 < 0 { // j1 < 0 after int overflow | |
break | |
} | |
j := j1 // left child | |
if j2 := j1 + 1; j2 < n && h.Less(j2, j1) { | |
j = j2 // = 2*i + 2 // right child | |
} | |
if !h.Less(j, i) { | |
break | |
} | |
h.Swap(i, j) | |
i = j | |
} | |
return i > i0 | |
} |
官方的 demo：
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(old) | |
x := old[n-1] | |
*h = old[0 : n-1] | |
return x | |
} |
# List
链表，一个有 prev 和 next 指针的数组。它维护两个 type，(注意，这里不是 interface)
type Element struct { | |
next, prev *Element // 上一个元素和下一个元素 | |
list *List // 元素所在链表 | |
Value interface{} // 元素 | |
} | |
type List struct { | |
root Element // 链表的根元素 | |
len int // 链表的长度 | |
} |
方法：
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) Front() *Element // 第一个元素 | |
func (l *List) Init() *List // 链表初始化 | |
func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某个元素后插入 | |
func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 在某个元素前插入 | |
func (l *List) Len() int // 在链表长度 | |
func (l *List) MoveAfter(e, mark *Element) // 把 e 元素移动到 mark 之后 | |
func (l *List) MoveBefore(e, mark *Element) // 把 e 元素移动到 mark 之前 | |
func (l *List) MoveToBack(e *Element) // 把 e 元素移动到队列最后 | |
func (l *List) MoveToFront(e *Element) // 把 e 元素移动到队列最头部 | |
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{} // 删除某个元素 |
demo:
func main() { | |
list := list.New() | |
list.PushBack(1) | |
list.PushBack(2) | |
fmt.Printf("len: %v\n", list.Len()) | |
fmt.Printf("first: %#v\n", list.Front()) | |
fmt.Printf("second: %#v\n", list.Front().Next()) | |
func main() { | |
list := list.New() | |
list.PushBack(1) | |
list.PushBack(2) | |
fmt.Printf("len: %v\n", list.Len()) | |
fmt.Printf("first: %#v\n", list.Front()) | |
fmt.Printf("second: %#v\n", list.Front().Next()) | |
// len: 2 | |
// first: &list.Element{next:(*list.Element)(0xc0000a01b0), prev:(*list.Element)(0xc0000a0150), list:(*list.List)(0xc0000a0150), Value:1} | |
// second: &list.Element{next:(*list.Element)(0xc0000a0150), prev:(*list.Element)(0xc0000a0180), list:(*list.List)(0xc0000a0150), Value:2} | |
} |
# Ring
环的结构有点特殊，环的尾部就是头部，所以每个元素实际上就可以代表自身的这个环。 它不需要像 list 一样保持 list 和 element 两个结构，只需要保持一个结构就行。
type Ring struct { | |
next, prev *Ring | |
Value interface{} | |
} |
方法：
type Ring | |
func New(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 // 指针从当前元素开始向后移动或者向前（n 可以为负数） | |
func (r *Ring) Next() *Ring // 当前元素的下个元素 | |
func (r *Ring) Prev() *Ring // 当前元素的上个元素 | |
func (r *Ring) Unlink(n int) *Ring // 从当前元素开始，删除 n 个元素 |
demo ：
func main() { | |
ring := ring.New(3) | |
for i := 1; i <= 3; i++ { | |
ring.Value = i | |
ring = ring.Next() | |
} | |
// 计算 1+2+3 | |
s := 0 | |
ring.Do(func(p interface{}) { | |
s += p.(int) | |
}) | |
fmt.Println("sum is", s) | |
// sum is 6 | |
} |
