堆排序

堆排序如何工作？

• 建堆: 对输入数组原地调整, 建成大顶堆;
• 取最大值: 堆顶与堆底交换, 堆长度减一, 已排序区间扩大一位;
• 恢复堆: 从根开始自顶向下堆化;
• 重复以上两步 n-1 轮后数组升序;

自顶向下堆化如何实现？

• 比较节点 i 与其左右子节点, 记三者中最大者的下标为 ma;
• ma 等于 i 时无须继续, 跳出;
• 否则交换 i 与 ma, 令 i = ma 继续向下;
• 子节点下标越界即停止;

堆排序如何实现？

function siftDown(nums: number[], n: number, i: number): void {
  while (true) {
    const l = 2 * i + 1;
    const r = 2 * i + 2;
    let ma = i;
    if (l < n && nums[l] > nums[ma]) ma = l;
    if (r < n && nums[r] > nums[ma]) ma = r;
    if (ma === i) break;
    [nums[i], nums[ma]] = [nums[ma], nums[i]];
    i = ma;
  }
}

function heapSort(nums: number[]): void {
  // 建堆: 从最后一个非叶节点向前堆化
  for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
    siftDown(nums, nums.length, i);
  }
  // 取最大值: 交换堆顶与堆底, 再堆化剩余部分
  for (let i = nums.length - 1; i > 0; i--) {
    [nums[0], nums[i]] = [nums[i], nums[0]];
    siftDown(nums, i, 0);
  }
}

堆排序的特性是什么？

• 时间复杂度: O(n log n);
• 空间复杂度: O(1), 原地排序;
• 稳定性: 非稳定排序;
• 特点: 三种 O(n log n) 排序中唯一只需常数级额外空间的算法;