Сортировка Четные и Нечетные числа в массиве при сохранении порядка

Question

http://www.geeksforgeeks.org/segregate-even-and-odd-numbers/ Я искал вопросы интервью и наткнулся на этот интересный вопрос. Алгоритм кажется достаточно простым, но мне было интересно, можно ли поддерживать порядок четных и нечетных чисел, сохраняя при этом временную сложность O (n) без использования дополнительного пространства.

Например

ввода: {12, 34, 45, 9, 8, 90, 3}

выход: {12, 34, 8, 90, 45, 9, 3}

Редактировать: Если это невозможно без дополнительного пространства, может ли он работать с целыми числами, только перестроенными на место? Как и в свопах, может произойти только в массиве

Answer 1

Я думаю, что это маловероятно, так как без дополнительного пространства (в зависимости от n) вам придется менять элементы и, таким образом, нарушать их (или вы можете переместить куски в массиве, но что, скорее всего, потребует нелинейного общего времени, с использованием других структур данных, таких как связанные списки, в этой проблеме не разрешено, насколько я понимаю).

Эта проблема может рассматриваться как стабильная не-сортировка на месте, где все четные элементы сопоставляются нулю, а все нечетные элементы сопоставляются друг с другом для сравнения, и, похоже, нет алгоритма, который бы соответствовал этим критериям (стабильный, время O(n), дополнительная память O(1)) (см., например, таблицу «Сравнение без сортировки» на https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms).