Перестановка вектора

Question

предположим, у меня есть вектор:

 0  1  2  3  4  5
[45,89,22,31,23,76]

И перестановка его индексов:

[5,3,2,1,0,4]

Есть ли эффективный способ прибегнуть к нему в соответствии с перестановкой, получив таким образом:

[76,31,22,89,45,23]

Использование не более O (1) дополнительного пространства?

Answer 1

Да. Начиная с крайней левой позиции, мы помещаем элемент в его правильную позицию i, заменяя его (другим) неуместным элементом в этой позиции i. Здесь нам нужно дополнительное пространство O (1). Мы продолжаем обмениваться парами элементов, пока элемент в этом положении не будет правильным. Только тогда мы переходим к следующей позиции и делаем то же самое.

Пример:

[5 3 2 1 0 4] начальное состояние

[4 3 2 1 0 5] поменялся местами (5,4), 5 сейчас в правильном положении, но 4 все еще не в порядке

[0 3 2 1 4 5] поменялся местами (4,0), теперь и 4, и 0 находятся в правильных положениях, переходите к следующей позиции

[0 1 2 3 4 5] поменялся местами (3,1), теперь 1 и 3 находятся в правильных положениях, переходите к следующей позиции

[0 1 2 3 4 5] все элементы находятся в правильных положениях, конец.

Примечание :

Поскольку каждая операция подкачки помещает хотя бы один (из двух) элементов в правильное положение, нам нужно всего не более N таких перестановок.

Answer 2

Решение Заха очень хорошее.

Тем не менее, мне было интересно, почему есть необходимость сортировать. Если у вас есть перестановка индексов, используйте значения в качестве указателя на старый массив.

Это может устранить необходимость сортировки массива в первую очередь. Это не решение, которое можно использовать во всех случаях, но в большинстве случаев оно будет работать нормально.

Например:

a = [45,89,22,31,23,76];
b = [5,3,2,1,0,4]

Теперь, если вы хотите просмотреть значения в a , вы можете сделать что-то вроде (псевдокод):

for i=0 to 4
{
    process(a[i]);
}

Если вы хотите просмотреть значения в новом порядке, выполните:

for i=0 to 4
{
    process(a[b[i]]);
}

Как упоминалось ранее, этот раствор может быть достаточным во многих случаях, но не может быть в некоторых других случаях. В других случаях вы можете использовать решение Zach.But, но в тех случаях, когда это решение можно использовать, оно лучше, поскольку сортировка вообще не требуется.