В света на програмирането манипулирането на масиви е основно умение. Един масив може да бъде разбъркан, което включва произволно пренареждане на неговите елементи, като един общ процес. Тази процедура е от съществено значение за неща като изграждане на рандомизирани тестета за игри, провеждане на статистически симулации или просто показване на данни по-произволно. Първоначално има много логика, която можем да приложим, за да разбъркаме масив; можем да използваме различни видове рамки за събиране като ArrayList, хеш набори, свързани списъци и т.н. разбъркването на масив може да се направи по различен начин и
Алгоритъм за разбъркване на масив:
Следва алгоритъмът за разбъркване на масив,
ЕТАП 1: СТАРТ
СТЪПКА 2: Започнете от последния елемент на масива и се върнете назад към първия елемент.
СТЪПКА 3: За всеки елемент с индекс i, генерирайте произволен индекс j, така че j да е в диапазона [0, i].
СТЪПКА 4: Разменете елементите с индекси i и j.
СТЪПКА 5: Повторете стъпки 2 и 3 за всички елементи в масива, като се движите назад от последния елемент към първия.
СТЪПКА 6: КРАЙ
Можем да разбъркаме масив, съдържащ различни типове елементи като цели числа, знаци и т.н.
Алгоритъм за разбъркване на Fisher-yates:
Следната 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), защото не използва никакви допълнителни структури от данни, които зависят от размера на масива. Времевата сложност на алгоритъма за разбъркване на Fisher-Yates, използван в метода 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]
Резултатът може да се различава, ако го изпълните във вашата система, защото произволно подрежда елементите и извежда разбъркания масив.
Сложности:
css подравняване на текст
Пространствената сложност също е 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() за непримитивни масиви и прилагане на алгоритъма за разбъркване на Fisher-Yates за примитивни масиви. Методът Collections.shuffle() опростява процеса на разбъркване за обекти или непримитивни масиви чрез използване на вградени функционалности. От друга страна, алгоритъмът на Фишър-Йейтс предоставя ефективен и безпристрастен начин за разбъркване на примитивни масиви, осигурявайки еднаквост в пермутациите.