費雪耶茨洗牌

也被稱為 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++];
}