Как разбить массив целых чисел на четные и нечетные?

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

Если вы настаиваете на подходе на месте вместо тривиального стандарта 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
}

Answer 2

Вы можете сделать это на месте в 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 3

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 4

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 ;
};