Стабильный вид двухзначного массива?

Question

У меня есть массив объектов. объекты имеют логическое значение, которое я хочу использовать в качестве ключа для сортировки массива (все объекты со значением true предшествуют всем объектам со значением false), но в остальном все остается в том же порядке.

Существует ли простое на месте решение O (n) для этого? Может быть, какой-нибудь вариант radix-sort ?

Answer 1

См. здесь для обсуждения этой темы. В принципе, вы можете иметь либо решение O (n), для которого требуется дополнительное пространство, либо решение O (n log n) на месте.

Answer 2

Хм. Со связанным списком это должно быть выполнимо - вы будете искать первую «ложную» запись и сохранять ее как «место вставки». (Если нет «ложных» записей, то вы все равно сделали :) Затем просто выполните итерацию по всему списку - если вы находитесь до места вставки и найдете «ложную» запись или если вы после места вставки и найдите «истинную» запись, затем переместите ее непосредственно перед «местом вставки». Пока что, так O(n).

Теперь вы можете преобразовать массив в связанный список в O(n) и скопировать данные back в массив в O(n). Поэтому я думаю, что это будет работать с точки зрения сложности - но это не на месте. Я подумаю, можно ли это сделать на месте ...

Answer 3

сортировка слиянием. O (n log n).