排序算法7-堆排序

2021-04-19  本文已影响0人  小杰66

堆排序

算法步骤:
1.创建一个堆
2.将堆构造成大顶堆,从最后一个非叶子节点往前,把最大值交换到堆首。
3.把堆首和堆尾互换,即把最大值放到了堆尾。
4.将堆的长度减1,即剔除了最大值然后重复开始步骤2,直到堆的尺寸为1。

function swap(arr, a, b) {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}
function heapify(arr, i, len) {
  let son = i * 2 + 1;
  if (son >= len) return;
  if (son + 1 < len && arr[son] < arr[son + 1]) son++;
  if (arr[i] < arr[son]) {
    swap(arr, i, son);
    heapify(arr, son, len);
  }
}

function heapSort(arr) {
  let len = arr.length;
  //第一次需要对所有非叶子节点操作
  for (let i = (len >> 1) - 1; i >= 0; i--) {
    heapify(arr, i, len);
  }
  //第二次开始由于只有顶节点兑换了,所以只需要对顶节点操作就行了
  for (let i = len - 1; i > 0; i--) {
    swap(arr, 0, i);
    len--;
    heapify(arr, 0, len);
  }
}
上一篇 下一篇

猜你喜欢

热点阅读