排序算法无疑是每个程序员最常用的算法之一。几乎每个新手程序员在面试前都会准备一两个排序算法，比如冒泡排序、归并排序、快速排序之类的。而且很多面试官还会要求应聘者当场写一个简单的排序算法来测试对方的基本功。排序算法就是让无序的数据变得有序，反之，让有一定顺序的数据变得无序，那么这个算法就是一个洗牌算法。洗牌算法是生活中常见的基本算法。最简单的应用就是打扑克时随机初始化扑克牌。这时候要用到的算法就是洗牌算法。看过王晶赌侠电影的人，想必对赌徒花式洗牌的各种花式洗牌方式记忆犹新。直观来说，洗牌算法很好理解，无非就是洗一副牌。不过，什么样的结果才叫混沌，很多人都不是很清楚。在数学上，一个好的洗牌算法需要达到的目标是：洗牌后，任意一张牌出现在任意位置的概率都是相同的。例如，对于n个数字的洗牌算法，一张牌出现在任意位置的概率为1/n，洗牌算法的最终结果有n！类型，这是数据的完整排列。这个目标很容易理解。如果某种算法给出的结果是黑桃A是第一张牌的概率是50%，那么庄家可能会蒙受很大的损失。所以洗牌算法最重要的是结果要够乱。最经典的洗牌算法是Fisher-YatesShuffle算法。该算法由RonaldA.Fisher和FrankYates提出。步骤如下：1、初始化原数组和新数组，数组长度设置为n；2.从未处理的数据中（如果还剩k个），随机生成一个介于[0,k]之间的数p；3、从剩余的k个数中取出第p个数，依次放入一个新的数组中；4、重复步骤2和3，直到所有的号码都取完；5、此时新的数组就是洗牌后的数组。接下来，我们证明该算法具有足够的随机性，即每个元素被放置在新数组中第i个位置的概率为1/n。证明：元素m被放在第i个位置的概率P=在第i-1个位置选择元素时m没有被选中的概率*m在第i个位置被选中的概率，即就是，其中，第n次被选中，如果没有被选中，则选中另外n-1次的概率为(n-1)/n，以此类推。所以该算法具有足够的随机性。它的时间复杂度是O(n*n)，空间复杂度是O(n)。后来，Knuth和Durstenfeld根据这个算法进行了修改，在原来的数组上交换了数字，从而节省了额外的数组空间。该算法的基本思想类似于Fisher算法，只是每次从未处理的数据中随机取出一个数，然后将该数放在数组的末尾，即存储处理后的数在数组的末尾。Knuth-DurstenfeldShuffle算法是目前最常用的洗牌算法。
