费雪耶茨洗牌

也被称为 Knuth shuffle 和 Durstenfeld-Fisher-Yates shuffle。这个 shuffle 采用了一系列 n 元素并将其洗牌。该算法是真正随机的，因为在混洗之后，阵列的每个排列都是同样可能的。

在 java 中：

public static void shuffle(E[] deck) {

    //From the end, swap each card with a random card from the unswapped portion.
    for(int i = deck.length - 1; i > 0; i--)
    {
        //Pick an element from [0,i], inclusive.
        int chosenCard = (int) (Math.random() * (i + 1));

        E temp = deck[i];
        deck[i] = deck[chosenCard];
        deck[chosenCard] = temp;
    }
}

请注意：替换元素必须来自[0，i]包含而不是[0，i]独占：否则，元素保留到位的数组的排列是不可能的，这不是真正随机的。

假设假设随机数采用 O(1) 生成，则算法就地运行并占用 O(n) 时间和空间。以这种方式混洗的数组可用于检索每个元素的 O(1) 摊销时间中的非重复元素。

E[] deck;
int drawIndex;

//Elements are taken from an index that advances.
public E drawUniqueCard()
{
    //Once all cards have been drawn, reshuffle the deck and draw from the top.
    if(drawIndex == deck.length)
    {
        shuffle(deck);
        drawIndex = 0;
    }
    //Pull the next card off the deck.
    return deck[drawIndex++];
}