排序算法對于每個程序員來說，無疑是最常見的算法之一了。幾乎每個新入行的程序員，在面試之前都會準備好一兩種排序算法，例如冒泡排序、歸并排序、快速排序之類的。而面試官們很多也都會現場讓應聘者寫一個簡單的排序算法，來考驗對方的基本功怎么樣。

排序算法是讓無序的數據變得有序起來，而反過來，讓有一定順序的數據變得無序起來，那么這個算法就是洗牌算法。洗牌算法是生活中常見的一種基礎算法，最簡單的應用就是在打撲克牌的時候，隨機對撲克牌進行初始化。這時候要用到的算法就是洗牌算法。

大家在看王晶的賭王片里，肯定對于各種賭王的花式洗牌方法記憶很深刻。直觀上來講，洗牌算法非常好理解，無非就是把一副牌打亂。但是，什么樣的結果才叫亂，很多人則說不太清楚了。

數學上，一個好的洗牌算法需要達到的目標是：在洗過牌之后，任意一張牌出現在任意位置的概率是一樣的。例如對于n個數的洗牌算法，那么一張牌出現在任一位置的概率都是1/n，而洗牌算法最終的結果一共有n!種，即為數據的全排列。

這個目標很好理解，如果某種算法給出的結果是黑桃A在第一張的概率是50%，那么搞不好莊家就要吃大虧了。

所以洗牌算法最重要的就是結果要夠亂。

最為經典的洗牌算法是Fisher-Yates Shuffle算法。該算法由Ronald A. Fisher 和 Frank Yates兩人提出，其步驟如下：

1、初始化原始數組和新數組，數組長度設為n；

2、從還沒有處理的數據中（假如還剩下k個），隨機產生一個[0, k)之間的數字p；

3、從剩下的k個數中把第p個數字取出，按順序放入新數組；

4、重復步驟2和3直到數字全部取完；

5、此時新數組中即是洗牌之后的數組。

下面我們證明一下該算法具有足夠的隨機性，即每個元素被放置在新數組中的第i個位置的概率是1/n。

證明：一個元素m被放入第i個位置的概率P = 前i-1個位置選擇元素時沒有選中m的概率 * 第i個位置選中m的概率，即

其中，第一次在n個中選沒選到它，選中了另外n-1個的概率就是(n-1)/n，以此類推。

所以該算法具有足夠的隨機性。其時間復雜度為O(n*n),空間復雜度為O(n)。

后來Knuth和Durstenfeld在該算法基礎上進行了改變，在原始數組上對數字進行交換，從而節省了額外的數組空間。該算法的基本思想和Fisher算法類似，只不過每次從未處理的數據中隨機取出一個數字，然后把該數字放在數組的尾部，即把已經處理的數字存放在數組尾部。Knuth-Durstenfeld Shuffle算法是當前最為常用的洗牌算法。?