洗牌排序的数组

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));