堆排序

堆排序利用堆这种完全二叉树结构。构建大顶堆后，每次将堆顶最大值交换到数组末尾，再恢复剩余区间的堆性质。

实现

function heapSort(arr) {
  const result = [...arr]
  const heapify = (size, root) => {
    let largest = root
    const left = root * 2 + 1
    const right = root * 2 + 2

    if (left < size && result[left] > result[largest]) largest = left
    if (right < size && result[right] > result[largest]) largest = right

    if (largest !== root) {
      ;[result[root], result[largest]] = [result[largest], result[root]]
      heapify(size, largest)
    }
  }

  for (let i = Math.floor(result.length / 2) - 1; i >= 0; i--) {
    heapify(result.length, i)
  }

  for (let end = result.length - 1; end > 0; end--) {
    ;[result[0], result[end]] = [result[end], result[0]]
    heapify(end, 0)
  }

  return result
}

复杂度

• 时间复杂度：O(n log n)
• 空间复杂度：O(1)，不计算复制输入数组的空间
• 稳定性：不稳定

堆排序的最坏时间复杂度有保证，且原地排序，不依赖输入数据是否有序。