Предположим, что массив задан как a1, a2,..., ak, _ , a(k+1),..., an. Здесь символ подчеркивания (_) представляет собой пробел. Мы можем переместить любой элемент массива в это пространство. Мы можем повторять эту операцию любое количество раз. Можно ли отсортировать каждый массив с одним таким пробелом?
Можно ли отсортировать массив, используя одну временную переменную/пробел?
Ответы (3)
Да, это возможно.
Отсортированный массив — это просто конкретная перестановка этого массива.
Любая перестановка может быть достигнута последовательностью отдельных обменов.
А своп можно реализовать с помощью одного временного элемента.
(На самом деле можно отсортировать массив целочисленных типов без временного, используя операции XOR).
person
Bathsheba
schedule
14.10.2016
Спасибо. Я даже не знаю, есть ли у безвременной подкачки версия с XOR. а = а ^ б; б = а ^ б; а = а ^ б; или через плюс/минус: a = a + b; б = а - б; а = а - б;
- person khôi nguyễn; 14.10.2016
Существует несколько алгоритмов сортировки на месте. Наиболее примечательной из них является нерекурсивная версия быстрой сортировки (поскольку рекурсивная версия будет занимать место в стеке, пропорциональное количеству рекурсивных вызовов), которая в среднем дает вам сложность O(n log n).
Другая возможность — использовать менее эффективные алгоритмы, такие как сортировка вставками и пузырьковая сортировка, сложность которых равна O(n^2).
Что касается вашего конкретного вопроса, то есть использовать это конкретное пространство, вы можете использовать его для обмена, как сказала Вирсавия, но я бы не стал терять время, выполняя такую операцию.
Учтите также тот факт, что если у вас есть явное понятие «неиспользуемого пространства» в середине вашего массива, вы должны попытаться понять его семантику, то есть, каково будет его правильное размещение с точки зрения порядка. Если вы этого не сделаете и оставите его там, где он есть, вы окажетесь с «сломанным» инвариантом, и у вас возникнут трудности с реализацией алгоритмов, таких как бинарный поиск, в вашей коллекции.
person
alessandrolenzi
schedule
14.10.2016
Я еще не видел таких контейнеров в реальном коде, но самый простой для реализации алгоритм (не самый эффективный!) - это поменять местами пустые с первым элементом, затем поменять местами наименьший с пустым на первом месте, а затем предположить, что контейнер начинается со второго позицию и повторяйте до последней позиции, которая будет пустым пространством. В этом случае поменять местами просто означает заполнить пустое место и отметить другую позицию как пустую.
person
stefaanv
schedule
14.10.2016
