如何将整数数组划分为偶数和奇数？

Question

我想对数组进行分区（例如[1,2,3,4,5,6,7,8]），第一个分区应保留偶数，第二个分区应保留奇数（示例结果：[2,4,6,8,1,3,5,7]）。

我使用内置 Array.prototype 方法成功解决了这个问题两次。第一个解决方案使用 map 和 sort，第二个仅使用 sort.

我想做第三种解决方案，它使用排序算法，但我不知道使用什么算法来划分列表。我正在考虑冒泡排序，但我认为它用于我的第二个解决方案 (array.sort((el1, el2)=>(el1 % 2 - el2 % 2)))...我查看了 quicksort，但我不知道在哪里应用检查整数是偶数还是奇数...

在保持元素顺序的情况下就地执行此类任务的最佳（线性缩放与数组增长）算法是什么？

Answer 1

let evens = arr.filter(i=> i%2==0);
let odds = arr.filter(i=> i%2==1);
let result = evens.concat(odds);

我相信那是 O(n)。玩得开心。

编辑：或者如果你真的关心效率：

let evens, odds = []
arr.forEach(i=> {
if(i%2==0) evens.push(i); else odds.push(i);
});
let result = evens.concat(odds);

Answer 2

Array.prototype.getEvenOdd= function (arr) {
    var result = {even:[],odd:[]};
    if(arr.length){
      for(var i = 0; i < arr.length; i++){
        if(arr[i] % 2 = 0)
            result.odd.push(arr[i]);
        else
            result.even.push(arr[i]);
      }
    }
    return result ;
};

Answer 3

您可以很容易地在 O(n) 时间内就地完成此操作。在前面开始偶数索引，在后面开始奇数索引。然后，遍历数组，跳过第一个偶数块。

当你命中奇数时，从末尾向后移动找到第一个偶数。然后交换偶数和奇数。

代码看起来像这样：

var i;
var odd = n-1;
for(i = 0; i < odd; i++)
{
    if(arr[i] % 2 == 1)
    {
        // move the odd index backwards until you find the first even number.
        while (odd > i && arr[odd] % 2 == 1)
        {
            odd--;
        }
        if (odd > i)
        {
            var temp = arr[i];
            arr[i] = arr[odd];
            arr[odd] = temp;
        }
    }
}

请原谅任何语法错误。 Javascript 不是我的强项。

请注意，这不会保持相同的相对顺序。也就是说，如果你给它数组[1,2,7,3,6,8]，那么结果就是[8,2,6,3,7,1]。数组已分区，但奇数的相对顺序与原始数组中的顺序不同。

Answer 4

如果您坚持使用就地方法而不是琐碎的标准 return [arr.filter(predicate), arr.filter(notPredicate)] 方法，可以使用数组两侧的两个索引运行和必要时交换：

function partitionInplace(arr, predicate) {
    var i=0, j=arr.length;
    while (i<j) {
        while (predicate(arr[i]) && ++i<j);
        if (i==j) break;
        while (i<--j && !predicate(arr[j]));
        if (i==j) break;
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
    }
    return i; // the index of the first element not to fulfil the predicate
}

如何将整数数组划分为偶数和奇数？

How to partition array of integers to even and odd?

javascript

algorithm

data-partitioning