使用堆排序方法排序（45，78，57，25，41，89），初

[单选题]

使用堆排序方法排序（45，78，57，25，41，89），初始堆为（）

```
78,45,57,25,41,89
```
```
89,78,57,25,41,45
```
```
89,78,25,45,41,57
```
```
89,45,78,41,57,25
```

查看正确选项

修改昵称失败

首先建立完全二叉树

从最后一个叶子节点开始

第一次交换了57和89的位置

然后比较45和89，进行交换

再比较换下来的45，45不符合大根堆，与57交换

发表于 2019-05-29 21:11:08 回复(7)

叫我皮卡丘

发表于 2019-08-05 17:40:53 回复(2)

蒙古上单再世

堆排序 (Heap sort) 就是利用堆(假设利用大顶堆)进行排序的方法。基本思想是

构建初始堆
将根节点与末尾元素交换，进行堆构造（末尾元素不参与）
重复2过程，直到“堆”仅剩1个元素。

function HeapSort(arr) {
  arr = [0, ...arr]; // 方便左右子树表示
  //第一步，构建初始堆
  for (let i = ~~Math.length / 2; i > 0; i--) {
    buildHeap(arr, i, arr.length);
  }

  for (let i = arr.length; i > 1; i--) {
    // 交换
    [arr[1], arr[i - 1]] = [arr[i - 1], arr[1]];
    // 根元素与末尾元素交换，再构建大顶堆
    buildHeap(arr, 1, i - 1);
  }
  return arr.slice(1); // 移除添加的0元素
}

// 构造大顶堆
function buildHeap(arr, i, length) {
  let temp = arr[i];
  for (let j = 2 * i; j <= length; j *= 2) {
    if (arr[j] < arr[j + 1]) j++;
    if (temp > arr[j]) break;
    arr[i] = arr[j];
    i = j;
  }
  arr[i] = temp;
}

// ------- 测试
let arr = [3, 9, 5, 2, 6];
console.log(HeapSort(arr)); // [ 9, 5, 6, 2, 3 ]

arr = [5, 3, 9, 8, 3, 4];
console.log(HeapSort(arr)); // [ 8, 3, 3, 5, 9, 4 ]

发表于 2019-06-09 09:31:00 回复(0)