У світі програмування маніпулювання масивами є фундаментальним навиком. Масив можна перетасувати, що включає випадкове перевпорядкування його елементів, як один загальний процес. Ця процедура є важливою для таких речей, як створення рандомізованих ігрових колод, запуск статистичного моделювання або просто відображення даних у більш випадковому порядку. Спочатку існує багато логіки, яку ми можемо застосувати для перетасування масиву; ми можемо використовувати різні типи фреймворків колекції, такі як ArrayList, хеш-набори, пов’язані списки тощо. Перетасування масиву може виконуватися по-різному та
Алгоритм перетасування масиву:
Нижче наведено алгоритм для перемішування масиву,
КРОК 1: ПОЧАТОК
КРОК 2: Почніть з останнього елемента масиву і перейдіть назад до першого елемента.
КРОК 3: Для кожного елемента з індексом i згенеруйте випадковий індекс j, щоб j знаходився в діапазоні [0, i].
КРОК 4: Поміняти місцями елементи за індексами i та j.
КРОК 5: Повторіть кроки 2 і 3 для всіх елементів масиву, рухаючись назад від останнього елемента до першого.
КРОК 6: КІНЕЦЬ
Ми можемо перетасувати масив, що містить різні типи елементів, наприклад цілі числа, символи тощо.
Алгоритм перемішування Фішера-Йейтса:
Наступна програма Java використовується для перемішування масиву, що складається з цілих чисел.
ArrayShuffle.java
import java.util.Random; public class ArrayShuffler { public static void main(String[] args) { // Sample array of integers int[] array = {1, 2, 3, 4, 5}; // Shuffle the array shuffleArray(array); // Print the shuffled array for (int num : array) { System.out.print(num + ' '); } } public static void shuffleArray(int[] array) { Random rand = new Random(); for (int i = array.length - 1; i > 0; i--) { // Generate a random index between 0 and i (inclusive) int j = rand.nextInt(i + 1); // Swap the elements at indices i and j int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } Вихід:
1 3 2 4 5
Вихід може відрізнятися, якщо ви виконуєте його у своїй системі, оскільки він у випадковому порядку впорядковує елементи та виводить перетасований масив.
Складності:
Просторова складність алгоритму перетасування становить O(1), оскільки він не використовує жодних додаткових структур даних, які залежать від розміру масиву. Часова складність алгоритму перетасування Фішера-Єйтса, який використовується в методі shuffleArray(), становить O(n), де n – кількість елементів у масиві.
Перетасування масиву за допомогою списків у Java:
ShuffleArray.java
import java.util.Arrays; import java.util.Collections; import java.util.List; public class ShuffleArray { public static void main(String[] args) { Integer[] intArray = {1, 2, 3, 4, 5, 6, 7}; List intList = Arrays.asList(intArray); Collections.shuffle(intList); intList.toArray(intArray); // This line will not resize the array System.out.println(Arrays.toString(intArray)); } } Вихід:
[4, 1, 7, 3, 6, 5, 2]
Вихід може відрізнятися, якщо ви виконуєте його у своїй системі, оскільки він у випадковому порядку впорядковує елементи та виводить перетасований масив.
Складності:
що таке особливий символ
Просторова складність також дорівнює O(n). Це пояснюється тим, що метод Collections.shuffle() змінює вихідний список на місці та не використовує жодних додаткових структур даних. Часова складність цього коду дорівнює O(n), де n – кількість елементів у масиві.
Перетасувати масив, що містить символи:
ShuffleCharacters.java
import java.util.Arrays; import java.util.Random; public class ShuffleCharacters { public static void main(String[] args) { char[] charArray = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}; shuffleArray(charArray); System.out.println('Shuffled Characters: ' + Arrays.toString(charArray)); } public static void shuffleArray(char[] array) { Random rand = new Random(); for (int i = array.length - 1; i > 0; i--) { int j = rand.nextInt(i + 1); // Swap characters at indices i and j char temp = array[i]; array[i] = array[j]; array[j] = temp; } } } Вихід:
Shuffled Characters: [e, f, g, d, a, c, b]
Вихід може відрізнятися, якщо ви виконуєте його у своїй системі, оскільки він у випадковому порядку впорядковує елементи та виводить перетасований масив.
Складності:
Просторова складність алгоритму перетасування становить O(1), оскільки він не використовує жодних додаткових структур даних, які залежать від розміру масиву. Часова складність програми, що використовується в методі shuffleArray(), становить O(n), де n – кількість символів у масиві.
Висновок:
Перетасування масиву в Java — це важливий навик, який дає змогу розробникам створювати рандомізовані та неупереджені розташування даних. У цьому дослідженні ми розглянули два ефективні підходи: використання методу Collections.shuffle() для непримітивних масивів і впровадження алгоритму перетасування Фішера-Йетса для примітивних масивів. Метод Collections.shuffle() спрощує процес перетасування для об’єктів або непримітивних масивів, використовуючи вбудовані функції. З іншого боку, алгоритм Фішера-Єйтса забезпечує ефективний і неупереджений спосіб перетасувати примітивні масиви, забезпечуючи однаковість перестановок.