无名阁,只为技术而生。流水不争先,争的是滔滔不绝。

常用算法-shuffle洗牌算法详解

学习与成长 dancy 12个月前 (11-24) 195次浏览 已收录 0个评论 扫描二维码

排序算法对于每个程序员来说,无疑是最常见的算法之一了。几乎每个新入行的程序员,在面试之前都会准备好一两种排序算法,例如冒泡排序、归并排序、快速排序之类的。而面试官们很多也都会现场让应聘者写一个简单的排序算法,来考验对方的基本功怎么样。排序算法是让无序的数据变得有序起来,而反过来,让有一定顺序的数据变得无序起来,那么这个算法就是洗牌算法。洗牌算法是生活中常见的一种基础算法,最简单的应用就是在打扑克牌的时候,随机对扑克牌进行初始化。这时候要用到的算法就是洗牌算法。

大家在看王晶的赌王片里,肯定对于各种赌王的花式洗牌方法记忆很深刻。直观上来讲,洗牌算法非常好理解,无非就是把一副牌打乱。但是,什么样的结果才叫乱,很多人则说不太清楚了。

数学上,一个好的洗牌算法需要达到的目标是:在洗过牌之后,任意一张牌出现在任意位置的概率是一样的。例如对于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算法是当前最为常用的洗牌算法。

python报typeerror错误,如何解决1(图文总结)

喜欢 (0)
[]
分享 (0)
关于作者:
发表我的评论
取消评论

评论审核已启用。您的评论可能需要一段时间后才能被显示。

表情 贴图 加粗 删除线 居中 斜体 签到