使用Python编写的洗牌算法及运行规则
作者:CalmWind
时间:2024-01-28
浏览:1
给定一个数组,编写一个程序来生成数组元素的随机排列,这个问题也被称为“洗牌”或“随机化给定的数组”。洗牌算法中数组元素的每种排列的可能性都应该是相同的。洗牌算法是如何运行的给定的数组是arr[],一个简单的解决方法是创建一个辅助数组temp[],它最初是arr[]的副本。从temp[]中随机选择一个元素,将随机选择的元素复制到arr[0],然后从temp[]中删除选择的元素。重复相同的过程n次并继续将元素复制到arr[1]、arr[2]、...。该解决方案的时间复杂度为O(n^2)。Fisher-Yate

给定一个数组,编写一个程序来生成数组元素的随机排列,这个问题也被称为“洗牌”或“随机化给定的数组”。洗牌算法中数组元素的每种排列的可能性都应该是相同的。
洗牌算法是如何运行的
给定的数组是arr[],一个简单的解决方法是创建一个辅助数组temp[],它最初是arr[]的副本。从temp[]中随机选择一个元素,将随机选择的元素复制到arr[0],然后从temp[]中删除选择的元素。重复相同的过程n次并继续将元素复制到arr[1]、arr[2]、...。该解决方案的时间复杂度为O(n^2)。
Fisher-Yates shuffle算法的工作时间复杂度为O(n)。这里的假设是,我们得到一个函数rand(),它在O(1)时间内生成一个随机数。这个想法是从最后一个元素开始,并将其与整个数组(包括最后一个)中随机选择的元素交换。现在考虑从0到n-2的数组(大小减1),重复这个过程直到我们找到第一个元素。
下面是详细的算法:
对包含n个元素(索引0..n-1)的数组a进行洗牌
for i from n-1 downto 1 do j=random integer with 0<=j<=i exchange a[j]and a
Python实现洗牌算法
from random import randint def randomize(arr,n): for i in range(n-1,0,-1): j=randint(0,i+1) arr,arr[j]=arr[j],arr return arr arr=[1,2,3,4,5,6,7,8] n=len(arr) print(randomize(arr,n)) 输出结果:7 8 4 6 3 1 2 5
作者最新文章
3ds Max怎么自定义快捷键:修改按键映射与保存配置
2026-09-29 14:23
PS快捷键有哪些 photoshop工具快捷键怎么设置
2026-09-28 10:35
PDF转图片在线怎么用?资料整理的简单流程
2026-09-03 12:12
科大讯飞发布星火多模态大模型X2-VL,基于全国产算力训练
2026-08-25 16:21
雷军小米YU7装600斤车厘子慰问工程师被指违规 回应:封闭道路分装 交警称后排满载不合法
2026-08-25 15:23
上一篇:
优化PHP语言开发中的错误处理建议
下一篇:
深入理解Golang中删除数组元素的方式
热门文章
更多
精品专题
更多
Mac软件
更多
WINDOWS
更多










































