本文介紹使用shell語(yǔ)法實(shí)現(xiàn)Fisher–Yates shuffle 洗牌算法。

Fisher-Yates shuffle 算法簡(jiǎn)介

Fisher–Yates shuffle 洗牌算法可以用于對(duì)數(shù)組進(jìn)行隨機(jī)排列，它的時(shí)間復(fù)雜度為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]

假定有一個(gè)數(shù)組a=[1, 2, 3, 4, 5, 6, 7, 8, 9]，數(shù)組長(zhǎng)度為n，打亂a中元素的具體迭代步驟如下：

生成一個(gè)[0, n-1]區(qū)間的隨機(jī)數(shù)k；將第k個(gè)元素和第n-1個(gè)元素進(jìn)行交換；進(jìn)行下一輪迭代，生成一個(gè)[0, n-2]區(qū)間的隨機(jī)數(shù)k，將第k個(gè)元素和第n-2個(gè)元素進(jìn)行交換， 迭代次數(shù)為n-1次：從n-1取到1；最終得到一個(gè)打亂的數(shù)組。

下表是一個(gè)數(shù)組的具體打亂過(guò)程，打亂后的數(shù)組是(9 4 8 1 2 3 5 6 7)

shell實(shí)現(xiàn)

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[*]}

執(zhí)行效果：

$ 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

到此這篇關(guān)于shell實(shí)現(xiàn)Fisher–Yates shuffle洗牌算法介紹的文章就介紹到這了,更多相關(guān)shell Fisher–Yates shuffle洗牌算法內(nèi)容請(qǐng)搜索本站以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持本站！

香港服務(wù)器租用

版權(quán)聲明：本站文章來(lái)源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請(qǐng)保持原文完整并注明來(lái)源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非maisonbaluchon.cn所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來(lái)源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來(lái)，僅供學(xué)習(xí)參考，不代表本站立場(chǎng)，如有內(nèi)容涉嫌侵權(quán)，請(qǐng)聯(lián)系alex-e#qq.com處理。