堆排序

func adjustHeap(a []int, pos int, len int) {
    for {
        // 计算孩子位置
        child := pos*2 + 1
        // 检查孩子是否越界
        if child >= (len - 1) {
            break
        }
        // 找出孩子中较大的那个
        if a[child+1] > a[child] {
            child++
        }
        // 检查孩子是否大于父亲，如果大于则交换
        if a[pos] < a[child] {
            // 父子交换
            a[pos], a[child] = a[child], a[pos]
            // 更新位置，指向子节点
            pos = child
        } else {
            // 如果子节点都小于父节点了，那就可以结束调整了
            break
        }
    }
}
func buildHeap(a []int) {
    // 从底层向上层构建，len(a)/2-1是第一个非叶子
    for i := len(a)/2 - 1; i >= 0; i-- {
        adjustHeap(a, i, len(a))
    }
}
func heapSort(a []int) {
    // 构建大顶堆
    buildHeap(a)
    fmt.Println("buildHeap over:", a)
    fmt.Println("===============================")
    // 首尾交换，重新构建大顶堆
    for i := len(a) - 1; i >= 0; i-- {
        a[0], a[i] = a[i], a[0]
        adjustHeap(a, 0, i)
    }
}

有问题

fmt.Println(heapSort([]int{1,-2147483648,2}))//-2147483648
fmt.Println(heapSort([]int{1,2,-2147483648}))//-2147483648

func sift(list []int, left, right int) {
    fIdx := left
    sIdx := fIdx*2 + 1
    // 构造大根堆
    for sIdx <= right {
        //判断左孩子:sIdx 右孩子:sIdx+1
        if sIdx < right && list[sIdx] < list[sIdx+1] {
            sIdx++
        }
        // 最终和大的儿子比较
        if list[fIdx] < list[sIdx] {
            // 交换
            list[fIdx], list[sIdx] = list[sIdx], list[fIdx]
            // 交换后重新检查被修改的子节点为大根堆
            fIdx = sIdx
            sIdx = 2*fIdx + 1
        } else {
            // 已经是大根堆
            break
        }
    }
}

func HeapSort(list []int) {
    length := len(list)
    //建立初始堆
    sift(list, 0, length-1)
    for idx := length / 2; idx >= 0; idx-- {
        // 从后往前调整
        sift(list, idx, length-1)
    }
    // 将大根堆的根节点和堆最后一个元素交换，重新对前面的 length - 1 调整堆
    for idx := length - 1; idx >= 1; idx-- {
        list[0], list[idx] = list[idx], list[0]
        sift(list, 0, idx-1)
    }
    // 结果就是逆序输出大根堆
}

参考

https://github.com/wangzheng0822/algo/blob/master/go/28_heap/heap_sort.go