改组排序的数组 [英] Shuffling a sorted array

问题描述

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

If we are given an array that is sorted, what algorithm can we use to create an output array that has the same elements as the sorted array, but the elements should be randomly shuffled. I am looking for an algorithm that has a complexity of O(n)

推荐答案

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

Collections.shuffle(List) has an O(n) time complexity. You can use Arrays.asList() to wrap the array so you can use this function.

它的作用是;

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

For each element from the last to the second element, swap the element with a random element from the rest of the list which includes itself i.e. it could randomly not move an element.

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

这篇关于改组排序的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！