深入分析:如何随机打乱一个数组

分析1: 怎么算随机打乱一个数组

只要能保证处理后的每个数所处的位置都是由随机数决定的, 那么就可以说数组被打乱了.

方案一(简单方便)

1. 对于一个长度为n的数组arr, 生成一个[0,n-1] 的整数随机数r, 将arr[r]与数组中最后一个数arr[n-1]进行交换.
2. 执行后忽略掉最后一个数, 将前面n-1个数看作是一个新的数组, 重复上个步骤, 直到最后数组长度n变成1.

步骤1从数组中随机选择一个数放到最后一个位置, 也就是说arr[r]被打乱了放到了最后, 之后前面的n-1个数可以看作新的数组, 直到最后数组长度变成1就可以了.
如此整个数组中的所有数的位置均是由随机数决定的, 我们将整个数组随机打乱了.

生成的随机数范围应该是当前数组大小, 数组大小是不断减小的, 因此生成的随机数也是不断减小的, 例如一个长度为5的数组, 只需要生成范围[0,4],[0,3],[0,2],[0,1]的4个随机数即可以打乱一组数据.

如此, 大小为n的数组, 需要n-1个随机数, 最多n-1次交换即可随机打乱一组数据, 且没有开辟额外空间.

代码示例(容易理解的代码)

java.util.Random random = new java.util.Random();

void disorder(int[] arr) {
   // 存放生成的随机数
   int rdm;
   // 用于数组交换
   int tmp;
   for (int n = arr.length; n > 1; n --) {
      // 生成一个`[0,n-1]` 的随机数
      rdm = random.nextInt(n);
      // 将这个随机数和最后一个数交换
      if (rdm != n - 1) {
         tmp = arr[rdm];
         arr[rdm] = arr[n - 1];
         arr[n - 1] = tmp;
      }
   }
}

优化后的代码(优化了n--的顺序)

java.util.Random random = new java.util.Random();

void disorder(int[] arr) {
   int rdm, tmp;
   for (int n = arr.length; n > 1; ) {
      // 生成一个`[0,n-1]` 的随机数
      rdm = random.nextInt(n);
      n --;
      // 将这个随机数和最后一个数交换
      if (rdm != n) {
         tmp = arr[rdm];
         arr[rdm] = arr[n];
         arr[n] = tmp;
      }
   }
}

时间复杂度为 O(n), 空间复杂度为 O(1)

分析2: 打乱一组数据需要几个随机数呢?

1. n个数有n!种排序方式: 两个数有两种排序方式, 3个数有6种排序方式, 4个数有24种排序方式,
2. 一个普通的随机数算法就可以表示一个非常大范围的值, 例如java中的java.lang.Math.Random, 可以生成一个取值范围是[0.0,1.0)的double值, 将其乘以1,000,000,000后取整就是一个[0,1,000,000,000)范围内的随机数.

只要能保证处理后的每个数所处的位置都是由随机数决定的, 那么就可以说数组被打乱了,

如果一个随机数的取值范围非常大, 刚好和数组的排列情况相等, 那么一个随机数就可以决定一个数组的排列顺序.

也就是说, 打乱一组数据只需要一个取值范围刚好等于数组的排列情况的随机数就可以了

例如一个长度为10的数组排列方式共有10! = 3,628,800种排列方式, 那么只需要一个[0,3,628,800) 范围内的整数随机数, 即可决定一个数组的排列顺序, 也就是说能够打乱这组数据.

分析3: 应该需要多少个随机数

根据分析2, 假如是长度为100的数组, 那么随机数范围应该是[0, 100!), 这是一个非常大的数, 普通的个随机算法都不能够算出这么大的数, 那怎么办?

事实上, 打乱一组数据和几个随机数没有多少关系, 只要能够表示出100!种情况, 最终从中随机选出一种, 即能随机打乱这组数据.

一个随机数表示不了100!这么大的数, 那么多个使用多个随机数联合就能够表示出100!范围内的数, 现在思考下方案一中的随机数, 按照方案一中的情况, 生成的随机数生成范围应该是依次[0, 100), [0, 99), [0, 98)…[0, 1), 共99次随机数, 这99次共同可以表示的范围刚好是 100!.

生成一个随机数比较慢, 我们可以将多个随机数组合成一次来生成, 例如我们可以将范围[0, 100), [0, 99), [0, 98)的3个随机数合并成一个范围[0, 970200)的一个随机数(970,200 = 100*99*98), 这样就能够减少随机数生成的次数, 这样就能快一点.

• 倘若是100个数, 生成一个[0, 9900)范围内的整数随机数, 就可以表示9900种情况, 那么一个随机数就可以给两个数使用.
• 如果是5个数, 那么只要生成一个`[0, 120)内的整数随机数, 就可以决定5个数的顺序, 相当于彻底打乱5个数.

方案二(复杂效率微微提高)

综上分析, 可以先指定一个最大随机数生成范围, 例如将最大随机数范围设置为1_000_000, 依然以打乱一个长度为100的数组为例.

1. 以100开始, 取连乘小于1_000_000的几个数, 例如经过简单计算可知: 100*99*98 <1_000_000< 100*99*98*97,

2. 那么就取[0, 970200)作为第一个随机数生成范围(970,200 = 100*99*98), 例如这个随机数值是657894, 通过分解可以表示出三个随机数65, 79, 73(657894 = 65*100 + 79*99 + 73)

3. 之后将数组中第65个数和第100个数交换, 第79个数和第99个数交换, 第73个数和第98个数交换, 一下子解决了三个数.

4. 之后从97开始, 重新重复执行步骤1, 2, 3, 直到最后每个数所处的位置都是由随机数决定那么就可以说数组被打乱了.

方案三(适合极端要求效率情况)

前两种方案已经很快了, 但是如果你需要更高要求的话, 可以考虑自定义一个适合的随机数算法.

根据分析2, 如果一个随机数的取值范围非常大, 刚好和数组的排列情况相等, 那么一个随机数就可以决定一个数组的排列顺序, 事实上通用的随机数算法直接满足需求, 只能通过多个随机数来合并决定一个数组的排列情况.

那么自定义一个随机数算法将是一个非常不错的选择, 自定义随机数职业需要考虑生成的随机数能够刚好决定数组排列顺序即可, 可以根据需求来提升速率. 可以生成一个非常大的随机数, 也可以为每一次排列单独生成随机数.

总结

方案一是最简便的算法, 也是最容易理解和实用的方案, 对于个人编写和使用来说很不错.

方案二相对来讲变得复杂, 难以理解, 但相对于方案一来说更加快, 而且可以较少的执行获取随机数的方法.

• 例如获取真随机数可能比较麻烦一些, 可能是希望能够尽量少点调用获取真随机数的方法, 那么使用该方案就很不错.
• 该方案到底是比较快一点, 做成工具类是不错的, 例如在java里面, 做成jar, 放到中央仓库, 供大家使用.

方案三的要求就更高了, 不适合个人, 也不适合通用工具jar, 适合有某些要求的极端情况.

最后

以上就是鲤鱼羽毛为你收集整理的深入分析:如何随机打乱一个数组的全部内容，希望文章能够帮你解决深入分析:如何随机打乱一个数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。