java - 洗牌一个排序的数组

Question

如果给定一个已排序的数组，我们可以使用什么算法来创建一个输出数组，该数组与已排序的数组具有相同的元素，但元素应该是随机打乱的。我正在寻找一种复杂度为 O(n) 的算法

Answer 1

Collections.shuffle(List)有O(n)时间复杂度。您可以使用Arrays.asList()来包装数组，以便您可以使用此函数。

它的作用是；

对于从最后一个元素到第二个元素的每个元素，将该元素与列表的其余部分（包括其自身）中的一个随机元素交换，即它不能随机移动一个元素。

for (int i=size; i>1; i--)
    swap(list, i-1, rnd.nextInt(i));

Answer 2

你可以使用这个代码

    // Create a list
    List list = new ArrayList();
    // Add elements to list
    // Shuffle the elements in the list
    Collections.shuffle(list);
    // Create an array
    String[] array = new String[] { "a", "b", "c" };
    // Shuffle the elements in the array
    Collections.shuffle(Arrays.asList(array));

    for (int i = 0; i < array.length; i++) {
        System.out.println("Count is: " + i + " letter is " + array[i]);
    }

这将打印如下内容：

计数是：0个字母是b

计数是：1 个字母是

计数是：2个字母是c

来自http://www.exampledepot.com/egs/java.util/coll_Shuffle.html