Programa Java para mezclar una array

Dada una array de tamaño N, la tarea es barajar los elementos de la array o cualquier otra permutación. Usando Java, es posible pensar en rellenar la array generando secuencias aleatorias de los elementos presentes en la array. Este algoritmo se llama algoritmo aleatorio de Fisher-Yates.

El algoritmo de reproducción aleatoria de Fisher-Yates funciona en una complejidad de tiempo O(n). La suposición es que dar una función rand() genera un número aleatorio en tiempo O(1). Comience desde el último elemento, intercámbielo con un elemento seleccionado al azar de toda la array. Ahora considere la array de 0 a n-2 (tamaño reducido en 1), y repita hasta que lleguemos al primer elemento.

Ejemplo:

Input : arr[] = {1, 2, 3, 4}
Output: arr[] = {3, 2, 4, 1}

Input : arr[] = {5, 2, 3, 4}
Output: arr[] = {2, 4, 3, 5}

Algoritmo:

  for i from n - 1 downto 1 do
       j = random integer with 0 <= j <= i
       exchange a[j] and a[i]

A continuación se muestra la implementación del enfoque anterior:

// Program to jumble an array  using Java
import java.util.Random;
import java.io.*;
  
public class GFG {
    public static void shuffleanarray(int[] a)
    {
        int n = a.length;
        Random random = new Random();
        // generating random number from list
        random.nextInt();
        
        for (int i = 0; i < n; i++) {
            
            // using random generated number
            int change = i + random.nextInt(n - i);
            
            // swapping elements to shuffle
            int holder = a[i];
            a[i] = a[change];
            a[change] = holder;
        }
    }
    public static void main(String[] args)
    {
        int[] a = new int[] { 0, 1, 2, 3, 4, 5, 6 };
        shuffleanarray(a);
        System.out.print("arr[] = {");
        for (int i : a) {
            System.out.print(i + " ");
        }
        System.out.print("}");
    }
}

arr[] = {4 0 6 1 5 3 2 }

Complejidad de tiempo: O(N), donde N es el tamaño de una array.