java - 完美的shuffle算法实现错误

Question

此代码对于完美的洗牌算法是否正确？我总是试图生成一个从 0 到 n 的数字，并将该数字与数组中的最后一个元素交换，从而减小 n 的范围。但是，当 n=0 时，我得到一个异常。我该如何处理这种情况？

    int [] array ={1,2,3,4,5};
    Random random = new Random();
    int n=array.length;

    while(n--!=0)
    {
        int number = random.nextInt(n);
        int temp = array[n];
        array[n] = array[number];
        array[number] = temp;
    }

编辑：如果我将其更改为 --n >0 那么它可以正常工作，但是在这种情况下我是否正确实施了洗牌算法，因为我从来没有为 n=0 做任何事情？

Answer 1

在您的代码段中

   while(n--!=0) 

 if n is 1, it will become 0 and `random.nextInt(0)` will return an error.

参考这个链接

Answer 2

如果您传递 0 的参数，我认为 nextInt 不起作用。

洗牌的最佳方法是使用Fisher Yates 算法。它速度快，可以就地工作，而且没有偏见：

int [] array = {1,2,3,4,5};
Shuffle(array, new Random());

// Fisher Yates shuffle - see http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
void Shuffle(int[] array, Random RNG)
{
    for (int i = array.length - 1; i >= 1; i -= 1)
    {
        // get integer in range of j >= 0 && j < i + 1
        int j = RNG.nextInt(i + 1);
        //assert(j >= 0 && j <= i);
        if (i != j)
        {
            // only swap if i and j are different
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}