shell实现Fisher–Yates shuffle洗牌算法介绍_linux shell_

本文介绍使用shell语法实现Fisher–Yates shuffle 洗牌算法。

Fisher-Yates shuffle 算法简介

Fisher–Yates shuffle 洗牌算法可以用于对数组进行随机排列，它的时间复杂度为O(n)，伪代码如下：

 To shuffle an array a of n elements (indices 0..n-1): for i from n - 1 downto 1 do j = random integer with 0 <= j <= i exchange a[j] and a[i] 

假定有一个数组a=[1, 2, 3, 4, 5, 6, 7, 8, 9]，数组长度为n，打乱a中元素的具体迭代步骤如下：

生成一个[0, n-1]区间的随机数k；将第k个元素和第n-1个元素进行交换；进行下一轮迭代，生成一个[0, n-2]区间的随机数k，将第k个元素和第n-2个元素进行交换， 迭代次数为n-1次：从n-1取到1；最终得到一个打乱的数组。

下表是一个数组的具体打乱过程，打乱后的数组是(9 4 8 1 2 3 5 6 7)

shell实现

shuffle.sh :

 #!/bin/bash shuffle() { local i tmp size max rand # 打乱顺序 # Knuth-Fisher-Yates shuffle algorithm size=${#my_array[*]} max=$(( 32767 / size * size )) # echo "max: $max" for ((i=size-1; i>0; i--)); do while (( (rand=$RANDOM) >= max )); do :; done rand=$(( rand % (i+1) )) # 交换 tmp=${my_array[i]} my_array[i]=${my_array[rand]} my_array[rand]=$tmp echo ${my_array[*]} done } my_array=(1 2 3 4 5 6 7 8 9) shuffle echo ${my_array[*]} 

执行效果：

 $ sh shuffle.sh 1 2 3 4 9 6 7 8 5 1 8 3 4 9 6 7 2 5 7 8 3 4 9 6 1 2 5 7 8 6 4 9 3 1 2 5 7 8 6 9 4 3 1 2 5 7 9 6 8 4 3 1 2 5 7 6 9 8 4 3 1 2 5 7 6 9 8 4 3 1 2 5

到此这篇关于shell实现Fisher–Yates shuffle洗牌算法介绍的文章就介绍到这了,更多相关shell Fisher–Yates shuffle洗牌算法内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

提示： 本文由神整理自网络，如有侵权请联系本站删除！
本站声明：
1、本站所有资源均来源于互联网，不保证100%完整、不提供任何技术支持；
2、本站所发布的文章以及附件仅限用于学习和研究目的;不得将用于商业或者非法用途；否则由此产生的法律后果，本站概不负责！