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

排序算法是讓無序的數(shù)據(jù)變得有序起來，而反過來，讓有一定順序的數(shù)據(jù)變得無序起來，那么這個(gè)算法就是洗牌算法。洗牌算法是生活中常見的一種基礎(chǔ)算法，最簡單的應(yīng)用就是在打撲克牌的時(shí)候，隨機(jī)對撲克牌進(jìn)行初始化。這時(shí)候要用到的算法就是洗牌算法。

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

數(shù)學(xué)上，一個(gè)好的洗牌算法需要達(dá)到的目標(biāo)是：在洗過牌之后，任意一張牌出現(xiàn)在任意位置的概率是一樣的。例如對于n個(gè)數(shù)的洗牌算法，那么一張牌出現(xiàn)在任一位置的概率都是1/n，而洗牌算法最終的結(jié)果一共有n!種，即為數(shù)據(jù)的全排列。

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

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

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

1、初始化原始數(shù)組和新數(shù)組，數(shù)組長度設(shè)為n；

2、從還沒有處理的數(shù)據(jù)中（假如還剩下k個(gè)），隨機(jī)產(chǎn)生一個(gè)[0, k)之間的數(shù)字p；

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

4、重復(fù)步驟2和3直到數(shù)字全部取完；

5、此時(shí)新數(shù)組中即是洗牌之后的數(shù)組。

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

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

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

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

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