前言
继续枯燥的排序算法。
正文
堆排序函数签名
function heap_sort(input: number[]) { // 1. 把无序数组构建最大堆 for (let i = (Math.floor((input.length - 2) / 2)); i >= 0; i--) { // a. down_just(input, i, input.length) // b. } // 2.循环删除堆顶元素，移到集合尾部，调整堆产生新的堆顶 for (let i = input.length - 1; i > 0; i--) { [input[i], input[0]] = [input[0], input[i]] // 下沉调整元素 down_just(input, 0, i) } }
a. input.length - 1 是最后一个堆节点的下标，input.length - 1 - 1 是最后一个堆节点，如果这最后一个堆节点的是靠右的节点，则除以 2 是父节点的下标 + 0.5；如果这最后一个堆节点是靠左的节点，则除以 2 就是父节点的下标。所以不管是靠左的节点还是靠右的节点，统一把小数省去就可以了，即 Math.floor((input.length - 1 - 1 ) / 2) 。其实这块要记住的是：左孩子的下标是父亲节点下标乘以2再加上1，即 childIndex = parentIndex + 1。
b. down_just 是堆节点下沉操作的函数
堆节点下沉操作函数签名
function down_just(input: number[], parent_index: number, length: number) { // temp 保存父节点值，用于最后的赋值 let temp = input[parent_index] let child_index = 2 * parent_index + 1 // a. while (child_index < length) { // 如果有右孩子，且右孩子大于左孩子，则定位到右孩子 if (child_index + 1 < length && input[child_index + 1] > input[child_index]) child_index++ // 如果父节点大于等于任何一个孩子的值，则直接跳出 if (temp >= input[child_index]) // A. break input[parent_index] = input[child_index] parent_index = child_index // b. child_index = 2 * child_index + 1 // c. } input[parent_index] = temp // d.
a. 孩子节点下标的计算方式：父亲“ 下标值 * 2 + 1，如果感觉比较抽象的话，脑海里可以想象一个 3 层的堆结果：默默数一下，第2个节点的孩子的下标是多少？”。
b. 类似于开始迭代，进入下一个轮回，前一代的孩子变成了这一代的父亲
c. 类似于开始迭代，进入一下个轮回，这一代的孩子是这一代父亲“ 下标值 * 2 + 1 ”
d. 不要写成了 child_index,因为触发到循环中断条件【父节点大于等于任何一个孩子的值】时，那时的父节点就应该赋最初保存的值了
A.切记此处的 temp 是最初需要下沉的那个元素，不要写成了每轮变化的 input[parent_index] [2021-08-18 补充~]
执行结果
let input = [5, 3, 44, 66, 5, 533, 45, 55, 65, 6, 35, 35, 77, 6, 3, 8, 4, 43, 7, 3, 20, 547559, 34, 44, 0] console.log("start -> ", input.toString()) heap_sort(input) console.log("end -> ", input.toString())
堆排序执行结果
没办法，算法慢慢解除的听多了，最后还是回归了基础，越是基础的越是要多理解，关键呀。
