乱序算法(shuffling algorithm)

文章目录

问题

shuffling 就是希望打乱一个基本有序的序列，越乱越好

比如现在有一个已经排好序的 objects，以下面扑克牌为例：

在这里插入图片描述
我们希望能够随机的打乱它的顺序，比如得到下面的序列：

在这里插入图片描述


基于排序的shuffling

我们可以为每一个数组中的元素随机的产生一个随机数，然后对随机数进行排序，排序的同时移动相应的数组中的元素，排序完成后，即可以实现数组中的元素乱序：

在这里插入图片描述
在这里插入图片描述


基于交换的shuffling(Knuth shuffle)

Knuth shuffle 的思想是这样的：

  • 依次遍历数组当中的每个元素，在遍历第 i 个元素的时候，在 [0, i] 之间产生一个随机数 r (也可以在 [i, n-1] 之间产生随机数，但一个常见的错误是在 [0, n-1] 之间产生)
  • 交换 a[i] 和 a[r]
版权声明：本文为ZLP_CSDN原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。