Sort 排序算法
sort 包中实现了四种基本排序算法：插入排序、归并排序、堆排序、快速排序。但是它们不公开，只供sort包内部自己使用，所以在需要实现数据排序时不必考虑使用哪一种排序方法，只要实现了 sort.Interface 定义的三个方法： 获取数据集合长度Len()、比较两个元素大小Less()、交换两个元素位置Swap() 就可以完成对数据集合的自定义排序。sort 内部再根据实际数据自动选择高效的排序算法。
type Interface interface {
// 获取数据集合元素个数
Len() int
// 如果 i 索引的数据小于 j 索引的数据，返回 true，且不会调用下面的 Swap()，即数据升序排序。
Less(i, j int) bool
// 交换 i 和 j 索引的两个元素的位置
Swap(i, j int)
}
自定义的数据结构只要实现了以上接口的三个方法就可以实现自定义排序的功能，可以通过调用该包的 Sort()方法进行排序。
同时还提供了以下的一些方法：
func Sort(data Interface) // 对数据集进行排序
func IsSorted(data Interface) bool // 判断数据集合是否有序
func Reverse(data Interface) Interface // 将数据按照Less()定义的排序方式逆序排序
func Search(n int, f func(int) bool) int // 该方法会使用“二分查找”算法来找出能使 f(x)(0<=x<n) 返回 ture 的最小值 i。 前提条件 : f(x)(0<=x<i) 均返回 false, f(x)(i<=x<n) 均返回 ture。 如果不存在 i 可以使 f(i) 返回 ture, 则返回 n。
sort 的使用示例
// 示例1，使用sort来完成对学生结构体数组的自定义排序
type StuScore struct {
name string
score int
}
type StuScores []StuScore
func (s StuScores) Len() int {
return len(s)
}
func (s StuScores) Less(i, j int) bool {
return s[i].score > s[j].score
}
func (s StuScores) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}
func TestStuScores() {
stus := StuScores{
{"alan", 95},
{"hikerell", 91},
{"acmfly", 96},
{"leao", 90},
}
// 打印未排序的 stus 数据
fmt.Println("Default:\n\t", stus)
//StuScores 已经实现了 sort.Interface 接口 , 所以可以调用 Sort 函数进行排序
sort.Sort(stus)
// 判断是否已经排好顺序，将会打印 true
fmt.Println("IS Sorted?\n\t", sort.IsSorted(stus))
// 打印排序后的 stus 数据
fmt.Println("Sorted:\n\t", stus)
// Reverse 升序排序
sort.Sort(sort.Reverse(stus))
fmt.Println("升序\n\t", stus)
// 测试 Search 函数，它会找到满足 bool为true的最小i的位置
pos := sort.Search(len(stus), func(i int) bool {
return stus[i].score >= 95
})
fmt.Println("pos: ", pos)
}
// 示例2，使用sort的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.Scan(&s)
return s != "" && s[0] == 'y'
})
fmt.Printf("Your number is %d.\n", answer)
}
sort包支持的内部数据类型排序
sort 包原生支持 []int、[]float64、[]string 三类内建数据类型切片的排序操作。
1. IntSlice 类型及 []int 排序
[]int 类型转化为 IntSlice 类型： sort.IntSlice(s)
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) }
IntSlice 类型是 []int 切片类型实现 sort.Interface 接口后所产生的一种数据类型。并且提供了以下几种常用方法：
func Ints(a []int) { Sort(IntSlice(a)) } // 对 []int 类型数据进行排序
func SearchInts(a []int, x int) int // 对 []int 类型数据进行查找，使用前提是集合已经完成了排序
func IntsAreSorted(a []int) bool // 判断是否完成排序
sort.Sort(sort.Reverse(sort.IntSlice(s))) // 对 []int 类型数据进行反转排序
使用示例：
func TestSortInt() {
s := []int{5, 2, 6, 3, 1, 4}
res := sort.IsSorted(sort.IntSlice(s))
fmt.Println(res)
sort.Ints(s)
res = sort.IsSorted(sort.IntSlice(s))
fmt.Println(s)
fmt.Println(res)
pos := sort.SearchInts(s, 3)
fmt.Println(pos)
}
2. Float64Slice 类型及[]float64 排序
[]Float64 类型转化为 Float64Slice ：sort.Float64Slice(s)
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) }
[]Float64 类型常用的3种方法：
func Float64s(a []float64) // 排序，默认升序
func Float64sAreSorted(a []float64) bool // 判断是否完成排序
func SearchFloat64s(a []float64, x float64) int // 查找
使用示例：
func TestSortFloat() {
s := []float64{1.11, 2.22, 3.33, 4.44, 5.55}
res := sort.IsSorted(sort.Float64Slice(s)) // 使用 sort.IsSorted(xxx) 方法时内部需要传入实现了接口的类型
fmt.Println(res)
sort.Float64s(s)
//res = sort.IsSorted(sort.Float64Slice(s)) 这种方法也可以
res = sort.Float64sAreSorted(s)
fmt.Println(res)
pos := sort.SearchFloat64s(s, float64(2.22))
fmt.Println(pos)
sort.Sort(sort.Reverse(sort.Float64Slice(s)))
fmt.Println(s)
}
3. StringSlice 类型及[]string 排序
[]string 转化为 stringSlice：sort.stringSlice(s)
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) }
[]string 常用的几种方法：
func Strings(a []string)
func StringsAreSorted(a []string) bool
func SearchStrings(a []string, x string) int
使用示例：
func TestSortString() {
s := []string{"aaa", "bbb", "ccc", "ddd"}
res := sort.IsSorted(sort.StringSlice(s))
fmt.Println(res)
sort.Strings(s)
res = sort.StringsAreSorted(s)
fmt.Println(res)
pos := sort.SearchStrings(s, "aaa")
fmt.Println(pos)
sort.Sort(sort.Reverse(sort.StringSlice(s)))
fmt.Println(s)
}
4. 其它数据类型如何排序
上面介绍了几种基本数据类型如何运用 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 作为参数，同时还需要一个匿名函数作为排序规则的制定，该匿名函数最后返回布尔
sort.Slice(xxx)
完成对 []interface 的自定义排序
func TestSortSB() {
people := []struct {
Name string
Age int
}{
{"Gopher", 7},
{"Alice", 55},
{"Vera", 24},
{"Bob", 75},
}
// 实现sort实现接口后自定义排序
sort.Slice(people, func(i, j int) bool {
return people[i].Age < people[j].Age
})
fmt.Println(people)
}
sort.SliceStable(xxx)
完成对 []interface 的自定义稳定排序
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)
sort.SliceIsSorted(xxx)
判断 []interface 是否为有序
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)
fmt.Println("Sorted:",sort.SliceIsSorted(people,func(i, j int) bool { return people[i].Age < people[j].Age }))
sort.Search(xxx)
在排序集合种进行数据查找
func TestIsSort() {
people := []struct {
Name string
Age int
}{
{"Gopher", 7},
{"Alice", 55},
{"Vera", 24},
{"Bob", 75},
}
// 实现sort实现接口后自定义排序
sort.Slice(people, func(i, j int) bool {
return people[i].Age < people[j].Age
})
// 判断是否完成了指定规则的排序
fmt.Println(sort.SliceIsSorted(people, func(i, j int) bool {
return people[i].Age > people[j].Age
}))
// 实现查找
pos := sort.Search(len(people), func(i int) bool {
return people[i].Age >= 55
})
fmt.Println(pos)
}
堆
堆排序参考：https://blog.csdn.net/qq_28063811/article/details/93034625/
go如何使用堆：https://www.jianshu.com/p/5dcfec42d3d9
heap源码分析：https://blog.csdn.net/m0_37965811/article/details/117911909
1. 简单使用
堆使用的数据结构是最小二叉树，即根节点比左子树和右子树的所有值都要小。它的内部也包括了 sort.Interface 结构，也就是说如果要使用go语言中的堆，需要实现 Len()、Less()、Swap()方法和 Push()、Pop()方法。
type Interface interface {
sort.Interface
Push(x interface{}) // add x as element Len()
Pop() interface{} // remove and return element Len() - 1.
}
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
}
堆提供的方法如下：
h := &IntHeap{3, 8, 6} // 创建IntHeap类型的原始数据
func Init(h Interface) // 对heap进行初始化，生成小根堆（或大根堆）
func Push(h Interface, x interface{}) // 往堆里面插入内容
func Pop(h Interface) interface{} // 从堆顶pop出内容
func Remove(h Interface, i int) interface{} // 从指定位置删除数据，并返回删除的数据
func Fix(h Interface, i int) // 从i位置数据发生改变后，对堆再平衡，优先级队列使用到了该方法
2. heap源码解析
参考： https://blog.csdn.net/m0_37965811/article/details/117911909
heap 内部实现的 down 和 up 分别表示对堆中的某个元素向下保证最小(最大)堆和向上保证最小(最大)堆。最小还是最大由 Less() 函数决定；
当往堆中插入一个元素时，这个元素插入到最右子树的最后一个节点中，然后调用 up() 向上保证最小(最大)堆；
当从堆中推出一个元素时，先把该元素和右子树的最后一个节点交换，然后对 root 调用 down() 向下保证最小(最大)堆；
// 初始化堆结构
func Init(h Interface) {
// heapify
n := h.Len() // 获取数据的长度
for i := n/2 - 1; i >= 0; i-- { // 从长度的一半开始，一直到第0个数据，每个位置都调用down方法，down方法实现的功能是保证从该位置往下保证形成堆
down(h, i, n)
}
}
// 取左右节点中最大(最小)值和当前节点交换，然后继续维护交换后的子节点
func down(h Interface, i0, n int) bool {
i := i0 // 中间变量，第一次存储的是需要保证往下需要形成堆的节点位置
for { // 死循环
j1 := 2*i + 1 // i节点的左子孩子
if j1 >= n || j1 < 0 { // j1 < 0 after int overflow // 保证其左子孩子没有越界
break
}
j := j1 // left child // 中间变量j先赋值为左子孩子，之后j将被赋值为左右子孩子中最小（大）的一个孩子的位置
if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) {
j = j2 // = 2*i + 2 // right child
} // 这之后，j被赋值为两个孩子中的最小（大）孩子的位置（最小或最大由Less中定义的决定）
if !h.Less(j, i) {
break
} // 若j大于（小于）i，则终止循环
h.Swap(i, j) // 否则交换i和j位置的值
i = j // 令i=j，继续循环，保证j位置的子数是堆结构
}
return i > i0
}
// up同down原理类似，区别在于交换后继续处理的是父节点
func up(h Interface, j int) {
for { // 死循环
i := (j - 1) / 2 // parent // j节点的父节点
if i == j || !h.Less(j, i) { // 如果越界，或者满足堆的条件，则结束循环
break
}
h.Swap(i, j) // 否则将该节点和父节点交换
j = i // 对父节点继续进行检查直到根节点
}
}
// 其余方法源码
func Push(h Interface, x interface{}) {
h.Push(x) // 将新插入进来的节点放到最后
up(h, h.Len()-1) // 确保新插进来的节点网上能保证堆结构
}
func Pop(h Interface) interface{} {
n := h.Len() - 1 // 把最后一个节点和第一个节点进行交换，之后，从根节点开始重新保证堆结构，最后把最后那个节点数据丢出并返回
h.Swap(0, n)
down(h, 0, n)
return h.Pop()
}
func Remove(h Interface, i int) interface{} {
n := h.Len() - 1 pop只是remove的特殊情况，remove是把i位置的节点和最后一个节点进行交换，之后保证从i节点往下及往上都保证堆结构，最后把最后一个节点的数据丢出并返回
if n != i {
h.Swap(i, n)
down(h, i, n)
up(h, i)
}
return h.Pop()
}
func Fix(h Interface, i int) {
if !down(h, i, h.Len()) { // i节点的数值发生改变后，需要保证堆的再平衡，先调用down保证该节点下面的堆结构，如果有位置交换，则需要保证该节点往上的堆结构，否则就不需要往上保证堆结构，一个小小的优化
up(h, i)
}
}
3. heap实现优先队列
package dataStruct
import (
"container/heap"
"fmt"
)
// 队列中存储的节点
type Item struct {
Value string // 队列中的数据，可以是任意类型
Priority int // 优先级
Index int // 在队列中的位置
}
type PriorityQueue []*Item
// 绑定 Len() 方法
func (pq PriorityQueue) Len() int {
return len(pq)
}
// 绑定 Less() 方法---小根堆
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].Priority < pq[j].Priority
}
// 绑定 Swap() 方法
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].Index, pq[j].Index = j, i
}
// 出队列
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
x := old[n-1]
*pq = old[0 : n-1]
x.Index = -1
return x
}
// 入队列
func (pq *PriorityQueue) Push(x interface{}) {
n := len(*pq)
item := x.(*Item)
item.Index = n
*pq = append(*pq, item)
}
// 更新优先级及节点在队列中的位置
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
item.Value = value
item.Priority = priority
heap.Fix(pq, item.Index)
}
func TestPriorityQueue() {
items := map[string]int{"二毛": 5, "张三": 3, "狗蛋": 9}
i := 0
pq := make(PriorityQueue, len(items)) // 创建优先队列并初始化
for k, v := range items {
pq[i] = &Item{
Value: k,
Priority: v,
Index: i,
}
i++
}
heap.Init(&pq)
item := &Item{
Value: "李四",
Priority: 1,
}
heap.Push(&pq, item)
pq.update(item, item.Value, 6)
for len(pq) > 0 {
item := heap.Pop(&pq).(*Item)
fmt.Printf("%.2d:%s index:%.2d\n", item.Priority, item.Value, item.Index)
}
}
链表
链表就是一个有 prev 和 next 指针的数组，Go语言中通过维护两个Type来定义链表结构
type Element struct {
next, prev *Element // 上一个元素和下一个元素
list *List // 元素所在链表
Value interface{} // 元素
}
type List struct {
root Element // 链表的根元素
len int // 链表的长度
}
list 对应方法如下：
type Element
func (e *Element) Next() *Element
func (e *Element) Prev() *Element
type List
func New() *List // 生成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{} // 删除某个元素
环
环不需要像 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 个元素