Go-堆排序

堆排序

• 算法实现

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)
    }
    // 结果就是逆序输出大根堆
}

• 测试代码

func main() {
    list := []int{8, 4, 8, 2, 9, 10, -3, 3, 20, 15, -1}
    function.HeapSort(list)
    fmt.Println(list)
}

• 排序结果

[-3 -1 2 3 4 8 8 9 10 15 20]

• 时间复杂度

O (nlgn)