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了新技能。
植入部分
如果您觉得文章不错,可以通过赞助支持我。
如果您不希望打赏,也可以通过关闭广告屏蔽插件的形式帮助网站运作。