訂單數組，使所有正數第一次出現

Question

我在c＃中編寫代碼來排序數組，我想要在右側的所有負值和在左側的所有正值，不應該在減少爲了

namespace SortApp 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      int[] newInt = new int[] { 5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10 }; 
      int size = 12, i= 0;    // or newInt.Length 

      for (i = 0; i < newInt.Length; i++) 
      { 
       if (newInt[i] < 0 && newInt[size] > 0) 
       { 
        int temp = newInt[i]; 
        newInt[i] = newInt[size]; 
        newInt[size] = temp; 
        size--; 
       } 
      } 
      for (i = 0; i < newInt.Length; i++) 
      { 
       Console.Write(newInt[i]); 
       Console.Write(" "); 
      } 
     } 
    } 
} 

但輸出是這樣的（-20是在錯誤的一邊）：

5 10 9 8 -20 6 7 -14 15 -16 -4 -1 -2 

，但預期的輸出結果是：

5 10 9 8 15 6 7 -14 -20 -16 -4 -1 -2 

爲什麼我的代碼不能生成我的預期輸出？

Answer 1

您的解決方案錯誤地決定何時完成循環。此外，它無條件地在循環標題中增加i，即使指向負數，也不會遞減size。

這裏是你如何解決它：

for (i = 0; i < size ;) { 
    if (newInt[i] < 0 && newInt[size] >= 0) { 
     int temp = newInt[i]; 
     newInt[i] = newInt[size]; 
     newInt[size] = temp; 
     size--; 
     i++; 
     continue; 
    } 
    if (newInt[i] >= 0) { 
     i++; 
    } 
    if (newInt[size] < 0) { 
     size--; 
    } 
} 

這裏是一個demo on ideone。

您可以使用更易讀的標識符爲left和right指針重寫此循環，而不是使用i和size。這將使你的算法的代碼看起來更「對稱」，承認在其設計的對稱性：

int left = 0, right = newInt.Length-1; 
while (left < right) { 
    if (newInt[left] < 0 && newInt[right] >= 0) { 
     int temp = newInt[left]; 
     newInt[left] = newInt[right]; 
     newInt[right] = temp; 
     right--; 
     left++; 
     continue; 
    } 
    if (newInt[left] >= 0) { 
     left++; 
    } 
    if (newInt[right] < 0) { 
     right--; 
    } 
} 

這裏是an ideone link to the alternative implementation。

Answer 2

，如果你可以使用泛型和LINQ比最簡單的解決辦法是：

int[] newInt = new int[] { 5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10 }; 
newInt.ToList().Sort(); 
newInt.Reverse(); 
newInt = newInt.ToArray(); 

希望這將幫助！

Answer 3

嘗試這種解決方案：

var newInt = new[] {5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10}; 
var solution = newInt.GroupBy(i => i > 0). 
    SelectMany(g => g). 
    ToArray(); 

與算法的問題是，當你降低size，最終不得不爲負值newInt[size]點，並沒有進入if塊。

Answer 4

一個非常容易的簡單解決方案的一般想法是啓動一個索引，在數組的開頭稱爲left，另一個索引right在數組末尾。

遞增left，直到找到一個負數或直到left == right。當您輸入負數時，請將right減1，直至找到正數，或直至right == left。

如果left正在爲負數編制索引並且right正在索引正數，請交換兩個項目並重新開始遞增left。

的總體思路，沒有測試：

int left = 0; 
int right = a.Length-1; 
while (left < right) 
{ 
    if (a[left] < 0) 
    { 
     while (right > left) 
     { 
      if (a[right] >= 0) 
      { 
       // swap here 
       int temp = a[left]; 
       a[left] = a[right]; 
       a[right] = temp; 
       break; 
      } 
      --right; 
     } 
    } 
    ++left; 
} 

Answer 5

這產生期望的順序以最小的循環

int[] newInt = new int[] { 5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10 }; 
int lt = 0; 
int rt = newInt.Length - 1; 
while (true) { 
    // Find first negative number 
    while (newInt[lt] >= 0 && lt < rt) { 
     lt++; 
    } 

    // Find last positive number 
    while (newInt[rt] < 0 && rt > lt) { 
     rt--; 
    } 

    if (lt == rt) { 
     break; // Finished 
    } 

    // Swap 
    int temp = newInt[lt]; 
    newInt[lt] = newInt[rt]; 
    newInt[rt] = temp; 
} 
//TODO: Print result