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