Как переупорядочить данные в массиве, чтобы два одинаковых элемента не располагались рядом друг с другом?

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

Пример

   1 1 2             =>   1 2 1 
   1 1 1 2 3         =>   1 2 1 3 1
   1 1 2 1 3 3 5 1   =>   1 2 1 3 1 3 5 1
   1 1 1 1 1 1 2     =>   1 2 1 1 1 1 1
   8 2 1 3 7 2 5     =>   rearrange not needed
   8 2 2 2 7 2 5 2   =>   8 2 7 2 5 2 2      // keep the original order

ИЗМЕНИТЬ: Добавлен пример, показывающий, что необходимо сохранять исходный порядок