JavaScript 说说随机排序(洗牌程序)

在小鱼的gayhub看到了这样的一题,其中就需要用到洗牌程序,当然,我在看到排序算法的时候就想到这样可以用于排序,所以很快就有了第一个排序算法:

var shuffleHack = function(arr) {

    var result = arr.slice();

    result.sort(function() {

        return Math.random() - 0.5;

    });


    return result;

};


之所以说这是一种Hack方法,在于他的代码精简,但是实际上,这不是一个很正确的洗牌程序,在于他的随机性很差,具体我们可以用统计学的方法去统计结果,这里忽略不计(其实是我也不太清楚怎么统计比较科学)。

有一种比较科学的洗牌程序,叫做Fisher Yates算法,关于Fisher Yates的介绍,可以看Wiki:Fisher–Yates shuffle

在这里我们根据其伪代码(可以看出这是一个倒序的选择排序算法):

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

给出具体实现即可:

/**
 * 正确的做法
 * Fisher Yates 算法
 *
 * 原理是倒序选择排序,只是随机选择无序的位置进行交换排列
 * @param arr
 * @returns {Array.<T>|string|Blob|ArrayBuffer}
 */
var shuffle = function(arr) {
    var result = arr.slice(),
        length = result.length,
        i,
        temp,
        j;

    for (i = length - 1; i > 1; i--) {
        j = parseInt(Math.random() * i);
        temp = result[i];
        result[i] = result[j];
        result[j] = temp;
    }

    return result;
};

这样的随机性更强,基本可以称之为一个洗牌程序,在如何测试洗牌程序一文中对此亦有介绍。

最后,关于小鱼的题目:

一群人出去玩,写一个程序随机分组可以如何分。最后简化成 10 个人出去玩,如何将人随机分配到 4 个组里,并保证每个组的人比较均匀。

我当时用的洗牌的实现是:

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

(function split(arr, group) {
  // you code here
  var groupSize = group.length,
      totalSize = arr.length;

  // 随机排序
  arr.sort(function() {
    return Math.random() * 2 - 1;
  });

  // 接下来保证每组数量比较平均即可
  group.forEach(function(elem, index) {
    var size = Math.floor(totalSize / groupSize);
    for (var i = 0; i < size; i++) {
      elem.push(arr.pop());
    }

    totalSize -= size;
    groupSize--;
  });

  console.log(group);
})(arr, group);

其实纯属想多了,为什么要那么麻烦呢——

可见小鱼对于此分配时的写法:

'use strict'

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

(function split(arr, group) {

  var size = group.length; // 分多少组
  var length = arr.length; // 人数总长度

  // 每次随机叫一个人,跳进一个组里,并从原数组里踢掉
  while(arr.length) {
    for(let i = 0; i < length; i++){ 
      let index = Math.random() * arr.length | 0;  // 随机
      group[i % size].push(arr[index]);            // 入组
      arr.splice(index, 1);                        // 踢掉
    }
  }

  console.log(group);
})(arr, group);

另外,他还补充了一则对于Fisher Yates算法的补充阅读:https://bost.ocks.org/mike/shuffle/

感觉似乎又Get了新技能。

如果您觉得文章不错,可以通过赞助支持我

标签: 知识, 题目, 算法

添加新评论