javascript数组完全随机排列(洗牌算法、shuffle算法)

关于错误算法的前言:(可以当做废话跳过,不谢)

  • 采用javascript的sort方法实现的随机洗牌算法是错误的。
  • 基于冒泡排序、插入排序等常规排序算法实现的随机洗牌算法是错误的。

采用排序实现的随机洗牌算法具体错误原理本文就不描述了,尔等可以用结尾的测试代码自行实验。大体来讲最终排序的结果是受排序前的状态影响,可以理解为排序前是正叙的话,结果也整体偏向于正序,排序前是倒序的话,结果也偏向于倒序。

进入主题:

随机算法代码:

时间复杂度为O(n).

function shuffle(array) {
  var m = array.length, t, i;

  // 处理余下待随机排序的元素…
  while (m) {

    // 取到一个带排序的元素…
    i = Math.floor(Math.random() * m--);

    // 把它和当前剩余元素序列的最后一个元素交换位置.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

在上面的算法里,我们每一次循环从前 len – i 个元素里随机一个位置,将这个元素和第 len – i 个元素进行交换,迭代直到 i = len – 1 为止。

洗牌算法、shuffle算法 洗牌算法、shuffle算法 洗牌算法、shuffle算法 洗牌算法、shuffle算法 洗牌算法、shuffle算法

为了证明这个算法的正确性,我们设计一个测试的方法。假定这个排序算法是正确的,那么,将这个算法用于随机数组 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],如果算法正确,那么每个数字在每一位出现的概率均等。因此,将数组重复洗牌足够多次,然后将每次的结果在每一位相加,最后对每一位的结果取平均值,这个平均值应该约等于 (0 + 9) / 2 = 4.5,测试次数越多次,每一位上的平均值就都应该越接近于 4.5。所以我们简单实现测试代码如下:

function shuffle(array) {
  var m = array.length, t, i;

  // 处理余下待随机排序的元素…
  while (m) {

    // 取到一个带排序的元素…
    i = Math.floor(Math.random() * m--);

    // 把它和当前剩余元素序列的最后一个元素交换位置.
    t = array[m];
    array[m] = array[i];
    array[i] = t;
  }

  return array;
}

var arr = [0,1,2,3,4,5,6,7,8,9]; 
var res = [0,0,0,0,0,0,0,0,0,0]; 

var t = 10000; 
for(var i = 0; i < t; i++) { 
  var sorted = shuffle(arr.slice(0));
  sorted.forEach(function(o,i){ res[i] += o; }); 
}

res = res.map(function(o) { 
  return o / t; 
});

console.log(res);

测试结果:

40E72288-BCAE-4FA7-959E-7F5873EF6C5C

随机性的数学归纳法证明

对 n 个数进行随机:

  1. 首先我们考虑 n = 2 的情况,根据算法,显然有 1/2 的概率两个数交换,有 1/2 的概率两个数不交换,因此对 n = 2 的情况,元素出现在每个位置的概率都是 1/2,满足随机性要求。
  2. 假设有 i 个数, i >= 2 时,算法随机性符合要求,即每个数出现在 i 个位置上每个位置的概率都是 1/i。
  3. 对于 i + 1 个数,按照我们的算法,在第一次循环时,每个数都有 1/(i+1) 的概率被交换到最末尾,所以每个元素出现在最末一位的概率都是 1/(i+1) 。而每个数也都有 i/(i+1) 的概率不被交换到最末尾,如果不被交换,从第二次循环开始还原成 i 个数随机,根据 2. 的假设,它们出现在 i 个位置的概率是 1/i。因此每个数出现在前 i 位任意一位的概率是 (i/(i+1)) * (1/i) = 1/(i+1),也是 1/(i+1)。
  4. 综合 1. 2. 3. 得出,对于任意 n >= 2,经过这个算法,每个元素出现在 n 个位置任意一个位置的概率都是 1/n。

参考文章:

  • https://bost.ocks.org/mike/shuffle/
  • https://www.h5jun.com/post/array-shuffle.html