随机化数组的有效方法 - Shuffle 代码

Question

我在面试中被问到这个问题，我给出了各种解决方案，但面试官并不相信。我有兴趣找到解决方案。请提出您的看法：

问：编写一个高效的数据结构来实现ipod中的shuffle。它必须播放所有歌曲，每次以不同的随机顺序播放，同一首歌曲不应重复。 （主要是 O(n)）

一个解决方案，我在面试后想到：我可以进行随机快速排序而不需要递归。我们随机选择 1 个主元 O(1)，然后进行快速排序 O(n)。现在歌曲将按某种顺序排序，我会一直播放到最后。一旦到达终点，我将再次选择一个随机枢轴，并一次又一次地重复这个过程。

问候， 塞图

Answer 1

您需要 Fisher-Yates 洗牌。请注意该页面上提到的实施错误，因为您当前接受的答案不符合其中之一。

Answer 2

将所有歌曲放入一个数组中...
对于数组中的每个元素，将其与随机位置交换。

Answer 3

好吧，我想到的第一个线性时间解决方案是：

您可以创建所有歌曲的链接列表，这大约需要 O(n) （假设插入是常数时间操作）。然后，生成一个随机数，对列表的大小取模以获得随机索引，然后删除该索引并将其附加到新列表（两者都是恒定时间操作）。

每个 O(n) 的插入 + 每个 O(n) 的删除 + 第二次插入 O(n)。这总体上会导致线性时间解决方案。

编辑：我完全忘记了要遍历列表。因此，您可以将结果设为固定长度数组。弹出链表的头部，为其分配随机索引，然后填充数组。

Answer 4

Nate（编辑）和 Brian 的算法是 Fisher–Yates 洗牌 O(n)，而通过排序洗牌是 O(nlogn)，但实际上在实践中可能更快 (http://en.wikipedia.org/wiki/Fisher% E2%80%93Yates_shuffle#Comparison_with_other_shuffling_algorithms)。歌曲洗牌错误可能会产生微不足道的后果，但如果您正在为在线扑克游戏编写洗牌算法，请确保您知道自己在做什么 (http://www.cigital.com/news/index.php?pg=艺术&艺术= 20）。

Answer 5

您想要的是 Fisher-Yates Shuffle。下面是 java 中的一个实现：

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

它的工作原理是将整个数组视为一顶帽子，并开始提取随机元素并将它们排列在数组的前面。 i 之后的所有元素都“在桶中”，i 之前的所有元素都被打乱。

Answer 6

我是初学者，说一个我想到的解决方案，如果有问题请告诉我。

假设歌曲存储在单链表或双链表中。每次打开音乐播放器时，选择一个小于（您想要的任何数字）假设 k 的随机数，并反转列表中的每个 k 节点，类似地执行两次或最多三次（如您所愿），这将需要 O( 2n) 或 O(3n) 时间进行洗牌。
最后有一个指向链表最后一个节点的指针。
每次听一首歌曲（访问一个节点）时，都会删除该节点并将其插入到最后一个节点旁边，这可以在 O(1) 时间内完成。
这将持续到音乐播放器关闭为止。

谢谢，
渴望知道答案的正确性。