java - 两种混洗方法中哪一种效果更好？

我试图随机地对列表中的整数集合进行随机排序，并且我想出了两种可以完成此任务的随机排序方法。但是，我不确定哪个效果更好？有没有人有任何意见或建议？

public class TheCollectionInterface {

    public static <E> void swap(List<E> list1, int i, int j) {
        E temp = list1.get(i);
        list1.set(i, list1.get(j));
        list1.set(j, temp);
    }

// Alternative version:
//    public static void shuffling(List<?> list, Random rnd){
//        for(int i = list.size(); i >= 1; i--){
//            swap(list, i - 1, rnd.nextInt(i));
//        }
//    }


    public static <E> void shuffling(List<E> list1, Random rnd) {
        for (int i = list1.size(); i >= 1; i--){
            swap(list1, i - 1, rnd.nextInt(list1.size()));
        }
    }

    public static void main(String[] args) {

        List<Integer> li2 = Arrays.asList(1,2,3,4,5,6,7,8,9);

        Random r1 = new Random();

        TheCollectionInterface.shuffling(li2, r1);

        System.out.println(li2);
    }
}

最佳答案

如果每个可能的结果均等可能，则改组算法通常被认为是好的。您的改组算法的“替代版本”被称为Fisher-Yates算法。给定足够好的随机性源，此算法可证明以相等的概率生成输入的每个可能排列。 JDK Collections.shuffle()方法使用此算法。

从理论上讲，未注释的算法较差，这很容易证明。在Fisher-Yates shuffle上的此Wikipedia文章中对此做了解释。引用该文章，（为清楚起见进行了编辑）


  实施Fisher-Yates随机播放时，常见的错误是从错误的范围中选择随机数。有缺陷的算法看似正确运行，但不会以相同的概率产生每个可能的排列。每次迭代时始终从有效数组索引的整个范围中选择j会产生有偏差的结果，尽管这种情况不那么明显。从这一事实可以看出，这样做会产生n^n个不同的可能交换序列，而n元素数组只有n!个可能的排列。由于当n^n时n!永远不能被n > 2整除（因为后者可以被n−1整除，而n)与n^n不共享素数，因此某些置换必须由更多的i - 1产生）交换顺序比其他顺序。


在这种情况下，j是交换元素list.size()的目标插槽。似乎将当前元素与0到之间的全部元素交换将提供更好的混洗，因为它似乎进行了“更多”混洗。实际上，可能的序列比Fisher-Yates多得多，但是额外的序列会增加偏差，从而降低混洗的质量。

Wikipedia文章详细说明了为什么这样做，并显示了将3元素数组改组的每种结果的概率。

这很容易演示。取一个3元素的数组或列表并对其进行随机播放，例如，进行一百万次，并计算可能的六个排列中的每个排列的出现频率。我是使用Fisher-Yates进行的，结果之间的误差都在±0.3％之内。在全范围混洗中，三个排列的发生频率比其他三个排列高大约20％。

标记为“替代版本”的Fisher-Yates随机算法显然是一种更好的方法。

关于java - 两种混洗方法中哪一种效果更好？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35953002/