W świecie programowania manipulowanie tablicami jest podstawową umiejętnością. Tablicę można przetasować, co obejmuje losowe przestawianie jej elementów, w ramach jednego wspólnego procesu. Ta procedura jest niezbędna w przypadku tworzenia losowych talii do gier, przeprowadzania symulacji statystycznych lub po prostu bardziej losowego wyświetlania danych. Początkowo istnieje wiele logiki, które możemy zastosować do tasowania tablicy; możemy używać różnych typów struktur kolekcji, takich jak ArrayList, zestawy skrótów, listy połączone itp. tasowanie tablicy można wykonać inaczej i
Algorytm tasowania tablicy:
Poniżej znajduje się algorytm losowania tablicy,
KROK 1: POCZĄTEK
KROK 2: Zacznij od ostatniego elementu tablicy i wróć do pierwszego elementu.
KROK 3: Dla każdego elementu o indeksie i wygeneruj losowy indeks j taki, że j należy do zakresu [0, i].
KROK 4: Zamień elementy o indeksach i i j.
KROK 5: Powtórz kroki 2 i 3 dla wszystkich elementów tablicy, przechodząc od ostatniego elementu do pierwszego.
KROK 6: KONIEC
Możemy przetasować tablicę zawierającą różne typy elementów, takie jak liczby całkowite, znaki itp.
Algorytm tasowania Fishera-yatesa:
Poniższy program Java służy do tasowania tablicy składającej się z liczb całkowitych.
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; } } } Wyjście:
1 3 2 4 5
Dane wyjściowe mogą się różnić, jeśli wykonasz je w swoim systemie, ponieważ losowo układa elementy i generuje przetasowaną tablicę.
Złożoność:
Złożoność przestrzenna algorytmu tasowania wynosi O(1), ponieważ nie wykorzystuje on żadnych dodatkowych struktur danych zależnych od rozmiaru tablicy. Złożoność czasowa algorytmu shuffle Fishera-Yatesa użytego w metodzie shuffleArray() wynosi O(n), gdzie n jest liczbą elementów tablicy.
Tasowanie tablicy za pomocą list w Javie:
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)); } } Wyjście:
[4, 1, 7, 3, 6, 5, 2]
Dane wyjściowe mogą się różnić, jeśli wykonasz je w swoim systemie, ponieważ losowo układa elementy i generuje przetasowaną tablicę.
Złożoność:
co to jest Mac OS
Złożoność przestrzenna również wynosi O(n). Dzieje się tak, ponieważ metoda Collections.shuffle() modyfikuje oryginalną listę na miejscu i nie wykorzystuje żadnych dodatkowych struktur danych. Złożoność czasowa tego kodu wynosi O(n), gdzie n jest liczbą elementów w tablicy.
Potasuj tablicę zawierającą znaki:
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; } } } Wyjście:
Shuffled Characters: [e, f, g, d, a, c, b]
Dane wyjściowe mogą się różnić, jeśli wykonasz je w swoim systemie, ponieważ losowo układa elementy i generuje przetasowaną tablicę.
Złożoność:
Złożoność przestrzenna algorytmu tasowania wynosi O(1), ponieważ nie wykorzystuje on żadnych dodatkowych struktur danych zależnych od rozmiaru tablicy. Złożoność czasowa programu użytego w metodzie shuffleArray() wynosi O(n), gdzie n jest liczbą znaków w tablicy.
Wniosek:
Tasowanie tablicy w Javie to kluczowa umiejętność, która umożliwia programistom tworzenie losowych i bezstronnych układów danych. W trakcie tej eksploracji omówiliśmy dwa skuteczne podejścia: użycie metody Collections.shuffle() w przypadku tablic nieprymitywnych i implementację algorytmu tasowania Fishera-Yatesa w przypadku tablic pierwotnych. Metoda Collections.shuffle() upraszcza proces tasowania obiektów lub nieprymitywnych tablic, wykorzystując wbudowane funkcje. Z drugiej strony algorytm Fishera-Yatesa zapewnia skuteczny i bezstronny sposób tasowania prymitywnych tablic, zapewniając jednorodność permutacji.