就这个数组问题(随即排序一个数组里的值,返回一个新数组)来说,我以前的实现方法是这样的:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
function randArr(arr) {
var ret = [],
obj = {},
i = arr.length,
l = i,
n;
while (--i >= 0) {
n = Math.floor( Math.random() * l );
if (obj[n] === void 0) {
ret[ret.length] = obj[n] = arr[n];
} else {
i++;
}
}
return ret;
}
|
现在给出群里那位同学的算法:
1 2 3 4 5 6 7 8 9 10 11 12 |
function randArr(arr) {
var ret = [],
i = arr.length,
n;
arr = arr.slice(0);
while (--i >= 0) {
n = Math.floor( Math.random() * i);
ret[ret.length] = arr.splice(n, 1)[0];
}
return ret;
}
|
还看到了一个改进版的,是考虑到了对数组的删除操作而导致的些许性能问题,运用了JK大的洗牌算法,即把每一次删除操作改为了位置替换操作(取到的该索引的值和当前自减键 i 对应的值进行互换),这样对整个数组的影响是最小的,还是放代码吧:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
function randArr(arr) {
var ret = [],
i = arr.length,
n;
arr = arr.slice(0);
while (--i >= 0) {
n = Math.floor( Math.random() * i);
ret[ret.length] = arr[n];
arr[n] = arr[i];
}
return ret;
}
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
function makeRandArr(min, max) {
var ret = [],
obj = {},
n;
for (; max >= min; max--) {
n = Math.ceil( Math.random() * (max - min) ) + min;
ret[ret.length] = obj[n] || n;
obj[n] = obj[max] || max;
}
return ret;
}
|