堆排序

将数组看成一个二叉堆，大致就是这样的

mermaid-diagram-20180618114344

父节点要大于子节点

简单一点，遍历整个树，每个节点都和父节点比较，如果大于父节点，则交换位置

tailrec fun casWithFather(array: IntArray, index: Int) {
    if (index == 0) {
        //第一个节点 do nothing
    } else {
        //和父节点比，如果大于父节点，递归和父节点比。
        val parent = (index + 1) / 2 - 1
        if (array[parent] < array[index]) {
            array.swap(index, parent)
            casWithFather(array, parent)
        }
    }
}

最大堆排序

经过上一步的处理，这个堆已经满足了父节点大于子节点，为一个最大堆。

如何来利用最大堆排序呢，我们取出最大的父节点，然后再生成最大堆。

  • 取出最大父节点
  • 与最尾端节点交换位置
  • 对新的堆排序（排除掉取出放在尾端的节点）
tailrec fun casWithChild(array: IntArray, farther: Int, end: Int) {
    val lc = farther * 2 + 1  //左节点
    val rc = farther * 2 + 2  //右节点
    if (lc >= end) {//到达了需要排序"堆"的终点
        return
    }
    val better = if (rc >= end || array[lc] > array[rc]) {
        lc
    } else {
        rc
    }
    if (array[farther] < array[better]) {
        array.swap(farther, better)
        casWithChild(array, better, end)
    }
}

完整调用

fun sort(array: IntArray) {
    for (i in 0..array.size - 1) {
        casWithFather(array, i)
    } //所有子节点都比父节点小
    for (i in (1..array.size - 1).reversed()) {//从尾端开始往前推
        array.swap(0, i)//把最大的0节点与该节点交换
        //再次从0开始排序，但是这个堆到i就结束了
        //因为i是上一步交换过来的已排序好的节点
        casWithChild(array, 0, i)
    }
}