堆排序

以下代码为个人学习笔记。

const maxHeap = (nums, i, endIndex) => {
  for (; (i << 1) + 1 <= endIndex; ) {
    let l = (i << 1) + 1
    let r = (i << 1) + 2

    let large = i

    if (l <= endIndex && nums[l] > nums[i]) {
      large = l
    }

    if (r <= endIndex && nums[r] > nums[large]) {
      large = r
    }

    if (large !== i) {
      [nums[i], nums[large]] = [nums[large], nums[i]]
      i = large
    } else {
      break
    }
  }
}

const heapSort = nums => {
  let len = nums.length
  let endIndex = len - 1
  // 首先构造一个大根堆
  for (let i = (endIndex - 1) >> 1; i >= 0; i--) {
    maxHeap(nums, i, endIndex)
  }

  for (let i = endIndex; i >= 1; i--) {
    // 每次将堆首的元素与最后一个元素交换位置
    [nums[0], nums[i]] = [nums[i], nums[0]]
    endIndex -= 1
    maxHeap(nums, 0, endIndex)
  }
}
const nums = [5, 2, 3, 1]
heapSort(nums)

console.log(nums)