A programozás világában a tömbök kezelése alapvető készség. Egy tömb egy közös folyamatként keverhető, ami magában foglalja az elemeinek véletlenszerű átrendezését. Ez az eljárás elengedhetetlen olyan dolgokhoz, mint például véletlenszerű játékcsomagok építése, statisztikai szimulációk futtatása, vagy csak az adatok véletlenszerűbb megjelenítése. Kezdetben sok logikát alkalmazhatunk egy tömb keverésére; különböző típusú gyűjteményi keretrendszereket használhatunk, mint például az ArrayList, hash készletek, linkelt listák stb. A tömb keverése eltérő módon történhet, és
Algoritmus egy tömb keverésére:
A következő az algoritmus egy tömb keverésére,
1. LÉPÉS: RAJT
2. LÉPÉS: Kezdje a tömb utolsó elemétől, és lépjen vissza az első elemhez.
3. LÉPÉS: Minden i indexű elemhez generáljon egy j véletlenszerű indexet úgy, hogy j a [0, i] tartományba esik.
4. LÉPÉS: Cserélje fel az i és j indexek elemeit.
5. LÉPÉS: Ismételje meg a 2. és 3. lépést a tömb összes elemére, az utolsó elemtől az elsőig visszafelé haladva.
6. LÉPÉS: VÉGE
Keverhetünk egy tömböt, amely különböző típusú elemeket tartalmaz, például egész számokat, karaktereket stb.
Fisher-yates keverési algoritmus:
A következő Java programot egész számokból álló tömb keverésére használják.
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; } } } Kimenet:
1 3 2 4 5
A kimenet eltérhet, ha a rendszerében hajtja végre, mert véletlenszerűen rendezi el az elemeket, és a megkevert tömböt adja ki.
Bonyolultságok:
A keverési algoritmus térbeli összetettsége O(1), mivel nem használ semmilyen extra adatstruktúrát, amely a tömb méretétől függ. A shuffleArray() metódusban használt Fisher-Yates shuffle algoritmus időbonyolultsága O(n), ahol n a tömb elemeinek száma.
Tömb keverése Java listák segítségével:
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)); } } Kimenet:
[4, 1, 7, 3, 6, 5, 2]
A kimenet eltérhet, ha a rendszerében hajtja végre, mert véletlenszerűen rendezi el az elemeket, és a megkevert tömböt adja ki.
Bonyolultságok:
leértékelési kép
A tér összetettsége is O(n). Ennek az az oka, hogy a Collections.shuffle() metódus a helyén módosítja az eredeti listát, és nem használ további adatstruktúrákat. Ennek a kódnak az időbonyolultsága O(n), ahol n a tömb elemeinek száma.
Karaktereket tartalmazó véletlenszerű tömb:
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; } } } Kimenet:
Shuffled Characters: [e, f, g, d, a, c, b]
A kimenet eltérhet, ha a rendszerében hajtja végre, mert véletlenszerűen rendezi el az elemeket, és a megkevert tömböt adja ki.
Bonyolultságok:
A keverési algoritmus térkomplexitása O(1), mert nem használ semmilyen extra adatstruktúrát, amely a tömb méretétől függ. A shuffleArray() metódusban használt program időbonyolultsága O(n), ahol n a tömbben lévő karakterek száma.
Következtetés:
A Java tömbök megkeverése kulcsfontosságú készség, amely képessé teszi a fejlesztőket az adatok véletlenszerű és elfogulatlan elrendezésének létrehozására. A feltárás során két hatékony megközelítést ismertettünk: a Collections.shuffle() metódust nem primitív tömbökhöz, valamint a Fisher-Yates keverési algoritmus megvalósítását primitív tömbökhöz. A Collections.shuffle() metódus leegyszerűsíti az objektumok vagy nem primitív tömbök keverési folyamatát a beépített funkciók kihasználásával. Másrészt a Fisher-Yates algoritmus hatékony és elfogulatlan módot biztosít a primitív tömbök keverésére, biztosítva a permutációk egységességét.