如何将整数数组划分为偶数和奇数? [英] How to partition array of integers to even and odd?

问题描述

我想对数组进行分区(例如 [1,2,3,4,5,6,7,8])，第一个分区应该保留偶数值，第二个是奇数值(示例结果: [2,4,6,8,1,3,5,7]).

I want to partition an array (eg [1,2,3,4,5,6,7,8]), first partition should keep even values, second odd values (example result: [2,4,6,8,1,3,5,7]).

我设法使用内置的 Array.prototype 方法两次解决了这个问题.第一个解决方案使用 map 和 sort，第二个只有 sort.

I managed to resolve this problem twice with built-in Array.prototype methods. First solution uses map and sort, second only sort.

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

I would like to make a third solution which uses a sorting algorithm, but I don't know what algorithms are used to partition lists. I'm thinking about bubble sort, but I think it is used in my second solution (array.sort((el1, el2)=>(el1 % 2 - el2 % 2)))... I looked at quicksort, but I don't know where to apply a check if an integer is even or odd...

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

What is the best (linear scaling with array grow) algorithm to perform such task in-place with keeping order of elements?

推荐答案

如果你坚持就地方法而不是琐碎的标准 return [arr.filter(predicate), arr.filter(notPredicate)] 方法，可以使用两个索引轻松有效地实现，从数组的两侧运行并在必要时交换:

If you are insisting on an in-place approach instead of the trivial standard return [arr.filter(predicate), arr.filter(notPredicate)] approach, that can be easily and efficiently achieved using two indices, running from both sides of the array and swapping where necessary:

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
}

这篇关于如何将整数数组划分为偶数和奇数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！