对一个已排序的数组进行洗牌

Question

如果我们有一个已排序的数组，想要创建一个输出数组，其中包含与排序数组相同的元素，但元素应随机洗牌，那么我们可以使用哪种算法？我正在寻找一个时间复杂度为O(n)的算法。

- RagHaven

Answer 1

Collections.shuffle(List) 方法的时间复杂度为 O(n)。你可以使用 Arrays.asList() 将数组转换成列表并使用该方法。

该方法的作用是：

从最后一个元素开始，对于每个元素，将其与列表中剩余元素（包括自身）中的随机元素进行交换，因此有可能不移动某些元素。

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

- Peter Lawrey

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 字母为a

计数为：2 字母为c

来源于 http://www.exampledepot.com/egs/java.util/coll_Shuffle.html。

- MaVRoSCy