生成以下结果的更好的算法是什么？

Question

我们有一个具有n数(非零)的数组的输入。

input--> [a1, a2, a3, a4, a5, ...., aN] (not in order)

现在我们希望输出如下所示

output--> Ai <= Aj >= Ak <= Al >= Am <= ....An.

我已经为这个问题写了一个代码，它很好，但没有优化，如果我谈到时间和空间复杂性，那么它肯定不是很好的解决方案。

function test(array){
    if(array && array.length){
        let newArray = [];
        array = array.sort();
        let m;
        if(array.length % 2){
            m = (array.length +1 )/2;
        }else{
            m = (array.length)/2;
        }
        newArray.push(array[m-1]);
        for(let i=1;i<=m;i++){
            if(array[m-1+i])
            newArray.push(array[m-1+i]);
            if(array[m-1-i])
            newArray.push(array[m-1-i]);
        }
        console.log(newArray);
        return newArray;
    }else{
        throw 'invalid argument';
    }
}

test([1,2,3,4]);

请帮助我，如果你有任何想法来优化，就像不使用其他变量(它将降低空间复杂性)。谢谢

Answer 1

您不需要对数组进行排序。只需对数组进行一次遍历，在每一步中只修复ai和ai+1。

假设a1 <= a2 >= a3...<= ai-1 >= ai

现在，如果ai <= ai+1，继续增加i。

如果ai > ai+1，则交换它们。

对称地，当i是偶数时，如果ai < ai+1，交换ai，ai+1。

Answer 2

您当前的算法按O(n log n)时间运行。开头的.sort()占用O(n log n)时间，而它下面的for循环以O(n)时间运行。因此，一种可能的改进是将sort函数改为使用计数排序(其时间复杂度为O(n + k)，其中k是从最低数字到最高数字的范围)。这将降低从O(n log n)到O(n + k)的总体时间复杂度，对于更大的集合，这将是一个显着的改进：

​

function countingSort(array) {
  const counts = array.reduce((a, num) => {
    a[num] = (a[num] || 0) + 1;
    return a;
  }, {});
  /*
  ok, maybe this is cheating
  return Object.entries(counts).reduce((arr, [num, occurrences]) => {
    for (let i = 0; i < occurrences; i++) {
      arr.push(Number(num));
    }
    return arr;
  }, []);
  */
  const sorted = [];
  const min = Math.min(...array);
  const max = Math.max(...array);
  for (let i = min; i <= max; i++) {
    for (let j = 0; j < counts[i]; j++) {
      sorted.push(i);
    }
  }
  return sorted;
}


function test(array){
    if(array && array.length){
        let newArray = [];
        array = countingSort(array);
        let m;
        if(array.length % 2){
            m = (array.length +1 )/2;
        }else{
            m = (array.length)/2;
        }
        newArray.push(array[m-1]);
        for(let i=1;i<=m;i++){
            if(array[m-1+i])
            newArray.push(array[m-1+i]);
            if(array[m-1-i])
            newArray.push(array[m-1-i]);
        }
        console.log(newArray);
        return newArray;
    }else{
        throw 'invalid argument';
    }
}

test([1,2,3,4]);

​

当两个数字之间没有很大的差距时，计数排序的性能最好。如果数字之间有很大的差距，您可以使用radix sort，它也在线性时间内运行(但编码有点复杂)。

(不过，如果你使用内置的sort函数，请确保使用.sort((a, b) => a - b)进行数字排序，否则结果数组将按词法排序，例如[1, 11, 2]，这是不可取的)

Answer 3

最后，这可能是一个更好的逻辑：

    function optimizedSort(array) {
    if(array && array.length){
        let temp;
        for(let i=0;i<array.length;i++){
            if((i+1)%2){
                // i is odd

                if(array[i]>=array[i+1]){
                    temp = array[i];
                    array[i] = array[i+1];
                    array[i+1] = temp;
                }

            }else{
                // i is even

                if(array[i]<=array[i+1]){
                    temp = array[i];
                    array[i] = array[i+1];
                    array[i+1] = temp;
                }
            }
        }
        console.log('********',array);
        return array;
    }else{
        throw 'invalid argument';
    }
}
optimizedSort([1,2,3,4]);