排序算法7-堆排序

堆排序

• 平均时间复杂度:O(nlogn)
• 最好情况:O(nlogn)
• 最坏情况:O(nlogn)
• 空间复杂度:O(1)
• 排序方式:In-place
• 稳定性:不稳定

算法步骤:
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);
  }
}