java - 关于Java Collections shuffle(List <？>，Random)方法，我们可以安全地做出哪些假设？

因此，我正在研究collections shuffle方法，并试图提出一个清单，该清单列出了我们在运行该方法时可以保证和不能保证的内容。我列举了一些明显的情况，如下:

改组后，给定的列表将包含与

之前相同的元素

运行方法后，列表可能相同，也可能不同(您可能会获得相同顺序的元素)。

该方法将在线性时间内运行(我认为这是正确的，但不是100％肯定的)。

这个清单是总结还是我错过了一些可能的情况？

最佳答案

official documentation of Collections.shuffle 有很多话要说。该列表将使用Fisher-Yates shuffle algorithm进行改组，ojit_a(假设O(1)中提供了随机访问)在时间O(n)和空间O(1)中运行。如果随机访问不可用，则实现将使用空间O(n)。假设底层随机源完全无偏，则发生任何特定排序的可能性是相等的(即，您在可能的排列上获得了均匀的随机分布)。

因此，回答您的问题:

该列表将包含相同的元素。

它们的顺序可能不同，但是存在1 / n!机会，他们将处于同一顺序。

运行时为O(n)，空间使用量为O(1)或O(n)，具体取决于您的列表是否具有随机访问支持。