整数の配列を偶数と奇数に分割する方法は？

Question

配列を分割したい（例えば[1,2,3,4,5,6,7,8]）、最初のパーティションは偶数の値、2番目の奇数の値（例の結果：[2,4,6,8,1,3,5,7]）を保持する必要があります。

私はこの問題を組み込みのArray.prototypeメソッドで2回解決することができました。第1の解決策は、mapおよびsortを使用し、次はsortです。

ソートアルゴリズムを使用する3番目のソリューションを作成したいと思いますが、リストをパーティション化するためにどのアルゴリズムが使用されているのかわかりません。私はバブルの並べ替えについて考えていますが、私はそれが私の2番目の解決策（array.sort((el1, el2)=>(el1 % 2 - el2 % 2))）で使用されていると思います... quicksortを見ましたが、整数が偶数か奇数ならチェックをどこに適用するのかわかりません...

要素の順序を維持したままそのようなタスクを実行する最適なアルゴリズム（配列が成長する直線的スケーリング）は何ですか？

Answer 1

簡単かつ効率的に、2つの指標を用いて、アレイの両側から実行し、必要に応じてスワップを達成することができる代わりに、些細な標準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

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

私はそれがO（n）だと信じています。楽しむ。

EDIT： それとも、本当に効率を気にしている場合：あなたはかなり簡単に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 3

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 4

。正面インデックスを開始し、背面の奇数インデックスを開始します。次に、偶数番号の最初のブロックをスキップして配列を調べます。

奇数番号を押すと、最後から逆方向に移動して最初の偶数番号を見つけます。次に、偶数と奇数を入れ替えます。

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]になります。配列は分割されていますが、奇数は元の配列と同じ相対順序ではありません。