shell實(shí)現(xiàn)Fisher–Yates shuffle洗牌算法介紹
更新時間：2021年11月30日 09:03:38 作者：測試開發(fā)小記
大家好，本篇文章主要講的是shell實(shí)現(xiàn)Fisher–Yates shuffle洗牌算法介紹，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下哦
本文介紹使用shell語法實(shí)現(xiàn)Fisher–Yates shuffle 洗牌算法。
Fisher-Yates shuffle 算法簡介
Fisher–Yates shuffle 洗牌算法可以用于對數(shù)組進(jìn)行隨機(jī)排列，它的時間復(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]
假定有一個數(shù)組a=[1, 2, 3, 4, 5, 6, 7, 8, 9]，數(shù)組長度為n，打亂a中元素的具體迭代步驟如下：
生成一個[0, n-1]區(qū)間的隨機(jī)數(shù)k；將第k個元素和第n-1個元素進(jìn)行交換；進(jìn)行下一輪迭代，生成一個[0, n-2]區(qū)間的隨機(jī)數(shù)k，將第k個元素和第n-2個元素進(jìn)行交換， 迭代次數(shù)為n-1次：從n-1取到1；最終得到一個打亂的數(shù)組。
下表是一個數(shù)組的具體打亂過程，打亂后的數(shù)組是(9 4 8 1 2 3 5 6 7)
| 隨機(jī)數(shù) | 原數(shù)組 | 新數(shù)組 |
|---|---|---|
| 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實(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
學(xué)習(xí)linux這么久了，最常用的命令莫屬 ls命令了，今天就總結(jié)下ls命令的用法與經(jīng)驗(yàn)技巧。感興趣的朋友一起看看吧2017-08-08
在shell腳本中激活conda虛擬環(huán)境的方法總結(jié)
在Anaconda中conda可以理解為一個工具，也是一個可執(zhí)行命令，其核心功能是包管理與環(huán)境管理,下面這篇文章主要給大家介紹了關(guān)于如何在shell腳本中激活conda虛擬環(huán)境的相關(guān)資料,需要的朋友可以參考下2022-08-08
這篇文章主要介紹了Shell字符串截取的詳細(xì)方法,如截取指定字?jǐn)?shù)、按指定的字符串截取、按指定要求分割,需要的朋友可以參考下2014-03-03
這篇文章主要介紹了淺談shell 遍歷數(shù)組的幾種方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
這篇文章主要介紹了如何使用curl命令查看服務(wù)器端口開放情況的方法,文中通過代碼示例和圖文講解的非常詳細(xì),具有一定的參考價值,需要的朋友可以參考下2024-05-05
shell腳本監(jiān)控系統(tǒng)負(fù)載、CPU和內(nèi)存使用情況
這篇文章主要介紹了shell腳本監(jiān)控系統(tǒng)負(fù)載、CPU和內(nèi)存使用情況,本文分別給出監(jiān)控服務(wù)器系統(tǒng)負(fù)載情況、監(jiān)控系統(tǒng)cpu使用情況、、監(jiān)控系統(tǒng)內(nèi)存情況、監(jiān)控系統(tǒng)交換分區(qū)swap使用情況的腳本,需要的朋友可以參考下2014-12-12
在Linux系統(tǒng)中,free命令用于顯示系統(tǒng)內(nèi)存的使用情況,它提供了系統(tǒng)內(nèi)存總量、已使用內(nèi)存、空閑內(nèi)存以及其他與內(nèi)存相關(guān)的統(tǒng)計(jì)信息,本文將給大家詳細(xì)的介紹一下Linux free命令的使用方法,需要的朋友可以參考下2023-08-08
Shell 腳本（shell script），是一種為 shell 編寫的腳本程序。下面通過本文給大家介紹使用shell腳本取出服務(wù)器圖片的方法，需要的朋友參考下吧2017-12-12
一天一個shell命令 linux文本操作系列-chmod命令用法
這篇文章主要介紹了一天一個shell命令 linux文本操作系列-chmod命令用法,需要的朋友可以參考下2016-06-06
今天小編就為大家分享一篇關(guān)于使用shell來發(fā)tcp包的方法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-04-04