Ve světě programování je manipulace s poli základní dovedností. Pole může být zamícháno, což zahrnuje náhodné přeskupení jeho prvků, jako jeden společný proces. Tento postup je nezbytný pro věci, jako je vytváření náhodných herních balíčků, spouštění statistických simulací nebo jen náhodnější zobrazování dat. Zpočátku existuje mnoho logiky, kterou můžeme použít k zamíchání pole; můžeme použít různé typy rámců kolekcí, jako je ArrayList, hash sady, propojené seznamy atd. zamíchání pole lze provést jinak a
Algoritmus pro míchání pole:
Následuje algoritmus pro míchání pole,
KROK 1: START
KROK 2: Začněte od posledního prvku pole a přejděte zpět k prvnímu prvku.
KROK 3: Pro každý prvek na indexu i vygenerujte náhodný index j takový, že j je v rozsahu [0, i].
KROK 4: Prohoďte prvky na indexech i a j.
KROK 5: Opakujte kroky 2 a 3 pro všechny prvky v poli a přejděte zpět od posledního prvku k prvnímu.
KROK 6: KONEC
Můžeme zamíchat pole obsahující různé typy prvků, jako jsou celá čísla, znaky atd.
Fisher-yates Shuffle algoritmus:
Následující program Java se používá k zamíchání pole složených 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ýstup:
1 3 2 4 5
Výstup se může lišit, pokud jej spustíte ve svém systému, protože náhodně uspořádá prvky a vydá zamíchané pole.
Složitosti:
Prostorová složitost algoritmu shuffle je O(1), protože nepoužívá žádné další datové struktury, které závisí na velikosti pole. Časová složitost algoritmu Fisher-Yates shuffle použitého v metodě shuffleArray() je O(n), kde n je počet prvků v poli.
Promíchání pole pomocí seznamů v Javě:
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ýstup:
[4, 1, 7, 3, 6, 5, 2]
Výstup se může lišit, pokud jej spustíte ve svém systému, protože náhodně uspořádá prvky a vydá zamíchané pole.
Složitosti:
ohraničení pomocí css
Prostorová složitost je také O(n). Je to proto, že metoda Collections.shuffle() upravuje původní seznam na místě a nepoužívá žádné další datové struktury. Časová složitost tohoto kódu je O(n), kde n je počet prvků v poli.
Zamíchat pole obsahující 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ýstup:
Shuffled Characters: [e, f, g, d, a, c, b]
Výstup se může lišit, pokud jej spustíte ve svém systému, protože náhodně uspořádá prvky a vydá zamíchané pole.
Složitosti:
Prostorová složitost algoritmu shuffle je O(1), protože nepoužívá žádné další datové struktury, které závisí na velikosti pole. Časová složitost programu použitého v metodě shuffleArray() je O(n), kde n je počet znaků v poli.
Závěr:
Zamíchání pole v Javě je klíčová dovednost, která umožňuje vývojářům vytvářet náhodná a nezaujatá uspořádání dat. Během tohoto průzkumu jsme pokryli dva efektivní přístupy: použití metody Collections.shuffle() pro neprimitivní pole a implementaci algoritmu Fisher-Yates shuffle pro primitivní pole. Metoda Collections.shuffle() zjednodušuje proces míchání objektů nebo neprimitivních polí využitím vestavěných funkcí. Na druhou stranu algoritmus Fisher-Yates poskytuje účinný a nezaujatý způsob promíchání primitivních polí, což zajišťuje jednotnost permutací.