冒泡排序

• 比较相邻元素大小，每一轮将最大移到末尾。

func bubbleSort(lst []int) {

    len := len(lst)
    for i := 0; i < len-1; i++ {
        for j := 0; j < len-i-1; j++ {
            if lst[j] > lst[j+1] {
                lst[j], lst[j+1] = lst[j+1], lst[j]
            }
        }
    }
}

选择排序

• 每一轮选一个最大与末尾交换。

func selectSort(lst []int) {

    len := len(lst)
    for i := len - 1; i > 0; i-- {
        maxIndex := i
        for j := 0; j < i-1; j++ {
            if lst[j] > lst[maxIndex] {
                maxIndex = j
            }
        }
        if maxIndex != i {
            lst[maxIndex], lst[i] = lst[i], lst[maxIndex]
        }
    }
}

插入排序

• 每一轮从未排序中选一个合适的元素插到已排序部分。

func isnertSort(lst []int) {

    len := len(lst)
    for i := 1; i < len; i++ {
        val := lst[i]
        j := i - 1
        for j >= 0 && lst[j] > val {
            lst[j+1] = lst[j]
            j--
        }
        lst[j+1] = val
    }
}

快速排序

• 将第一个值作为基准值，不断交换左右元素，使右边都大于基准值，左边都小于基准值。然后对左右两边子序递归处理。

func quickSort(lst []int, left int, right int) {

    if left >= right {
        return
    }

    pivot := lst[left] //第一个元素作为基准值，第一个元素的位置空了出来
    i, j := left, right
    for i < j {

        for i < j && lst[j] >= pivot { //从右往左找比基准值小的
            j--
        }
        if i < j {
            lst[i] = lst[j] //之前的空位存进去找到的比基准值小的值，又空出来一个位置
            i++             //跳过空位
        }
        for i < j && lst[i] <= pivot { //从左往右找到比基准值大的值
            i++
        }
        if i < j {
            lst[j] = lst[i] //之前的空位存进去比基准值大的值，又空出来一个位置
            j--
        }
    }

    lst[i] = pivot //空位填进去基准值

    quickSort(lst, left, i-1) //递归左子序
    quickSort(lst, i+1, right)

}

堆排序

• heapify 用于将一个节点及其子节点调整为大顶堆结构。
• 将整个数组构造成大顶堆。
• 不断交换堆顶到末尾，然后对剩余元素再建大顶堆。

// 建堆函数
func heapify(arr []int, n int, i int) {
    largest := i      // 初始化最大值下标为根节点
    l := 2*i + 1     // 左孩子的下标
    r := 2*i + 2     // 右孩子的下标

    // 如果左孩子存在并且大于根节点
    if l < n && arr[l] > arr[largest] {
        largest = l
    }

    // 如果右孩子存在并且大于上面找到的最大值
    if r < n && arr[r] > arr[largest] {
        largest = r
    }

    // 如果最大值不是根节点，交换它们
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i] // 交换
        heapify(arr, n, largest)                   // 对新的根节点重新调用heapify()
    }
}

// 堆排序函数
func heapSort(arr []int) {
    n := len(arr)

    // 构建大顶堆
    for i := n / 2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }

    // 一个个地从堆顶取出最大元素并放到数组末尾
    for i := n - 1; i >= 0; i-- {
        arr[i], arr[0] = arr[0], arr[i] // 交换堆顶元素和末尾元素
        heapify(arr, i, 0)             // 调整剩余元素的堆
    }
}