數組拼圖：分離偶數和奇數

Question

Segregating an array for even and odd numbers 這是重複的，但沒有解決方案可以保留元素的順序，O（n）時間和O（1）空間中是否存在這樣的解決方案。

我只是覺得這是在aove

Answer 1

我懷疑它給出的重複鏈接中提到的方法。

您可以使用鏈接文章中顯示的基本雙指針解決方案，但不是交換奇數元素，而是可以將數組元素滑動到左側並將奇數元素放在其位置;那就是O（n^2）時間和O（1）空間，就像插入排序一樣，因爲您必須訪問每個元素並可能將其滑動到整個數組的整個長度。

或者您可以保留O（n）時間，但是通過對輸入數組進行兩次遍歷，將偶數元素複製到輸出數組和第二遍奇數元素，從而使用O（n）空間。

但我沒有看到保存O（n）時間和O（1）空間的方法。

相反，如果你想在自己的偶數和奇數分區排序的所有元素，你可以使用標準的系統分類和比較功能是低於只有在較低索引元素一個甚至和更高索引元素b是奇數或者如果兩個元素具有相同的奇偶性和a < b;在C這是(a%2==0 && b%2==1) || (a%2==b%2 && a<b)。這就是排序中堆棧的O（n log n）時間和O（log n）空間，所以它不會保留原始的時間或空間範圍，也不能解決請求的問題。