均匀随机地随机打乱数组/n 个数字的元素。可能在预期的 O(n) 时间内

是否可以均匀地打乱一个n大小的数组的元素，即n!中任意一个的概率！出现的组合是相同的，在预期中O(n)时间。为何如此？ 我必须洗牌的元素A到一个新数组B当我尝试这样做时，我想到的第一件事就是选择一个随机数i从 1 到 n，看看是否A[i]已经被选取了，如果是，则重复，否则放入A[i]在第一个可用位置B。 然而，这个优惠券收集问题有预期的时间O(n log n)。 有人可以建议一个O(n)预期时间算法。

Thanks.

你应该看看费希尔-耶茨洗牌。

来自文章：

如果实施得当，费舍尔-耶茨 shuffle 是无偏的，因此每个 排列的可能性是相同的。这 该算法的现代版本是 也相当高效，只需要 时间与数量成正比 项目被洗牌并且没有额外的 储存空间。

所以它满足你的要求。它也很容易实现。