洗牌算法具体指的是什么？

1.背景介绍

洗牌算法具体指的是什么？

从字面意义上讲,就是实现洗牌的具体方法, 洗牌的目的是什么呢?在不考虑出老千的情况下,洗过的牌要足够乱才好,牌面随机分布,越乱越好! 在科研,计算机科学等很多领域都需要运用到概率分布的随机性, 所以说洗牌算法本质上是把一个给定元素集合打乱成为一个无序元素集合

2.知识剖析

ISHER–YATES SHUFFLE 洗牌算法概述

简单来说 Fisher–Yates shuffle 算法是一个用来将一个有限集合生成一个随机排列的算法（数组随机排序）。 这个算法生成的随机排列是等概率的,同时这个算法非常高效。 这是一个正确且高效的算法,在我们需要解决概率分布的随机性问题时,用这个就对了!(秒天秒地秒空气)

FISHER AND YATES 的原始版

Fisher–Yates shuffle 的原始版本， 最初描述在 1938 年的 Ronald Fisher 和 Frank Yates 写的书中， 他们使用纸和笔去描述了这个算法，并使用了一个随机数表来提供随机数。 它给出了 1 到 N 的数字的的随机排列，具体步骤如下：

写下从 1 到 N 的数字

取一个从 1 到剩下的数字（包括这个数字）的随机数 k

从低位开始，得到第 k 个数字（这个数字还没有被取出），把它写在独立的一个列表的最后一位

重复第 2 步，直到所有的数字都被取出

Fisher and Yates 的原始版是由自然语言描述的,他默认了人类不会选择自己已经选过的牌, 

然而计算机并没有这么聪明,计算机对于选过的牌是没有概念的,你必须告诉它如何处理这种情况, 否则它会重复选择,随着剩余元素的减少,它的效率会越来越低 到最后这种方法捞一张牌上来无疑是大海捞针 

所以我们需要针对计算机做出进一步的优化

Knuth 和 Durstenfeld 在Fisher 等人的基础上对算法进行了改进， 在原始数组上对数字进行交互，减小了空间复杂度 该算法的基本思想和 Fisher 类似，每次从未处理的数据中随机取出一个数字， 然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字

写下从 1 到 N 的数字

取一个从 1 到剩下的数字（包括这个数字）的随机数 k

从低位开始，从未处理的数据中得到第 k 个数字（这个数字还没有被取出），把它与当前未取出数列的最后一位数字进行交换

重复第 2 步，直到所有的数字都被交换

第 3 步将取出的数进行循环交换,直到所以数都交换了一边,得到了一个随机排列的数组

FISHER–YATES SHUFFLE变体:INSIDE-OUT ALGORITHM算法

各有优劣

Knuth-Durstenfeld Shuffle 是一个内部打乱的算法，算法完成后原始数据被直接打乱， 尽管这个方法可以节省空间，但在有些应用中可能需要保留原始数据，所以需要另外开辟一个数组来存储生成的新序列。

Inside-Out Algorithm 算法的基本思想是从前向后扫描数据， 把位置i的数据随机插入到第i个（包括第i个）位置中（假设为k），这个操作是在新数组中进行， 然后把原始数据中位置k的数字替换新数组位置i的数字。其实效果相当于新数组中位置k和位置i的数字进行交互。

评判一个洗牌算法优劣的标准有哪些?

算法必须是正确的,可以使用数学方法证明其正确性

算法应该是友好的，便于人们理解和交流，并且是机器可执行的

算法需要足够健壮，即当输入的数据非法或不合理时，也能适当的做出正确的反应或进行相应的处理

核心概念:算法复杂度

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。

时间复杂度是指执行算法所需要的计算工作量

最优时间复杂度 (Best-Case)

平均时间复杂度 (Average-Case)

最差时间复杂度 (Worst-Case)

空间复杂度是指执行这个算法所需要的内存空间

算法程序所占的空间；

输入的初始数据所占的存储空间；

算法执行过程中所需要的额外空间。