是否可以均匀地对n个大小的数组的元素进行混洗，即n个元素中任意一个的概率！在预期的O(n)时间内发生的组合是相同的。为何如此？我必须将元素洗牌A到一个新数组中B 当我尝试执行此操作时，我想到的第一件事就是选择一个i从1到n 的随机数，看看是否A[i]已被选择，如果是，则重复执行，否则放在A[i]的第一个可用位置B。但是，此优惠券收集器问题有预期的时间O(n log n)。有人可以建议一个O(n)预期时间算法。
O(n)
A
B
i
A[i]
O(n log n)
谢谢。
您应该看一下Fisher- Yates混洗。
从文章：
正确实施了Fisher- Yates混洗是没有偏见的，因此每个排列的可能性都是相同的。该算法的现代版本也相当高效，只需要与洗牌项目的数量成正比的时间，而无需额外的存储空间。
因此它符合您的要求。这也很容易实现。
