题解 | 堆排序

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
function MySort( arr ) {
    // write code here
 if(!arr || arr.length < 2) return arr;

  // buildHeap
  let len = arr.length;
  for(let i = Math.floor(len/2 - 1); i >= 0; i--) {
    heapify(arr, len, i);
  }

  // sort
  for(let i = len - 1; i > 0; i--) {
      swap(arr, 0, i);
      heapify(arr, i, 0);
  }

  return arr;
}

function heapify(arr, len, cur) {
  let maxChildIndex = cur * 2 + 1;
  while(maxChildIndex < len) {
    if(maxChildIndex+1 < len && arr[maxChildIndex] < arr[maxChildIndex+1]) {
      maxChildIndex++;
    }
    if(arr[cur] < arr[maxChildIndex]) {
      swap(arr, cur, maxChildIndex);
      cur = maxChildIndex;
      maxChildIndex = cur * 2 + 1
    } else {
      break;
    }
  }
}

function swap(arr, index1, index2) {
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}
module.exports = {
    MySort : MySort
};

用了改进版的冒泡排序还是超时，果断改成堆排序。 建立大顶堆，然后交换头尾，在堆化。