Vo svete programovania je manipulácia s poľami základnou zručnosťou. Pole môže byť premiešané, čo zahŕňa náhodné preusporiadanie jeho prvkov, ako jeden spoločný proces. Tento postup je nevyhnutný pre veci, ako je vytváranie náhodných herných balíčkov, spúšťanie štatistických simulácií alebo len náhodnejšie zobrazovanie údajov. Na začiatku existuje veľa logiky, ktorú môžeme použiť na premiešanie poľa; môžeme použiť rôzne typy rámcov kolekcií, ako napríklad ArrayList, hash sady, prepojené zoznamy atď. premiešanie poľa sa dá robiť inak a
Algoritmus pre miešanie poľa:
Nasleduje algoritmus pre miešanie poľa,
KROK 1: ŠTART
KROK 2: Začnite od posledného prvku poľa a prejdite späť k prvému prvku.
KROK 3: Pre každý prvok na indexe i vygenerujte náhodný index j tak, aby j bolo v rozsahu [0, i].
KROK 4: Vymeňte prvky na indexoch i a j.
5. KROK: Opakujte kroky 2 a 3 pre všetky prvky v poli a pohybujte sa späť od posledného prvku k prvému.
KROK 6: KONIEC
Môžeme zamiešať pole obsahujúce rôzne typy prvkov, ako sú celé čísla, znaky atď.
Fisher-yatesov algoritmus Shuffle:
Nasledujúci program Java sa používa na zamiešanie poľa pozostávajúceho z celých čísel.
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; } } } Výkon:
1 3 2 4 5
Výstup sa môže líšiť, ak ho spustíte vo svojom systéme, pretože náhodne usporiada prvky a vypíše premiešané pole.
Zložitosti:
Priestorová zložitosť algoritmu shuffle je O(1), pretože nepoužíva žiadne extra dátové štruktúry, ktoré závisia od veľkosti poľa. Časová zložitosť Fisher-Yatesovho algoritmu shuffle použitého v metóde shuffleArray() je O(n), kde n je počet prvkov v poli.
Miešanie poľa pomocou zoznamov v jazyku 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)); } } Výkon:
[4, 1, 7, 3, 6, 5, 2]
Výstup sa môže líšiť, ak ho spustíte vo svojom systéme, pretože náhodne usporiada prvky a vypíše premiešané pole.
Zložitosti:
ako premenovať adresár linux
Priestorová zložitosť je tiež O(n). Je to preto, že metóda Collections.shuffle() upravuje pôvodný zoznam na mieste a nepoužíva žiadne ďalšie dátové štruktúry. Časová zložitosť tohto kódu je O(n), kde n je počet prvkov v poli.
Zamiešať pole obsahujúce znaky:
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; } } } Výkon:
Shuffled Characters: [e, f, g, d, a, c, b]
Výstup sa môže líšiť, ak ho spustíte vo svojom systéme, pretože náhodne usporiada prvky a vypíše premiešané pole.
Zložitosti:
Priestorová zložitosť algoritmu shuffle je O(1), pretože nepoužíva žiadne extra dátové štruktúry, ktoré závisia od veľkosti poľa. Časová zložitosť programu použitého v metóde shuffleArray() je O(n), kde n je počet znakov v poli.
Záver:
Miešanie poľa v jazyku Java je kľúčová zručnosť, ktorá umožňuje vývojárom vytvárať náhodné a nezaujaté usporiadanie údajov. Počas tohto prieskumu sme pokryli dva efektívne prístupy: použitie metódy Collections.shuffle() pre neprimitívne polia a implementáciu algoritmu Fisher-Yates shuffle pre primitívne polia. Metóda Collections.shuffle() zjednodušuje proces miešania objektov alebo neprimitívnych polí využívaním vstavaných funkcií. Na druhej strane algoritmus Fisher-Yates poskytuje efektívny a nezaujatý spôsob premiešania primitívnych polí, čím sa zabezpečí jednotnosť v permutáciách.