如何不借助List与Collections实现数组对象的高效随机洗牌？

你之前的两种洗牌实现都存在明显问题：

• 第一种直接随机选取整个数组的元素填充新数组，必然会出现重复，因为每次选择都没有排除已选过的元素
• 第二种添加校验逻辑的方式，时间复杂度飙升至O(n²)，数组规模越大，运行速度越慢

想要实现无重复、时间复杂度O(n)的洗牌，Fisher-Yates洗牌算法是最优选择，它能保证每个元素被随机分配到任意位置的概率均等，且无需额外的校验步骤。

不修改原数组的实现（生成新洗牌数组） #

如果需要保留原数组unshuffledDeck不变，可以先复制原数组再进行洗牌操作：

import java.util.Arrays;
import java.util.Random;

// ...

Random shuffleRandom = new Random();
Card[] shuffledDeck = Arrays.copyOf(unshuffledDeck, cardAmount); // 复制原数组

// 从数组末尾向前遍历
for (int i = cardAmount - 1; i > 0; i--) {
    // 生成0到i（包含i）的随机索引
    int j = shuffleRandom.nextInt(i + 1);
    // 交换当前位置i和随机位置j的元素
    Card temp = shuffledDeck[i];
    shuffledDeck[i] = shuffledDeck[j];
    shuffledDeck[j] = temp;
}

原地洗牌实现（直接修改原数组） #

如果不需要保留原数组，可以直接在原数组上操作，节省额外的空间：

import java.util.Random;

// ...

Random shuffleRandom = new Random();
int deckSize = unshuffledDeck.length;

for (int i = deckSize - 1; i > 0; i--) {
    int j = shuffleRandom.nextInt(i + 1);
    Card temp = unshuffledDeck[i];
    unshuffledDeck[i] = unshuffledDeck[j];
    unshuffledDeck[j] = temp;
}

算法原理 #

Fisher-Yates算法的核心逻辑是从后往前，每次为当前位置随机选取一个未被处理过的元素交换过来：

1. 从数组最后一个元素开始，逐个向前处理
2. 对于当前索引i，生成一个范围在[0, i]的随机索引j——这个范围保证了j指向的元素还没被分配到最终位置
3. 交换i和j位置的元素，此时i位置的元素就确定了，后续不会再被修改
4. 重复上述步骤直到处理完所有元素

这种方法的优势：

• 时间复杂度严格为O(n)，仅需一次遍历，每步操作都是常数时间
• 空间复杂度可选：复制数组为O(n)，原地洗牌为O(1)
• 洗牌结果无偏，每个元素出现在任意位置的概率完全相等

内容的提问来源于stack exchange，提问作者Only_Maxi