このアルゴリズムをより効率的に書くには

Question

私は配列を2つに分割するアルゴリズムを書く必要があります。左辺は奇数で、右辺は偶数でなければなりません。両側は昇順にソートする必要があります。私は一時配列または既存のAPIを使用することはできません。

私は正常な方法を作ることができました。問題は100000の整数の配列であり、終了するまでに約15秒かかります。要件は0.1秒ですので、明らかに改善すべき点はたくさんあります。私は答えをスプーンフィードする人を探しているわけではなく、ちょうど正しい方向に微笑んでいます。私が書いた何かが悪いのか、それともなぜ私が知りたいのですが、私には何のコードも書かないでください！私がこれまで持って何

：

public static void delsortering(int[] a){   

     int oddnum = 0; 
     int n = a.length; 

     for(int k : a){ //finds how many odd numbers there are 
      if((k & 1) != 0) oddnum++; 
     } 

     for(int i = 0; i < n; i++){ 
      if((a[i] & 1) != 0){ //finds odd numbers 
       for(int j = 0; j < n; j++){ 
        if((a[j] & 1) == 0) //looks for even numbers to change pos with 
         switch(a, j, i); 
       } 
      } 
     } 

     for (int i = 0; i < n; i++){ 
      int from = i < oddnum ? 0 : oddnum; 
      int to = i < oddnum ? oddnum - i: n - i + oddetall; 
      int m = maxValue(a, from, to); //finds max value in specified range 
      switch(a, m, to - 1); //puts said max value at specified index 
     } 
    } 

は私が得ることができるすべての助けに感謝！

Answer 1

よりよい解決策は次のようになります

• はまずアレイ例えばx=0; y=N-1の最初と最後の要素を指す2つの変数を保ちます。
• 偶数を見つけるまでは、を右に移動してください（今までの数字はすべてです）yを左に移動して、奇数Y、Xを増加させ、そしてxまで同じ手順を繰り返し、yはあなたが見つける奇数最初の1 !!!）
• スワップ値x、yのまでさえある左-moving、yはを交差させます。

次に、右側にはevensが、左側には奇数の配列がありますが、順序はありません。だから、あなたは上記の手順の間に数列の数が分かれていることを知るためにオッズとエヴェンスを数えることができます。kのインデックスで言いましょう。

• Sort array[0 - k], Sort array[k+1 - N]。ソリューションであるO(n^2)よりも優れている両方の種類のために最初の部分のためのO(n)（x、yは一度だけ一方向に移動している）とO(nlogn)ようO(nlogn)：

複雑。