import java.util.Random;

public class BogoSort {
    
    /**
     * 猴子排序
     * 警告：此算法平均时间复杂度为 O((n+1)!)，仅用于教学演示
     * 对于超过 10 个元素的数组，可能需要数小时甚至数天才能完成排序
     */
    public static void sort(int[] arr) {
        Random random = new Random();
        int attempts = 0;
        
        while (!isSorted(arr)) {
            shuffle(arr, random);
            attempts++;
            
            // 安全保护，避免无限循环
            if (attempts > 1_000_000) {
                System.out.println("超过一百万次尝试，放弃排序");
                return;
            }
        }
        
        System.out.println("排序完成，共尝试 " + attempts + " 次");
    }
    
    /**
     * 检查数组是否有序
     */
    private static boolean isSorted(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
    
    /**
     * Fisher-Yates 洗牌算法
     */
    private static void shuffle(int[] arr, Random random) {
        for (int i = arr.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    /**
     * 猴子排序（泛型版本）
     */
    public static <T extends Comparable<T>> void sortGeneric(T[] arr) {
        Random random = new Random();
        int attempts = 0;
        
        while (!isSortedGeneric(arr)) {
            shuffleGeneric(arr, random);
            attempts++;
            if (attempts > 1_000_000) {
                System.out.println("超过一百万次尝试，放弃排序");
                return;
            }
        }
        System.out.println("排序完成，共尝试 " + attempts + " 次");
    }
    
    private static <T extends Comparable<T>> boolean isSortedGeneric(T[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i].compareTo(arr[i + 1]) > 0) {
                return false;
            }
        }
        return true;
    }
    
    private static <T> void shuffleGeneric(T[] arr, Random random) {
        for (int i = arr.length - 1; i > 0; i--) {
            int j = random.nextInt(i + 1);
            T temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}