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了新技能。