一种随机化数组洗牌码的有效方法

把所有的歌排成一列。。。 对于数组中的每个元素,将其与随机位置交换。

你想要的 Fisher-Yates shuffle . 请注意该页中提到的实现错误,因为您当前接受的答案与一个错误不符。

您可以将所有歌曲制作成一个链接列表,这需要大约O(n)(假设插入是固定时间操作)。然后,生成一个随机数,对列表的大小进行模运算以获得一个随机索引,然后移除该索引并将其附加到一个新列表(这两个列表都是常数时间操作)。

每个O(n)的插入+每个O(n)的移除+第二个插入O(n)。这将导致一个线性时间解决方案。

:我完全忘了带名单。因此,您可以将结果设为固定长度数组。弹出链接列表的头部,为其分配随机索引,并填充数组。

Nate(编辑)和Brian的算法是FisherYates shuffle O(n),而按排序的shuffle是O(nlogn),但实际上可能更快(http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates shuffle与其他shuffle算法的比较)。错误的歌曲洗牌可能会产生无关紧要的后果,但如果您正在为在线扑克游戏编写洗牌算法,请确保您知道自己在做什么(http://www.cigital.com/news/index.php?pg=art&artid=20)。

我是一个初学者,让我说一个让我印象深刻的解决方案,如果有什么问题,请让我知道。

假设歌曲存储在单链或双链列表中。每次打开音乐播放器时,选择一个小于(您希望的任何数字)假设k的随机数,并反转列表中的每个k个节点,同样地,以两次或最多三次(您希望的)的速度执行此操作,这将花费O(2n)或O(3n)时间来洗牌。 最后有一个指向列表最后一个节点的指针。 一直持续到音乐播放器关闭。

急于知道答案的正确性。

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 都在桶里,所有的元素 我