爱站程序员基地目录
- Fisher-Yates shuffle 算法简介
- 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 doj = random integer with 0 <= j <= iexchange 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)
| 随机数 | 原数组 | 新数组 |
|---|---|---|
| 0-8：6 | a = (1 2 3 4 5 6 7 8 9) | 交换a[8]和a[6] ：(1 2 3 4 5 6 9 8 7) |
| 0-7：5 | a = (1 2 3 4 5 6 9 8 7) | 交换a[7]和a[5] ：(1 2 3 4 5 8 9 6 7) |
| 0-6：4 | a = (1 2 3 4 5 8 9 6 7) | 交换a[6]和a[4] ：(1 2 3 4 9 8 5 6 7) |
| 0-5：2 | a = (1 2 3 4 9 8 5 6 7) | 交换a[5]和a[2] ：(1 2 8 4 9 3 5 6 7) |
| 0-4：1 | a = (1 2 8 4 9 3 5 6 7) | 交换a[4]和a[1] ：(1 9 8 4 2 3 5 6 7) |
| 0-3：0 | a = (1 9 8 4 2 3 5 6 7) | 交换a[3]和a[0] ：(4 9 8 1 2 3 5 6 7) |
| 0-2：2 | a = (4 9 8 1 2 3 5 6 7) | 交换a[2]和a[2] ：(4 9 8 1 2 3 5 6 7) |
| 0-1：0 | a = (4 9 8 1 2 3 5 6 7) | 交换a[1]和a[0] ：(9 4 8 1 2 3 5 6 7) |
shell实现
shuffle.sh :
#!/bin/bashshuffle() {local i tmp size max rand# 打乱顺序# Knuth-Fisher-Yates shuffle algorithmsize=${#my_array[*]}max=$(( 32767 / size * size ))# echo \"max: $max\"for ((i=size-1; i>0; i--)); dowhile (( (rand=$RANDOM) >= max )); do :; donerand=$(( rand % (i+1) ))# 交换tmp=${my_array[i]}my_array[i]=${my_array[rand]}my_array[rand]=$tmpecho ${my_array[*]}done}my_array=(1 2 3 4 5 6 7 8 9)shuffleecho ${my_array[*]}
执行效果：
$ sh shuffle.sh1 2 3 4 9 6 7 8 51 8 3 4 9 6 7 2 57 8 3 4 9 6 1 2 57 8 6 4 9 3 1 2 57 8 6 9 4 3 1 2 57 9 6 8 4 3 1 2 57 6 9 8 4 3 1 2 57 6 9 8 4 3 1 2 5
到此这篇关于shell实现Fisher–Yates shuffle洗牌算法介绍的文章就介绍到这了,更多相关shell Fisher–Yates shuffle洗牌算法内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！
您可能感兴趣的文章:
- shell脚本for循环实现文件和目录遍历
- Shell编程条件测试的实现
- shell 中小括号、中括号及大括号的区别解析
