排序算法

堆排：

func heapSort(arr []int) {
    len := len(arr)
    for i := len/2 - 1; i >= 0; i-- {
        adjust(arr, i, len - 1)
    }
    for i := len - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        adjust(arr, 0, i - 1)
    }
}
func adjust(arr []int, i, length int) {
    left := 2 * i + 1
    right := 2 * i + 2
    max := i
    if left <= length && arr[left] > arr[max]{
        max = left
    }
    if right <= length && arr[right] > arr[max]{
        max = right
    }
    if max != i{
        arr[max], arr[i] = arr[i], arr[max]
        adjust(arr, max, length)
    }
}

快排：

func quickSort(arr []int, left, right int) {
    if left >= right {
        return
    }
    l, r := left, right
    target := left
    for l < r {
        for l < r && arr[target] <= arr[r] {
            r--
        }
        for l < r && arr[target] >= arr[l] {
            l++
        }
        if l < r {
            arr[l], arr[r] = arr[r], arr[l]
        }
    }
    arr[target], arr[l] = arr[l], arr[target]
    quickSort(arr, left, l-1)
    quickSort(arr, l+1, right)
}

冒泡：

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

归并：

归并排序是稳定排序。每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度都是O(nlogn)。

func mergeSort(arr []int, left, right int){
    if left >= right{
        return
    }
    mid := (left + right) / 2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid + 1, right)
    merge(arr, left, mid, right)
}
func merge(arr []int, left, mid, right int){
    tmp := make([]int, right - left + 1)
    i, j, t := left, mid + 1, 0
    for i <= mid && j <= right{
        if arr[i] <= arr[j]{
            tmp[t] = arr[i]
            i++
        }else{
            tmp[t] = arr[j]
            j++
        }
        t++
    }
    for i <= mid{
        tmp[t] = arr[i]
        i++
        t++
    }
    for j <= right{
        tmp[t] = arr[j]
        j++
        t++
    }
    t = 0
    for left <= right{
        arr[left] = tmp[t]
        left++
        t++
    }
}