列举官方三个可通过的算法：快速排序(需优化)、归并排序、堆排序

快速排序

简单版

Node.js内存溢出(JavaScript heap out of memory)版本

/**
 * JS简单版快速排序
 * @param {number[]} arr
 * @returns {number[]}
 */
function quickSortWithExtraArr(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const pivotIdx = arr.length - 1; // 将最后一位作为基准值
  const left = arr.filter((x) => x < arr[pivotIdx]);
  const mid = arr.filter((x) => x === arr[pivotIdx]);
  const right = arr.filter((x) => x > arr[pivotIdx]);
  return [...quickSortWithExtraArr(left), ...mid, ...quickSortWithExtraArr(right)];
}

常规版

会超时，原题的测试参数有时会导致快速排序复杂度变为O(n^2)，需要优化代码

/**
 * 快速排序标准版
 * @param {number[]} arr
 * @returns {number[]}
 */
export function quickSort(arr) {
  function qs(left = 0, right = arr.length - 1) {
    // 直到子数组剩下 不多于 1 个时退出
    if (left >= right) {
      return;
    }

    if (left < right) {
      // 将数组分类并选取基准
      const pivotIdx = partition(left, right);
      // 递归排序子数组
      qs(left, pivotIdx - 1);
      qs(pivotIdx + 1, right);
    }
  }
  function partition(left, right) {
    const pivot = arr[right];
    let j = left - 1;
    for (let i = left; i < right; i++) {
      if (arr[i] <= pivot) {
        j++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
    [arr[j + 1], arr[right]] = [arr[right], arr[j + 1]];
    return j + 1;
  }
  qs();
  return arr;

}

优化版

算法时间复杂度退化为O(n^2)，是因为参数含有大量有序与逆序子数组

  1. 对有序数组跳过检查

  2. 对基准值随机选取，降低平均每次排序的复杂度

/**
 * 快速排序标准版
 * @param {number[]} arr
 * @returns {number[]}
 */
function quickSort(arr) {
  /**
   *
   * @param {number[]} arr
   * @param {number} left
   * @param {number} right
   */
  function qs(arr, left = 0, right = arr.length - 1) {
	// 😎对于顺序的子数组跳过排序
    let ordered = true;
    for (let i = left; i < right; i++) {
        if (arr[i] > arr[i + 1]) {
            ordered = false;
            break;
        }
    }
    if (ordered) {
        return;
    }

    if (left >= right) {
      return;
    }
    if (left < right) {
      const pivotIdx = partition(arr, left, right);
      qs(arr, left, pivotIdx - 1);
      qs(arr, pivotIdx + 1, right);
    }
  }

  /**
   * 严格按照正统的快排方式书写
   * @param {number[]} arr
   * @param {number} left
   * @param {number} right
   * @returns {number} pivotIdx
   */
  function partition(arr, left, right) {
	// 😎选取随机基准值
    const r = Math.floor(Math.random() * (right-left+1)) + left;
    [arr[r], arr[right]] = [arr[right], arr[r]];
    let i = left - 1; // 小于等于基准值的最后一个比较元素的索引
    // right作为基准值，必须<=right遍历
    for (let j = left; j <= right; j++) {
      if (arr[j] <= arr[right]) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
    return i;
  }

  qs(arr);

  return arr;
}

归并排序

相比于快速排序，归并(分治)排序算法更稳定，严格对半分区，平局复杂度O(nlog(n))

/**
 *
 * @param {number[]} arr
 * @returns {number[]} res
 */
export function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  /**
   *
   * @param {number[]} left
   * @param {number[]} right
   * @returns {number[]}
   */
  function merge(left, right) {
    let res = [];
    let l = 0,
      r = 0;
    while (l < left.length && r < right.length) {
      if (left[l] <= right[r]) {
        res.push(left[l]);
        l++;
      } else {
        res.push(right[r]);
        r++;
      }
    }
  
    if (l < left.length) {
      res = res.concat(...left.slice(l));
    }
    if (r < right.length) {
      res = res.concat(...right.slice(r));
    }
    return res;
  }
  return merge(left, right);
}

堆排序

通过构造最大堆，循环找出最大值

 数学公式推导结论：
左孩子下标：2 i + 1
右孩子下标：2 i + 2
父节点下标：Math.floor((i - 1) / 2)
 最后一个非叶子节点下标：Math.floor(元素个数 / 2) - 1

/**
 * 堆排序
 * @param {number[]} arr
 * @returns {number[]} res
 */
export function heapSort(arr) {
  if (arr.length < 2) {
    return arr;
  }

  // 从最后一个非叶子节点开始构造最大堆
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    heapify(arr, i, arr.length);
  }

  // 堆排序,i作为构成最大堆的数组的大小
  for (let i = arr.length - 1; i > 0; i--) {
    // 把开头最大的元素移到末尾
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, 0, i);
  }
  return arr;

  
  /**
   * 构造最大堆（一颗完全二叉树，顶部根元素为最大值）
   * @param {number[]} arr
   * @param {number} i
   * @param {number} len 规定最大堆的范围,确保子节点不越界
   */
  function heapify(arr, i, len) {
    let parent = i; // 二叉树最大值
    const leftChild = 2 * i + 1;
    const rightChild = 2 * i + 2;
    if (leftChild < len && arr[parent] < arr[leftChild]) {
      parent = leftChild;
    }
    if (rightChild < len && arr[parent] < arr[rightChild]) 
      parent = rightChild;
    }
    // 交换保持根元素为最大值
    if (parent !== i) {
      [arr[parent], arr[i]] = [arr[i], arr[parent]];
      // 变化后需要对替换的元素(parent此时指向被交换元素的位置)重新堆化
      heapify(arr, parent, len);
    }
  }
}