堆排序

var sortArray = function (nums) {
  if (nums.length === 1) return nums;
  return heapSort(nums);

  function heapSort (arr) {
    if (arr == null || arr.length < 2) return;

    for (let i = 0; i < arr.length; i++) {
      // 创造大顶堆
      heapInsert(arr, i);
    }

    let heapSize = arr.length;

    // 开始将 对顶元素与末尾元素 进行交换， 使得末尾元素最大
    swap(arr, 0, --heapSize);
    while (heapSize > 0) {
      heapify(arr, 0, heapSize);
      // 循环交换， 直到 arr[1] 停止;
      swap(arr, 0, --heapSize);
    }

    return arr;
  }

  function swap (arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

  // 调整堆
  function heapInsert(arr, index) {
    // 判断该元素与父元素谁大 （ 因为是大顶堆）
    while (arr[index] > arr[Math.floor((index - 1) / 2)]) {
      swap(arr, index, Math.floor((index - 1) / 2));
      // 重复判断， 直到最顶层
      index = Math.floor((index - 1) / 2);
    }
  }

  // 交换顶堆元素与末尾元素之后， 再次调整大顶堆
  function heapify (arr, index, heapSize) {
    // heapSize 表示堆大小， 以及一个数组我们可以认为它从 0到heapsize 是堆
    let left = index * 2 + 1; // 左子节点下标, 从左子节点进行判断，是否有子节点大于根节点， 如果有则交换，因为是大顶堆
    while (left < heapSize) {
      // 找到最大的子节点
      let largest = (left + 1 < heapSize) && arr[left + 1] > arr[left] ? left + 1 : left;

      // 如果子节点大于父节点则交换，再找有没有儿子比他大
      if (arr[largest] > arr[index]) {
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
      } else {
        break;  // 如果没有更大的，则大顶堆调整完成，退出这一次的调整，
                // 进行下一次交换
      }
    }
  }

}