将一个排序后的数组重新排序

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

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