給定一個數組，編寫一個程序來生成數組元素的隨機排列，這個問題也被稱為“洗牌”或“隨機化給定的數組”。洗牌算法中數組元素的每種排列的可能性都應該是相同的。
洗牌算法是如何運行的
給定的數組是arr[]，一個簡單的解決方法是創建一個輔助數組temp[]，它最初是arr[]的副本。從temp[]中隨機選擇一個元素，將隨機選擇的元素復制到arr[0]，然后從temp[]中刪除選擇的元素。重復相同的過程n次并繼續將元素復制到arr[1]、arr[2]、…。該解決方案的時間復雜度為O(n^2)。
Fisher-Yates shuffle算法的工作時間復雜度為O(n)。這里的假設是，我們得到一個函數rand()，它在O(1)時間內生成一個隨機數。這個想法是從最后一個元素開始，并將其與整個數組（包括最后一個）中隨機選擇的元素交換。現在考慮從0到n-2的數組（大小減1），重復這個過程直到我們找到第一個元素。
下面是詳細的算法：
對包含n個元素（索引0..n-1）的數組a進行洗牌
for i from n-1 downto 1 do j=random integer with 0<=j<=i exchange a[j]and a<i>
登錄后復制
Python實現洗牌算法
from random import randint def randomize(arr,n): for i in range(n-1,0,-1): j=randint(0,i+1) arr<i>,arr[j]=arr[j],arr<i> return arr arr=[1,2,3,4,5,6,7,8] n=len(arr) print(randomize(arr,n)) 輸出結果：7 8 4 6 3 1 2 5
登錄后復制
