堆排序

简化版

//nums为要排序的数组
function heapify(heap, i, len) {
  let max = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  if (left < len && heap[left] > heap[max]) {
    max = left;
  }
  if (right < len && heap[right] > heap[max]) {
    max = right;
  }
  if (max !== i) {
    [heap[i], heap[max]] = [heap[max], heap[i]];
    heapify(heap, max, len);
  }
}
//第一步 建立最大堆（升序）从最后一个非叶子节点开始
for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
  heapify(nums, i, nums.length);
}
//第二步 排序
for (let i = nums.length - 1; i >= 0; i--) {
  [nums[0], nums[i]] = [nums[i], nums[0]];
  heapify(nums, 0, i);
}

堆排序

function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}
// 创建堆，其实是对data数组做一个结构调整，使其具有堆的特性
function buildHeap(data) {
  let len = data.length;
  for (let i = Math.floor(len / 2); i >= 0; i--) {
    heapAdjust(data, i, len);
  }
}
// 堆调整函数，即调整当前data为大根堆
function heapAdjust(data, i, len) {
  let child = 2 * i + 1;
  // 如果有孩子结点，默认情况是左孩子
  while (child <= len) {
    let temp = data[i];
    // 如果右孩子存在且其值大于左孩子的值，则将child指向右孩子
    if (child + 1 <= len && data[child] < data[child + 1]) {
      child = child + 1;
    }
    // 如果当前结点的值小于其孩子结点的值，则交换，直至循环结束
    if (data[i] < data[child]) {
      data[i] = data[child];
      data[child] = temp;
      i = child;
      child = 2 * i + 1;
    } else {
      break;
    }
  }
}
// 排序
function heapSort(data) {
  var data = data.slice(0);
  if (!(data instanceof Array)) {
    return null;
  }
  if (data instanceof Array && data.length == 1) {
    return data;
  }
  // 将data数组改造为“堆”的结构
  buildHeap(data);

  var len = data.length;
  // 下面需要注意的时候参数的边界，参考文档里面程序中i的值是不对的
  for (var i = len - 1; i >= 0; i--) {
    // 将第一位（最大值）移到数组最后一位，然后对前i-1位继续生成大根堆，如此往复
    swap(data, i, 0);
    heapAdjust(data, 0, i - 1);
  }
  return data;
}
const arr = [62, 88, 58, 47, 35, 73, 51, 99, 37, 93];
var newArr = heapSort(arr);