Go 语言常用算法及数据结构汇总

Keep calm and use Go.

目录

• 目录
• 一、排序算法
  • 1. 冒泡排序
  • 2. 插入排序
  • 3. 选择排序
  • 4. 归并排序
  • 5. 快速排序
  • 6. 计数排序
  • 7. 堆排序
• 二、二分查找
• 三、数据结构
  • 1. 二叉树
  • 2. 链表
  • 3. 栈
  • 4. 队列
  • 5. 堆

一、排序算法

常用排序算法汇总

1. 冒泡排序

//冒泡排序，a是数组，n表示数组大小
func BubbleSort(a []int, n int) {
    if n <= 1 {
        return
    }
    for i := 0; i < n; i++ {
        // 提前退出标志
        flag := false
        for j := 0; j < n-i-1; j++ {
            if a[j] > a[j+1] {
                a[j], a[j+1] = a[j+1], a[j]
                //此次冒泡有数据交换
                flag = true
            }
        }
        // 如果没有交换数据，提前退出
        if !flag {
            break
        }
    }
}

2. 插入排序

// 插入排序，a表示数组，n表示数组大小
func InsertionSort(a []int, n int) {
    if n <= 1 {
        return
    }
    for i := 1; i < n; i++ {
        value := a[i]
        j := i - 1
        //查找要插入的位置并移动数据
        for ; j >= 0; j-- {
            if a[j] > value {
                a[j+1] = a[j]
            } else {
                break
            }
        }
        a[j+1] = value
    }
}

3. 选择排序

// 选择排序，a表示数组，n表示数组大小
func SelectionSort(a []int, n int) {
    if n <= 1 {
        return
    }
    for i := 0; i < n; i++ {
        // 查找最小值
        minIndex := i
        for j := i + 1; j < n; j++ {
            if a[j] < a[minIndex] {
                minIndex = j
            }
        }
        // 交换
        a[i], a[minIndex] = a[minIndex], a[i]

    }
}

4. 归并排序

// 归并排序
func MergeSort(a []int, n int) {
    if n <= 1 {
        return
    }
    mergeSort(a, 0, n-1)
}

func mergeSort(a []int, start, end int) {
    if start >= end {
        return
    }
    mid := (start + end) / 2
    mergeSort(a, start, mid)
    mergeSort(a, mid+1, end)
    merge(a, start, mid, end)
}

func merge(a []int, start, mid, end int) {
    tmpArr := make([]int, end-start+1)

    i := start
    j := mid + 1
    k := 0

    for ; i <= mid && j <= end; k++ {
        if a[i] < a[j] {
            tmpArr[k] = a[i]
            i++
        } else {
            tmpArr[k] = a[j]
            j++
        }
    }

    for ; i <= mid; i++ {
        tmpArr[k] = a[i]
        k++
    }
    for ; j <= end; j++ {
        tmpArr[k] = a[j]
        j++
    }
    copy(a[start:end+1], tmpArr)
}

5. 快速排序

func QuickSort(a []int, n int) {
    separateSort(a, 0, n-1)
}

func separateSort(a []int, start, end int) {
    if start >= end {
        return
    }
    i := partition(a, start, end)
    separateSort(a, start, i-1)
    separateSort(a, i+1, end)
}

func partition(a []int, start, end int) int {
    // 选取最后一位当对比数字
    pivot := a[end]

    i := start
    for j := start; j < end; j++ {
        if a[j] < pivot {
            if !(i == j) {
                // 交换位置
                a[i], a[j] = a[j], a[i]
            }
            i++
        }
    }
    a[i], a[end] = a[end], a[i]
    return i
}

6. 计数排序

func CountingSort(a []int, n int) {
    if n <= 1 {
        return
    }

    var max = math.MinInt32
    for i := range a {
        if a[i] > max {
            max = a[i]
        }
    }

    c := make([]int, max+1)
    for i := range a {
        c[a[i]]++
    }
    for i := 1; i <= max; i++ {
        c[i] += c[i-1]
    }

    r := make([]int, n)
    for i := range a {
        index := c[a[i]] - 1
        r[index] = a[i]
        c[a[i]]--
    }
    copy(a, r)
}

7. 堆排序

• 父节点：(x-1)/2
• 左子节点：2x+1
• 右子节点：2x+2
• 堆中最后一个父节点：(n/2)-1

func HeapSort(arr []int, n int) {
    // 1. 建立一个大顶堆
    buildMaxHeap(arr, n)
    length := n
    // 2. 交换堆顶元素与堆尾，并对剩余的元素重新建堆
    for i := n - 1; i > 0; i-- {
        swap(arr, 0, i)
        length--
        heapify(arr, 0, length)
    }
    // 3. 返回堆排序后的数组
    return
}

func buildMaxHeap(arr []int, n int) {
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, i, n)
    }
}

// 从上至下堆化
func heapify(arr []int, i int, n int) {
    left := 2*i + 1
    right := 2*i + 2
    largest := i

    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }
    if largest != i {
        swap(arr, i, largest)
        heapify(arr, largest, n)
    }
}

func swap(arr []int, i int, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}

二、二分查找

func BinarySearch(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }
    low := 0
    high := n - 1
    for low <= high {
        mid := (low + high) / 2
        if a[mid] == v {
            return mid
        } else if a[mid] > v {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1
}

// 递归写法
func BinarySearchRecursive(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }
    return bs(a, v, 0, n-1)
}

func bs(a []int, v int, low, high int) int {
    if low > high {
        return -1
    }
    mid := (low + high) / 2
    if a[mid] == v {
        return mid
    } else if a[mid] > v {
        return bs(a, v, low, mid-1)
    } else {
        return bs(a, v, mid+1, high)
    }
}

// 查找第一个等于给定值的元素
func BinarySearchFirst(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }

    low := 0
    high := n - 1

    for low <= high {
        mid := low + (high-low)>>1
        if a[mid] > v {
            high = mid - 1
        } else if a[mid] < v {
            low = mid + 1
        } else {
            if mid == 0 || a[mid-1] != v {
                return mid
            } else {
                high = mid - 1
            }
        }
    }
    return -1
}

// 查找最后一个值等于给定值的元素
func BinarySearchLast(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }

    low := 0
    high := n - 1

    for low <= high {
        mid := low + (high-low)>>1
        if a[mid] > v {
            high = mid - 1
        } else if a[mid] < v {
            low = mid + 1
        } else {
            if mid == n-1 || a[mid+1] != v {
                return mid
            } else {
                low = mid + 1
            }
        }
    }

    return -1
}

// 查找第一个大于等于给定值的元素
func BinarySearchFirstGT(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }

    low := 0
    high := n - 1
    for low <= high {
        mid := (high + low) >> 1
        if a[mid] > v {
            high = mid - 1
        } else if a[mid] < v {
            low = mid + 1
        } else {
            if mid != n-1 && a[mid+1] > v {
                return mid + 1
            } else {
                low = mid + 1
            }
        }
    }

    return -1
}

// 查找最后一个小于等于给定值的元素
func BinarySearchLastLT(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }

    low := 0
    high := n - 1
    for low <= high {
        mid := (low + high) >> 1
        if a[mid] > v {
            high = mid - 1
        } else if a[mid] < v {
            low = mid + 1
        } else {
            if mid == 0 || a[mid-1] < v {
                return mid - 1
            } else {
                high = mid - 1
            }
        }
    }

    return -1
}

三、数据结构

1. 二叉树

type Node struct {
    data interface{}
    left *Node
    right *Node
}

func NewNode(data interface{}) *Node {
    return &Node{data: data}
}

func (this *Node) String() string {
    return fmt.Sprintf("v:%+v, left:%+v, right:%+v", this.data, this.left, this.right)
}

2. 链表

单链表

package _6_linkedlist

import "fmt"

/*
单链表基本操作
author:leo
*/

type ListNode struct {
    next  *ListNode
    value interface{}
}

type LinkedList struct {
    head   *ListNode
    length uint
}

func NewListNode(v interface{}) *ListNode {
    return &ListNode{nil, v}
}

func (this *ListNode) GetNext() *ListNode {
    return this.next
}

func (this *ListNode) GetValue() interface{} {
    return this.value
}

func NewLinkedList() *LinkedList {
    return &LinkedList{NewListNode(0), 0}
}

//在某个节点后面插入节点
func (this *LinkedList) InsertAfter(p *ListNode, v interface{}) bool {
    if nil == p {
        return false
    }
    newNode := NewListNode(v)
    oldNext := p.next
    p.next = newNode
    newNode.next = oldNext
    this.length++
    return true
}

//在某个节点前面插入节点
func (this *LinkedList) InsertBefore(p *ListNode, v interface{}) bool {
    if nil == p || p == this.head {
        return false
    }
    cur := this.head.next
    pre := this.head
    for nil != cur {
        if cur == p {
            break
        }
        pre = cur
        cur = cur.next
    }
    if nil == cur {
        return false
    }
    newNode := NewListNode(v)
    pre.next = newNode
    newNode.next = cur
    this.length++
    return true
}

//在链表头部插入节点
func (this *LinkedList) InsertToHead(v interface{}) bool {
    return this.InsertAfter(this.head, v)
}

//在链表尾部插入节点
func (this *LinkedList) InsertToTail(v interface{}) bool {
    cur := this.head
    for nil != cur.next {
        cur = cur.next
    }
    return this.InsertAfter(cur, v)
}

//通过索引查找节点
func (this *LinkedList) FindByIndex(index uint) *ListNode {
    if index >= this.length {
        return nil
    }
    cur := this.head.next
    var i uint = 0
    for ; i < index; i++ {
        cur = cur.next
    }
    return cur
}

//删除传入的节点
func (this *LinkedList) DeleteNode(p *ListNode) bool {
    if nil == p {
        return false
    }
    cur := this.head.next
    pre := this.head
    for nil != cur {
        if cur == p {
            break
        }
        pre = cur
        cur = cur.next
    }
    if nil == cur {
        return false
    }
    pre.next = p.next
    p = nil
    this.length--
    return true
}

//打印链表
func (this *LinkedList) Print() {
    cur := this.head.next
    format := ""
    for nil != cur {
        format += fmt.Sprintf("%+v", cur.GetValue())
        cur = cur.next
        if nil != cur {
            format += "->"
        }
    }
    fmt.Println(format)
}

链表常用操作

package _7_linkedlist

import "fmt"

//单链表节点
type ListNode struct {
    next  *ListNode
    value interface{}
}

//单链表
type LinkedList struct {
    head *ListNode
}

//打印链表
func (this *LinkedList) Print() {
    cur := this.head.next
    format := ""
    for nil != cur {
        format += fmt.Sprintf("%+v", cur.value)
        cur = cur.next
        if nil != cur {
            format += "->"
        }
    }
    fmt.Println(format)
}

/*
单链表反转
时间复杂度：O(N)
*/
func (this *LinkedList) Reverse() {
    if nil == this.head || nil == this.head.next || nil == this.head.next.next {
        return
    }

    var pre *ListNode = nil
    cur := this.head.next
    for nil != cur {
        tmp := cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    }

    this.head.next = pre
}

/*
判断单链表是否有环
*/
func (this *LinkedList) HasCycle() bool {
    if nil != this.head {
        slow := this.head
        fast := this.head
        for nil != fast && nil != fast.next {
            slow = slow.next
            fast = fast.next.next
            if slow == fast {
                return true
            }
        }
    }
    return false
}

/*
两个有序单链表合并
*/
func MergeSortedList(l1, l2 *LinkedList) *LinkedList {
    if nil == l1 || nil == l1.head || nil == l1.head.next {
        return l2
    }
    if nil == l2 || nil == l2.head || nil == l2.head.next {
        return l1
    }

    l := &LinkedList{head: &ListNode{}}
    cur := l.head
    curl1 := l1.head.next
    curl2 := l2.head.next
    for nil != curl1 && nil != curl2 {
        if curl1.value.(int) > curl2.value.(int) {
            cur.next = curl2
            curl2 = curl2.next
        } else {
            cur.next = curl1
            curl1 = curl1.next
        }
        cur = cur.next
    }

    if nil != curl1 {
        cur.next = curl1
    } else if nil != curl2 {
        cur.next = curl2
    }

    return l
}

/*
删除倒数第N个节点
*/
func (this *LinkedList) DeleteBottomN(n int) {
    if n <= 0 || nil == this.head || nil == this.head.next {
        return
    }

    fast := this.head
    for i := 1; i <= n && fast != nil; i++ {
        fast = fast.next
    }

    if nil == fast {
        return
    }

    slow := this.head
    for nil != fast.next {
        slow = slow.next
        fast = fast.next
    }
    slow.next = slow.next.next
}

/*
获取中间节点
*/
func (this *LinkedList) FindMiddleNode() *ListNode {
    if nil == this.head || nil == this.head.next {
        return nil
    }
    if nil == this.head.next.next {
        return this.head.next
    }

    slow, fast := this.head, this.head
    for nil != fast && nil != fast.next {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
}

3. 栈

栈的接口

type Stack interface {
    Push(v interface{})
    Pop(v interface{})
    IsEmpty() bool
    Top() interface{}
    Flush()
}

基于数组的栈

type ArrayStack struct {
    // 数据
    data []interface{}
    // 栈顶指针
    top int
}

func NewArrayStack() *ArrayStack {
    return &ArrayStack{
        data: make([]interface{}, 0, 32),
        top: -1,
    }
}

func (this *ArrayStack) IsEmpty() bool {
    if this.top < 0 {
        return true
    }
    return false
}

func (this *ArrayStack) Push(v interface{}) {
    if this.top < 0 {
        this.top = 0
    } else {
        this.top += 1
    }

    if this.top > len(this.data)-1 {
        this.data = append(this.data, v)
    } else {
        this.data[this.top] = v
    }
}

func (this *ArrayStack) Pop() interface{} {
    if this.IsEmpty() {
        return nil
    }
    v := this.data[this.top]
    this.top -= 1
    return v
}

func (this *ArrayStack) Top() interface{} {
    if this.IsEmpty() {
        return nil
    }
    return this.data[this.top]
}

func (this *ArrayStack) Flush() {
    this.top = -1
}

func (this *ArrayStack) Print() {
    if this.IsEmpty() {
        fmt.Println("empty stack")
    } else {
        for i:= this.top; i>=0; i-- {
            fmt.Println(this.data[i])
        }
    }
}

基于链表的栈

package _8_stack

import "fmt"

/*
基于链表实现的栈
*/

type node struct {
    next *node
    val interface{}
}

type LinkedListStack struct {
    topNode *node
}

func NewLinkedListStack() *LinkedListStack {
    return &LinkedListStack{nil}
}

func (this *LinkedListStack) IsEmpty() bool {
    if this.topNode == nil {
        return true
    }
    return false
}

func (this *LinkedListStack) Push(v interface{}) {
    this.topNode = &node{next: this.topNode, val: v}
}

func (this *LinkedListStack) Pop() interface{} {
    if this.IsEmpty() {
        return nil
    }
    v := this.topNode.val
    this.topNode = this.topNode.next
    return v
}

func (this *LinkedListStack) Top() interface{} {
    if this.IsEmpty() {
        return nil
    }
    return this.topNode.val
}

func (this *LinkedListStack) Flush() {
    this.topNode = nil
}

func (this *LinkedListStack) Print() {
    if this.IsEmpty() {
        fmt.Println("empty stack")
    } else {
        cur := this.topNode
        for nil != cur {
            fmt.Println(cur.val)
            cur = cur.next
        }
    }
}

4. 队列

基于数组的队列

package queue

import "fmt"

type ArrayQueue struct {
    q        []interface{}
    capacity int
    head     int
    tail     int
}

func NewArrayQueue(n int) *ArrayQueue {
    return &ArrayQueue{make([]interface{}, n), n, 0, 0}
}

func (this *ArrayQueue) EnQueue(v interface{}) bool {

    if this.tail == this.capacity {
        // head == 0 && tail == capacity 表示整个队列都占满了
        if this.head == 0 {
            return false
        }
        // 数据搬移
        for i := this.head; i < this.tail; i++ {
            this.q[i-this.head] = this.q[this.tail]
        }
        // 搬移完之后，更新 head 和 tail
        this.tail -= this.head
        this.head = 0
    }

    this.q[this.tail] = v
    this.tail++
    return true
}

func (this *ArrayQueue) DeQueue() interface{} {
    if this.head == this.tail {
        return nil
    }
    v := this.q[this.head]
    this.head++
    return v
}

func (this *ArrayQueue) String() string {
    if this.head == this.tail {
        return "empty queue"
    }
    result := "head"
    for i := this.head; i <= this.tail-1; i++ {
        result += fmt.Sprintf("<-%+v", this.q[i])
    }
    result += "<-tail"
    return result
}

5. 堆

结构体声明

type Heap struct {
    a     []int
    n     int
    count int
}

🚩推荐阅读（由hexo文章推荐插件驱动）

• gops：Go 程序查看和诊断分析工具简介
• 使用 Gogs 自建 Git 服务
• 在 Gin 中使用 swaggo 自动生成 RESTful API 文档
• 使用 upx 压缩 go build 打包的可执行文件
• 服务器文件分片合并下载
• json tag 中的inline属性