文章

排序与集合

#golang#sort#container#slices

排序与集合

包总览

包核心类型/函数用途
sortSort, Search, Slice排序与搜索
slicesSort, Contains, BinarySearch（Go 1.21+）泛型 slice 操作
mapsKeys, Values, Clone, Copy（Go 1.21+）泛型 map 操作
container/listList, Element双向链表
container/heapHeap, Interface优先队列
container/ringRing环形缓冲

sort 包

基本排序

import "sort"

// 基本类型排序
sort.Ints([]int{3, 1, 4, 1, 5, 9, 2, 6})  // [1 1 2 3 4 5 6 9]
sort.Float64s([]float64{3.14, 1.41, 2.71})
sort.Strings([]string{"banana", "apple", "cherry"})

// 检查是否已排序
sort.IntsAreSorted([]int{1, 2, 3})  // true
sort.StringsAreSorted([]string{"a", "b"})  // true

// 搜索（已排序的 slice）
idx := sort.SearchInts([]int{1, 3, 5, 7, 9}, 5)  // 2
idx := sort.SearchStrings([]string{"a", "b", "c"}, "b")  // 1

自定义排序

// 方式1：实现 sort.Interface
type ByAge []User

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

users := []User{{Name: "小徐", Age: 28}, {Name: "小王", Age: 25}}
sort.Sort(ByAge(users))  // 按年龄升序

// 方式2：sort.Slice（更简洁）
sort.Slice(users, func(i, j int) bool {
    return users[i].Age < users[j].Age
})

// 降序
sort.Slice(users, func(i, j int) bool {
    return users[i].Age > users[j].Age
})

// 多字段排序
sort.Slice(users, func(i, j int) bool {
    if users[i].Age != users[j].Age {
        return users[i].Age < users[j].Age  // 先按年龄
    }
    return users[i].Name < users[j].Name  // 年龄相同按名字
})

// 稳定排序（相等元素保持原顺序）
sort.SliceStable(users, func(i, j int) bool {
    return users[i].Age < users[j].Age
})

sort.SliceStable vs sort.Slice

函数稳定性时间复杂度适用
sort.Slice不稳定O(n log n)通用
sort.SliceStable稳定O(n log² n)需要保持相等元素顺序

sort.Search（二分搜索）

// 在已排序的 slice 中搜索（返回第一个满足条件的位置）
nums := []int{1, 3, 5, 7, 9, 11, 13}

idx := sort.Search(len(nums), func(i int) bool {
    return nums[i] >= 7
})
// idx = 3, nums[3] = 7

// 查找第一个 >= 6 的元素
idx := sort.Search(len(nums), func(i int) bool {
    return nums[i] >= 6
})
// idx = 3, nums[3] = 7（6 不存在，返回插入位置）

// 自定义搜索
type User struct {
    ID   int
    Name string
}
users := []User{{1, "A"}, {3, "B"}, {5, "C"}, {7, "D"}}

idx := sort.Search(len(users), func(i int) bool {
    return users[i].ID >= 5
})
// idx = 2, users[2] = {5, "C"}

slices 包（Go 1.21+）

import "slices"

// 排序
s := []int{3, 1, 4, 1, 5, 9, 2, 6}
slices.Sort(s)                         // [1 1 2 3 4 5 6 9]
slices.SortFunc(s, func(a, b int) int { return b - a })  // 降序

// 字符串排序
strs := []string{"banana", "apple", "cherry"}
slices.Sort(strs)  // [apple banana cherry]

// 搜索
slices.Contains(s, 5)                  // true
slices.Index(s, 4)                     // 3
slices.BinarySearch(s, 5)              // (4, true)

// 比较
slices.Equal([]int{1,2,3}, []int{1,2,3})  // true
slices.Compare([]int{1,2}, []int{1,3})    // -1

// 操作
slices.Reverse(s)                      // 原地反转
slices.Delete(s, 1, 3)                 // 删除 [1,3) 范围
slices.Insert(s, 1, 99)                // 在索引1插入

// 最值
slices.Max(s)                          // 9
slices.Min(s)                          // 1
slices.MaxFunc(users, func(a, b User) int {
    return a.Age - b.Age
})

// 去重（需先排序）
slices.Sort(s)
slices.Compact(s)  // 去除连续重复元素

sort.SortFunc 比较函数

// Go 1.21+ 的比较函数签名：func(a, b T) int
// 返回负数: a < b
// 返回 0:   a == b
// 返回正数: a > b

slices.SortFunc(users, func(a, b User) int {
    return cmp.Compare(a.Age, b.Age)  // 使用 cmp.Compare
})

maps 包（Go 1.21+）

import "maps"

m := map[string]int{"a": 1, "b": 2, "c": 3}

// 获取所有 key（顺序随机）
keys := maps.Keys(m)  // []string{"a", "b", "c"}

// 获取所有 value
values := maps.Values(m)  // []int{1, 2, 3}

// 克隆
m2 := maps.Clone(m)

// 复制
maps.Copy(m, map[string]int{"d": 4, "e": 5})

// 删除满足条件的
maps.DeleteFunc(m, func(k string, v int) bool {
    return v < 2
})

// 比较
maps.Equal(m, m2)  // true

container/list（双向链表）

import "container/list"

l := list.New()

// 添加
l.PushBack("tail")       // 尾部添加
l.PushFront("head")      // 头部添加
l.PushBackList(other)    // 尾部追加另一个链表

// 遍历
for e := l.Front(); e != nil; e = e.Next() {
    fmt.Println(e.Value)
}

// 从尾部遍历
for e := l.Back(); e != nil; e = e.Prev() {
    fmt.Println(e.Value)
}

// 删除
e := l.Front()
l.Remove(e)

// 在指定元素前/后插入
l.InsertBefore("new", e)
l.InsertAfter("new", e)

// 获取
l.Len()                  // 长度
l.Front()                // 头元素
l.Back()                 // 尾元素

// 移动
l.MoveToFront(e)
l.MoveToBack(e)
l.MoveBefore(e, target)
l.MoveAfter(e, target)

container/heap（优先队列）

import "container/heap"

// 实现 heap.Interface
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[:n-1]
    return x
}

// 使用
h := &IntHeap{3, 1, 4, 1, 5, 9, 2, 6}
heap.Init(h)         // 初始化堆

heap.Push(h, 0)      // 插入元素
min := heap.Pop(h)   // 弹出最小元素（0）

// 大顶堆：修改 Less 函数
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }

优先队列应用

// 任务优先级队列
type Task struct {
    Priority int
    Name     string
}

type PriorityQueue []Task

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Priority > pq[j].Priority  // 大顶堆：优先级高的先出
}
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Task)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[:n-1]
    return x
}

// 使用
pq := &PriorityQueue{}
heap.Init(pq)
heap.Push(pq, Task{Priority: 3, Name: "high"})
heap.Push(pq, Task{Priority: 1, Name: "low"})
heap.Push(pq, Task{Priority: 2, Name: "medium"})

for pq.Len() > 0 {
    task := heap.Pop(pq).(Task)
    fmt.Println(task.Name)  // high, medium, low
}

container/ring（环形缓冲）

import "container/ring"

// 创建大小为 3 的环
r := ring.New(3)

// 填充数据
for i := 0; i < 3; i++ {
    r.Value = i
    r = r.Next()
}

// 遍历
r.Do(func(v interface{}) {
    fmt.Println(v)  // 0, 1, 2
})

// 长度
n := r.Len()  // 3

// 移动
r = r.Move(2)  // 向前移动 2 步

// 链接两个环
r.Link(otherRing)

数据结构选型指南

需求推荐类型时间复杂度
有序数组[]T + sort排序 O(n log n), 搜索 O(log n)
动态数组[]T追加 O(1) amortized, 访问 O(1)
键值查找map[K]VO(1) 平均
去重map[K]struct{}O(1)
有序键值无内置用 sorted slice 或第三方库
优先队列container/heap插入/删除 O(log n)
双向链表container/list头尾操作 O(1)
队列 (FIFO)[]T 或 list.ListO(1)
栈 (LIFO)[]TO(1)
环形缓冲container/ringO(1)