日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

shell實現Fisher–Yates?shuffle洗牌算法介紹_linux shell

更新時間： 2021-10-12 編程語言

本文介紹使用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)

隨機數 原數組 新數組
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/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

原文鏈接：https://blog.51cto.com/u_15441270/4714428

欄目分類
最近更新