使用javascript执行数组备用排序的最佳算法？

Question

以下是我的面试问题.但我无法破解它,甚至无法想到如何完成这项工作.

var arr = [1,4,5,8,3,2,6,9,7,10];

备用排序的预期输出:

[10,1,9,2,8,3,7,4,6,5]

我尝试过:
我尝试将Math.max.apply(null,arr)和Math.min.apply(null,arr)切换成单独的空数组.但据说这个算法不是最优的.

Answer 1

我会对数组进行排序,然后迭代它,在每次迭代中从开始和结束(内循环计算的偏移)中选择值.对奇数阵列的最终检查将完成该过程.

let a = [1, 4, 5, 8, 3, 2, 6, 9, 7, 10];
a.sort((a, b) => a - b);
let b =[];
    
let l = a.length-1;  // micro optimization
let L = l/2;         // micro optimization
for(var i=0; i<L; i++) b.push( a[l-i] ,a[i] );
if(a.length%2) b.push( a[i] ); // add last item in odd arrays

console.log(b);

结果:

b =  [10, 1, 9, 2, 8, 3, 7, 4, 6, 5]

算法利益:

• 避免原始阵列(通过pop和shift)的改变,大大提高了性能.
• 预计算l和L循环之前,无需在每次迭代中重复计算.
• 在procces结束时的单个条件检验,处理奇数数组,略微提高了速度.

我准备了一些性能测试,其中包括一些提议的算法: Original Array(10项) 和Big Array(1000项)

Answer 2

这是一种方法:

var arr = [1, 4, 5, 8, 3, 2, 6, 9, 7, 10];

// Sort the source array
arr.sort((a, b) => a - b);

// This will be the final result
var result = [];

// Create two pointers
var a = 0,
  b = arr.length - 1;

while (result.length < arr.length) {
  // Push the elements from start and end to the result array
  result.push(arr[b]);

  // Avoid bug when array is odd lengthed
  if (a !== b) {
    result.push(arr[a]);
  }

  a++;
  b--;
}

console.log(result);

这个想法是有两个指针(a和b)从两个方向遍历排序的原始数组并附加元素result.