如何更有效地編寫該算法

-1

我有一個任務，我必須編寫一個算法，將數組分成兩部分。左側應該是奇數，右側應該是偶數。雙方應按升序排序。我不允許使用臨時數組或現有的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 
     } 
    }

感謝所有幫助我能！

來源

2017-09-19 r4tchet

對於第一部分，分裂爲賠率/平衡：嵌套循環讓你n^2。你需要有兩個索引，從左邊走一個，右邊一個。當索引看到錯誤的數字時，它停止並讓其他索引走動。當兩者都看到錯誤的數字時，交換。當他們見面時完成。 – Arkadiy

您可以首先對數組-O（nlogn）進行排序，然後只需要按照另一個O（n）的順序拆分。 – Assafs

這不是Code Review的問題，因爲op明確要求提供一種算法，而不是改進他現有的代碼。 – coder

一個更好的解決辦法是：

首先保持兩個變量指向該陣列e.g x=0; y=N-1的第一和最後一個元素。
然後開始移動x到右邊，直到你找到一個偶數（所有的數字到現在爲止都是奇數 !!!），然後開始移動y到左邊，直到你找到一個奇數（所有的號碼，你檢查，同時降低 - 移動左y甚至直到第一個奇數你發現！）
交換值x，y，增加x，y和重複同樣的過程，直到X，Y得到越過。

然後，你有右evens和左奇數組，但沒有排序。所以你可以在上面的過程中計算出機率和平均數，以便知道數組中分隔的位置，比如k索引。

Sort array[0 - k], Sort array[k+1 - N]。

複雜性：O(n)用於第一部分（x，y是僅一次移動到一個方向）和O(nlogn)兩個種類所以O(nlogn)比O(n^2)這是你的溶液更好。

來源

2017-09-19 21:42:50 coder

如何更有效地編寫該算法

回答

相關問題