堆排序

定义

堆排序是一种基于比较的排序算法。堆排序可以看作是改进的选择排序。改进之处在于使用堆数据结构而不是线性搜索来找到最大或最小元素。

实现

• 使用递归。
• 使用扩展运算符（...）克隆原始数组arr。
• 使用闭包声明变量l和函数heapify。
• 使用for循环和Math.floor()结合heapify来从数组创建一个最大堆。
• 使用for循环来重复缩小考虑范围，使用heapify并根据需要交换值以对克隆数组进行排序。

const heapsort = arr => {
  const a = [...arr];
  let l = a.length;

  const heapify = (a, i) => {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let max = i;
    if (left < l && a[left] > a[max]) max = left;
    if (right < l && a[right] > a[max]) max = right;
    if (max !== i) {
      [a[max], a[i]] = [a[i], a[max]];
      heapify(a, max);
    }
  };

  for (let i = Math.floor(l / 2); i >= 0; i -= 1) heapify(a, i);
  for (i = a.length - 1; i > 0; i--) {
    [a[0], a[i]] = [a[i], a[0]];
    l--;
    heapify(a, 0);
  }
  return a;
};

heapsort([6, 3, 4, 1]); // [1, 3, 4, 6]

复杂度

该算法的平均时间复杂度为O(n log n)，其中n是输入数组的大小。