JavaScript实现数组交替排序的最优算法：面试题求解

嘿，这个面试题我之前也碰到过！你的初始思路（反复提取最大最小值）逻辑是通顺的，但确实不够高效——每次调用Math.max和Math.min都要完整遍历一遍数组，时间复杂度会达到O(n²)，当数组规模变大时性能会明显下降。下面分享一种更优的解法：

核心思路：排序+双指针交替取值 #

1. 先排序：把原数组升序排序，这样我们就能通过首尾指针直接拿到当前的最大/最小值，不用每次遍历查找
2. 双指针遍历：用左指针指向当前最小元素，右指针指向当前最大元素，交替把右指针、左指针的元素加入结果数组，直到指针相遇或交叉

代码实现（JavaScript） #

const arr = [1,4,5,8,3,2,6,9,7,10];
// 先对数组做升序排序（注意不要修改原数组，所以用扩展运算符复制）
const sortedArr = [...arr].sort((a, b) => a - b);
const result = [];

let left = 0;
let right = sortedArr.length - 1;
// 标记当前是否取右指针的元素（先取最大，再取最小，循环交替）
let takeMaxFirst = true;

while (left <= right) {
  if (takeMaxFirst) {
    result.push(sortedArr[right]);
    right--;
  } else {
    result.push(sortedArr[left]);
    left++;
  }
  // 切换下一次要取的指针
  takeMaxFirst = !takeMaxFirst;
}

console.log(result); // 输出：[10,1,9,2,8,3,7,4,6,5]

复杂度分析 #

• 时间复杂度：排序的时间是O(n log n)，双指针遍历是O(n)，整体时间复杂度由排序主导，为O(n log n)，比你原来的O(n²)高效很多
• 空间复杂度：需要额外存储排序后的数组和结果数组，空间复杂度为O(n)（如果允许原地排序，还能节省一点空间，但结果数组是必须的）

补充：处理奇数长度数组 #

如果原数组长度是奇数（比如[1,2,3,4,5]），最后循环结束时left会等于right，此时上面的代码会自动把中间的元素加入结果数组，无需额外处理。

内容的提问来源于stack exchange，提问作者Prem