选择排序

首先，找到数组中最小（最大）的那个元素，其次，将它和数组的第一个元素交换。再次，在剩下的元素中找到最小（最大）的元素，将它与数组的第二个元素交换位置。

func selectSort(array []int) {
    for i := 0; i < len(array); i ++ {
        max := i // 最大元素的索引
        for j := i + 1; j < len(array); j ++ {
            // 降序排序
            if array[max] < array[j] {
                max = j
            }
        }
        array[max], array[i] = array[i], array[max]
    }
}

插入排序

每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。

func insertSort(array []int) {
    for i := 1; i < len(array); i ++ {
        // 降序排序
        for j := i; j > 0 && array[j] > array[j - 1]; j -- {
            array[j], array[j - 1] = array[j - 1], array[j]
        }
    }
}

希尔排序（缩小增量排序）

将待排序数组按一定增量分组，分为多个子序列，然后对每个子序列进行插入排序，直到增量为 1 时， 进行最后一次插入排序。

func shellSort(array []int) {
    // 增量的初始值
    h := 1
    // 增量为 3 * n + 1 时，时间复杂度为 O(2 ^ (2 / 3))
    for h < len(array) / 3 {
        h = h * 3 + 1
    }
    for i := h; i > 0; i /= 3 {
        // 往后扫描
        for j := i; j < len(array); j ++ {
            // 往前扫描
            // 降序排序
            for k := j; k - i >= 0 && array[k] > array[k - 1]; k -- {
                array[k], array[k - i] = array[k - i], array[k]
            }
        }
    }
}

归并排序

归并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

func mergeSortFromFoot(array []int) { // 自底向上的并归排序
    temp := make([]int, len(array)) // 中间变量
    for i := 1; i < len(array); i *= 2 { // i 子数组大小
        for j := 0; j < len(array) - i; j += i * 2 { // j 数组索引
            if j + 2 * i - 1 < len(array) - 1 { // 防止溢出
                 merge(j, j + 2 * i - 1, j + i - 1, array, temp)
            } else {
                merge(j, len(array) - 1, j + i - 1, array, temp)
            }
        }
    }
}

func mergeSortFromTop(left int, right int, array []int, temp []int) { // 自顶向下的归并排序
    if left == right {
        return
    }
    mid := (left + right) >> 1 // 将 left + right 向右移动一位，得到平均值
    mergeSortFromTop(left, mid, array, temp)
    mergeSortFromTop(mid + 1, right, array, temp)
    merge(left, right, mid, array, temp)
}

func merge(left int, right, mid int, array []int, temp []int) {
    var (
        i int = left
        j int = mid + 1
        k int = 0
    )
    for ; i <= mid && j <= right; k ++ {
        if array[i] < array[j] {
            temp[k] = array[i]
            i += 1
        } else {
            temp[k] = array[j]
            j += 1
        }
    }
    for ; i <= mid; i, k = i + 1, k + 1 {
        temp[k] = array[i]
    }
    for ; j <= right; j, k = j + 1, k + 1 {
        temp[k] = array[j]
    }
    for l := left; l <= right; l ++ { // 将排序后的数据放回原数组
        array[l] = temp[l - left]
    }
}

快速排序

快速排序是对冒泡排序的一种改进，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

func fastSort(left, right int, array []int) {
    if left >= right {
        return
    }
    mark := sort(left, right, array) // 基准的下标
    fastSort(left, mark -  1, array)
    fastSort(mark + 1, right, array)
}

func sort(left, right int, array []int) int {
    var (
        mark int = array[left] // 基准的数值
        start int = left
        end int = right
    )
    for start < end {
        for ; start < end && array[end] >= mark; end -= 1 {}
        for ; start < end && array[start] <= mark; start += 1 {}
        array[start], array[end] = array[end], array[start]
    }
    array[left], array[start] = array[start], array[left]
    return start
}

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

func heapSort(array []int) {
    length := len(array)
    buildMaxHeap(array, length)
    for i := length - 1; i >= 0; i -- {
        array[0], array[i] = array[i], array[0]
        length -= 1
        heap(array, 0, length) // 从零构建大顶堆
    }
}

堆

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

func buildMaxHeap(array []int, length int) { // 构建大顶堆
    for i := length / 2; i >= 0; i -- {
        heap(array, i, length)
    }
}

func heap(array []int, i, length int) {
    var (
        left int = i * 2 + 1
        right int = i * 2 + 2
        max int = i
    )
    if left < length && array[max] < array[left] {
        max = left
    }
    if right < length && array[max] < array[right] {
        max = right
    }
    if max != i {
        array[i], array[max] = array[max], array[i]
        heap(array, max, length)
    }
}