1.md

数组

1. 简单排序
2. 归并排序
3. 快速排序
4. 基数排序

---

　　数组本质上是一段连续的存储区域，可以通过计算地址偏移快速访问里面的任意元素（即"随机访问"）。因为要保持连续，所以数组的扩容往往需要通过先申请新空间再拷贝的方法实现，比较奢侈。

func InsertTo[T any](list []T, pos int, val T) []T {
    if pos < 0 || pos > len(list) {
        panic("illegal pos")
    }
    list = append(list, val)
    for i := len(list)-1; i > pos; i-- {
        list[i] = list[i-1]
    }
    list[pos] = val
    return list
}

func EraseFrom[T any](list []T, pos int, keepOrder bool) []T {
    if pos < 0 || pos >= len(list) {
        panic("illegal pos")
    }
    last := len(list) - 1
    if keepOrder {
        for i := pos; i < last; i++ {
            list[i] = list[i+1]
        }
    } else {
        list[pos] = list[last]
    }
    return list[:last]
}

对于无序数组，插入和删除都是很方便的（O(1)时间），但对于有序数组则需要一番腾挪（O(N)时间）。

二分查找

有序数组在查找上有特殊优势，可以在O(logN)的时间内完成：

func Search[T constraints.Ordered](list []T, key T) int {
    for a, b := 0, len(list); a < b; {
        m := (a+b) / 2
        switch {
            case key > list[m]: a = m + 1
            case key < list[m]: b = m
            default: return m           
        }
    }                           //寻找key的位置
    return -1                   //没有则返回-1
}

环状队列

可以基于数组实现队列，这种队列呈环状，实际可容纳元素比底层的数组少一个。

type queue[T any] struct {
    r, w  int       //读写游标
    space []T       //底层数组
}

func (q *queue[T]) init(size int) {
    if size < 7 {
        size = 7
    }
    q.space = make([]T, size+1)
    q.r, q.w = 0, 0
}

func (q *queue[T]) IsEmpty() bool {
    return q.r == q.w
}

func (q *queue[T]) IsFull() bool {
    return (q.w+1)%len(q.space) == q.r
}

---

返回　下一章　下一节