P粉8100506692023-08-22 00:30:17
這是一個JavaScript實作的Durstenfeld shuffle,它是Fisher-Yates演算法的最佳化版本:
/* 使用Durstenfeld shuffle算法原地随机化数组 */ function shuffleArray(array) { for (var i = array.length - 1; i > 0; i--) { var j = Math.floor(Math.random() * (i + 1)); var temp = array[i]; array[i] = array[j]; array[j] = temp; } }
它為每個原始數組元素選擇一個隨機元素,並從下一次抽取中排除它,就像從一副牌中隨機抽取一樣。
這個巧妙的排除操作將被選中的元素與當前元素交換,然後從剩餘的元素中選擇下一個隨機元素,為了最佳效率而向後循環,確保隨機選擇被簡化(它總是可以從0開始),從而跳過最後一個元素。
演算法的運行時間為O(n)
。請注意,洗牌是原地進行的,所以如果你不想修改原始數組,請先使用.slice(0)
建立一個副本。
新的ES6允許我們同時賦值兩個變數。當我們想要交換兩個變數的值時,這特別方便,因為我們可以在一行程式碼中完成。這是使用此功能的相同函數的更短形式。
function shuffleArray(array) { for (let i = array.length - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)); [array[i], array[j]] = [array[j], array[i]]; } }
P粉5534287802023-08-22 00:07:03
事實上,無偏的洗牌演算法是Fisher-Yates(又稱Knuth)洗牌演算法。
function shuffle(array) { let currentIndex = array.length, randomIndex; // While there remain elements to shuffle. while (currentIndex != 0) { // Pick a remaining element. randomIndex = Math.floor(Math.random() * currentIndex); currentIndex--; // And swap it with the current element. [array[currentIndex], array[randomIndex]] = [ array[randomIndex], array[currentIndex]]; } return array; } // Used like so var arr = [2, 11, 37, 42]; shuffle(arr); console.log(arr);