知食记
搜索文档…
数组乱序

需求

给定一个数组,返回一个完全乱序过的数组

实现

Fisher–Yates Shuffle复杂度 O(n)。
其实它的思想非常的简单,遍历数组元素,将其与之前的任意元素交换。因为遍历有从前向后和从后往前两种方式,所以该算法大致也有两个版本的实现。

从后往前版本

1
function shuffle(array) {
2
var _array = array.concat();
3
4
for (var i = _array.length; i--; ) {
5
var j = Math.floor(Math.random() * (i + 1));
6
var temp = _array[i];
7
_array[i] = _array[j];
8
_array[j] = temp;
9
}
10
11
return _array;
12
}
Copied!

流传但不准确的版本

另一个为人津津乐道的方法是 "巧妙应用" JavaScript 中的 Math.random() 函数。
1
function shuffle(a) {
2
return a.concat().sort(function(a, b) {
3
return Math.random() - 0.5;
4
});
5
}
Copied!
同样是 [0, 1, 2 ... 10] 作为初始值,同样跑了 1w 组 case,结果请猛戳 http://hanzichi.github.io/test-case/shuffle/Math.random/
看平均值的图表,很明显可以看到曲线浮动,而且多次刷新,折现的大致走向一致,平均值更是在 5 上下 0.4 的区间浮动。如果我们将 [0, 1, 2 .. 9] 作为初始数组,可以看到更加明显不符预期的结果(有兴趣的可以自己去试下)。究其原因,要追究 JavaScript 引擎对于Array.prototype.sort的实现原理,这里就不展开了(其实是我也不知道)。因为 ECMAScript 并没有规定 JavaScript 引擎对于 Array.prototype.sort 应该实现的方式,所以我猜想不同浏览器经过这样的乱序后,结果也不一样。
什么时候可以用这种方法乱序呢?"非正式" 场合,一些手写 DEMO 需要乱序的场合,这不失为一种 clever solution。
但是这种解法不但不正确,而且 sort 的复杂度,平均下来应该是 O(nlogn),跟我们接下来要说的正解还是有不少差距的。

参考