堆排序

更新于 阅读 0

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

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)
标签:堆排序