Java 打亂數組的兩種公平隨機算法：Fisher-Yates 洗牌法 與 隨機索引集合法深度對比

算法一：Fisher-Yates 洗牌法（標準庫實現原理）

核心思想：從數組末尾向前遍歷，每次從 [0, i] 範圍隨機選一個索引 j，交換 array[i] 與 array[j]。單次遍歷、原地交換、O(n) 時間、O(1) 空間，且數學證明每種排列概率均等（1/n!）。

手寫實現

public static void shuffle(int[] array, Random random) {
    for (int i = array.length - 1; i > 0; i--) {
        int j = random.nextInt(i + 1);  // [0, i]
        swap(array, i, j);
    }
}

private static void swap(int[] array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

等價於 Collections.shuffle(list) / Arrays.shuffle(array) (Java 17+)。

算法二：隨機索引集合法（Set 去重 + 重排）

核心思想：利用 Set 不重複特性，生成 [0, n-1] 的隨機索引排列，再按新索引順序重構數組。

實現

public static void redistribute(int[] array) {
    Random random = new Random();
    Set<Integer> indexSet = new LinkedHashSet<>();  // 保持插入順序
    
    // 1. 生成不重複隨機索引集合
    while (indexSet.size() < array.length) {
        indexSet.add(random.nextInt(array.length));
    }
    
    // 2. 按新索引順序填充新數組
    int[] result = new int[array.length];
    int idx = 0;
    for (Integer newIndex : indexSet) {
        result[idx++] = array[newIndex];
    }
    
    // 3. 複製回原數組（或直接返回新數組）
    System.arraycopy(result, 0, array, 0, array.length);
}

深度對比

Random 類深度補充

• java.util.Random：線程安全但爭用鎖，高併發下性能瓶頸。內部用 AtomicLong CAS 更新種子。
• ThreadLocalRandom (JDK 7+)：線程本地、無鎖、高性能，並行流/多線程環境首選：ThreadLocalRandom.current().nextInt(n)。
• SecureRandom：密碼學強隨機，種子來自 OS 熵池（/dev/urandom），速度慢，僅用於安全敏感場景（Token、Key、UUID）。
• SplittableRandom (JDK 8+)：可分割、統計質量好、適合 Fork/Join 並行任務。