arrays - 对数组中的偶数和奇数进行排序，同时保持顺序

Question

http://www.geeksforgeeks.org/segregate-even-and-odd-numbers/我在查找面试问题时发现了这个有趣的问题。该算法看起来很简单，但我想知道是否可以在不使用任何额外空间的情况下保持偶数和奇数的顺序，同时仍然保持 O(n) 的时间复杂度。

例如

input: {12, 34, 45, 9, 8, 90, 3}

output: {12, 34, 8, 90, 45, 9, 3}

编辑:如果没有额外的空间就不可能，它可以使用仅重新排列的整数吗？因为交换只能发生在数组中

Answer 1

我认为这不太可能，因为没有额外的空间(取决于n)，你将不得不交换元素，从而打乱它们(或者你可以移动数组中的 block ，但这可能需要非线性总体时间；据我所知，问题中不允许使用其他数据结构，例如链表)。

这个问题可以被视为稳定的就地非比较排序，其中所有偶数元素都映射到零，所有奇数元素都映射到一进行比较，并且似乎没有算法匹配这些标准(稳定，时间) O(n)，额外内存O(1))(参见 https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms 处的“非比较排序”表)。