洗牌算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了洗牌算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2412字,纯文字阅读大概需要4分钟。
内容图文
![洗牌算法](/upload/InfoBanner/zyjiaocheng/637/e0a51e6d213d439d9f95765a780645d8.jpg)
描述
打乱一个数组。
所以我们面临两个问题:
1、什么叫做「真的乱」?
2、设计怎样的算法来打乱数组才能做到「真的乱」?
洗牌算法正确性的准则:产生的结果必须有 n! 种可能,否则就是错误的。**这个很好解释,因为一个长度为 n 的数组的全排列就有 n! 种,也就是说打乱结果总共有 n! 种。算法必须能够反映这个事实,才是正确的。
代码
// 得到一个在闭区间 [min, max] 内的随机整数 int randInt(int min, int max); // 第一种写法 void shuffle(int[] arr) { int n = arr.length(); /******** 区别只有这两行 ********/ for (int i = 0 ; i < n; i++) { // 从 i 到最后随机选一个元素 int rand = randInt(i, n - 1);// 不是0 /*************************/ swap(arr[i], arr[rand]); } } // 第二种写法 for (int i = 0 ; i < n - 1; i++) int rand = randInt(i, n - 1); // 第三种写法 for (int i = n - 1 ; i >= 0; i--) int rand = randInt(0, i); // 第四种写法 for (int i = n - 1 ; i > 0; i--) int rand = randInt(0, i);
解析
正确代码分析
// 假设传入这样一个 arr int[] arr = {1,3,5,7,9}; void shuffle(int[] arr) { int n = arr.length(); // 5 for (int i = 0 ; i < n; i++) { int rand = randInt(i, n - 1); swap(arr[i], arr[rand]); } }
for 循环第一轮迭代时,i = 0
,rand
的取值范围是 [0, 4]
,有 5 个可能的取值。
for 循环第二轮迭代时,i = 1
,rand
的取值范围是 [1, 4]
,有 4 个可能的取值。
后面以此类推,直到最后一次迭代,i = 4
,rand
的取值范围是 [4, 4]
,只有 1 个可能的取值。
可以看到,整个过程产生的所有可能结果有 n! = 5! = 5*4*3*2*1
种,所以这个算法是正确的。
第二种写法:
前面的迭代都是一样的,少了一次迭代而已。所以最后一次迭代时 i = 3
,rand
的取值范围是 [3, 4]
,有 2 个可能的取值。
所以整个过程产生的所有可能结果仍然有 5*4*3*2 = 5! = n!
种,因为乘以 1 可有可无嘛。所以这种写法也是正确的。
如果以上内容你都能理解,那么你就能发现第三种写法就是第一种写法,只是将数组从后往前迭代而已;第四种写法是第二种写法从后往前来。所以它们都是正确的。
// 第二种写法 // arr = {1,3,5,7,9}, n = 5 for (int i = 0 ; i < n - 1; i++) int rand = randInt(i, n - 1);
错误代码分析
void shuffle(int[] arr) { int n = arr.length(); for (int i = 0 ; i < n; i++) { // 每次都从闭区间 [0, n-1] // 中随机选取元素进行交换 int rand = randInt(0, n - 1);// 这里是0,错误 swap(arr[i], arr[rand]); } }
现在你应该明白这种写法为什么会错误了。因为这种写法得到的所有可能结果有 n^n 种,而不是 n! 种,而且 n^n 不可能是 n! 的整数倍。
比如说 arr = {1,2,3}
,正确的结果应该有 3!= 6 种可能,而这种写法总共有 3^3 = 27 种可能结果。因为 27 不能被 6 整除,所以一定有某些情况被「偏袒」了,也就是说某些情况出现的概率会大一些,所以这种打乱结果不算「真的乱」。
内容总结
以上是互联网集市为您收集整理的洗牌算法全部内容,希望文章能够帮你解决洗牌算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。