解答
1、将给定数组转化为一个二叉堆
2、定义一个指针,为数组的最后一位
1 2 3 4 5 6 7 8 | function sortArray (nums: number[]) { let N = nums.length - 1 // 从中位开始, 指针i, 向左移动 for(let i = Math.floor(N / 2); i >= 0; i--) { // 将 i 至 N 位元素堆有序直到数字组首位 sink(nums, i, N) } } |
3、将二叉堆的根节点(最大值)与当前指针位交换, 随后指针往左挪一位
4、将数组索引0开始到指针这调用一次sink(), 重新堆有序化
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | function sink (nums: number[], k: number, N: number) { while (k * 2 <= N) { let j = k * 2 // 子节点 if (j < N && nums[j] < nums[j + 1]) j++ if (nums[k] >= nums[j]) break; exch(nums, k, j) k = j } } function sortArray (nums: number[]) { let N = nums.length - 1 // 从中位开始, 指针i, 向左移动 for(let i = Math.floor(N / 2); i >= 0; i--) { // 将 i 至 N 位元素堆有序直到数字组首位 sink(nums, i, N) } while (N > 0) { exch(nums, 0, N--) // 交换首位与尾部, 并且指针左移 sink(nums, 0, N) // 指针移动后向堆有序化 } return nums } |
帖子还没人回复快来抢沙发