Программа на Java для перемешивания массива

Дан массив размера N, и задача состоит в том, чтобы перетасовать элементы массива или любую другую перестановку. Используя Java, можно подумать о заполнении массива путем генерации случайных последовательностей элементов, присутствующих в массиве. Этот алгоритм называется алгоритмом перемешивания Фишера-Йейтса.

Алгоритм тасования Фишера – Йейтса работает с временной сложностью O (n). Предполагается, что функция rand () генерирует случайное число за время O (1). Начните с последнего элемента, замените его произвольно выбранным элементом из всего массива. Теперь рассмотрим массив от 0 до n-2 (размер уменьшен на 1) и повторяем, пока мы не дойдем до первого элемента.

Пример:

 Ввод: arr [] = {1, 2, 3, 4}
Вывод : arr [] = {3, 2, 4, 1}

Ввод : arr [] = {5, 2, 3, 4}
Вывод : arr [] = {2, 4, 3, 5}

Алгоритм:

 для i от n - 1 до 1 do
       j = случайное целое число с 0 <= j <= i
       поменяйте местами a [j] и a [i]

Ниже представлена реализация описанного выше подхода:

Сложность времени: O (N), где N - размер массива.

Вниманию читателя! Не переставай учиться сейчас. Ознакомьтесь со всеми важными концепциями Java Foundation и коллекций с помощью курса "Основы Java и Java Collections" по доступной для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .