CodeSky 代码之空

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

1var shuffleHack = function(arr) {
2
    var result = arr.slice();
3
    result.sort(function() {

4        return Math.random() - 0.5;
5
    });
6

    return result;

7};

8

之所以说这是一种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]

给出具体实现即可：

1/**
2 * 正确的做法
3 * Fisher Yates 算法
4 *
5 * 原理是倒序选择排序，只是随机选择无序的位置进行交换排列
6 * @param arr
7 * @returns {Array.<T>|string|Blob|ArrayBuffer}
8 */
9var shuffle = function(arr) {
10    var result = arr.slice(),
11        length = result.length,
12        i,
13        temp,
14        j;
15
16    for (i = length - 1; i > 1; i--) {
17        j = parseInt(Math.random() * i);
18        temp = result[i];
19        result[i] = result[j];
20        result[j] = temp;
21    }
22
23    return result;
24};
25

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

最后，关于小鱼的题目：

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

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

1var arr = [1,2,3,4,5,6,7,8,9,0];
2var group = [[],[],[],[]];
3
4(function split(arr, group) {
5  // you code here
6  var groupSize = group.length,
7      totalSize = arr.length;
8
9  // 随机排序
10  arr.sort(function() {
11    return Math.random() * 2 - 1;
12  });
13
14  // 接下来保证每组数量比较平均即可
15  group.forEach(function(elem, index) {
16    var size = Math.floor(totalSize / groupSize);
17    for (var i = 0; i < size; i++) {
18      elem.push(arr.pop());
19    }
20
21    totalSize -= size;
22    groupSize--;
23  });
24
25  console.log(group);
26})(arr, group);
27

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

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

1'use strict'
2
3var arr = [1,2,3,4,5,6,7,8,9,0];
4var group = [[],[],[],[]];
5
6(function split(arr, group) {
7
8  var size = group.length; // 分多少组
9  var length = arr.length; // 人数总长度
10
11  // 每次随机叫一个人，跳进一个组里，并从原数组里踢掉
12  while(arr.length) {
13    for(let i = 0; i < length; i++){ 
14      let index = Math.random() * arr.length | 0;  // 随机
15      group[i % size].push(arr[index]);            // 入组
16      arr.splice(index, 1);                        // 踢掉
17    }
18  }
19
20  console.log(group);
21})(arr, group);
22

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

感觉似乎又Get了新技能。