Fisher Yates算法解释

Question

我想知道你们中的一些人是否了解Fisher Yates洗牌的工作原理，并能向我解释它。所以我在网上找到了这个Fisher Yates shuffle代码：

public function Main() {
var tempArray:Array = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
ShuffleArray(tempArray);
trace(tempArray);
}
public function ShuffleArray(input:Array)
{
for (var i:int = input.length-1; i >=0; i--)
{
var randomIndex:int = Math.floor(Math.random()*(i+1));
var itemAtIndex:Object = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;
}
}

这个代码运行得很好，但我仍然对感到困惑

1. 我把循环改为"input.length"，但效果不好，有时我仍然得到"0"值。我不知道为什么要用"input.length-1"而不是"input.llength"
2. 在随机化部分，为什么我要将索引从0随机化到值（I+1），为什么我们不将其从0随机化为（I）

如果你们中的一些人理解它，你能向我解释一下吗？非常感谢

Answer 1

1. Js的数组索引从0开始，所以长度为n的数组a的最后一个元素是a[n -1]。

2. Math.random返回一个从0到0.9999…的值，但不包括1（范围在[0, 1)），所以Math.random()* (i + 1)将有一个从0到i + 0.999999......的值，而不是i + 1（范围为[0, i+1)），并使用Math.floor切割点部分以得到Integer，所以我们得到一个范围在[0, i]的数字。

Answer 2

让我用一个否定的例子来解释，让我们说数组大小是10。

1） 如果我们使用index.length，for循环中的第3行将读取

input[randomIndex] = input[i] i.e.
input[randomIndex] = input[10];

但由于javascript有基于0的数组，它的值从索引0到9。索引10将超出范围。因此，我们应该从最后一个元素（仅索引9）中洗牌

2） 对于您的第二个问题，如果我们使用i而不是i+1。假设您处于索引9的循环的第一次迭代中（对于其他迭代也适用）。如上所述，这里i是9。我们希望从0到9的任何一个索引中打乱第9个索引Math.random将从0返回到.999，Math.floor将下限它，所以在我们的情况下，最大值将为.999*（9+1）=9.99。Math.floo将下限它到9。所以范围是[0,9]

如果我们使用i，则最大可能值为8，即范围[0,8]

因此，我们使用i+1，因为我们想要[0,9]的值