2016-05-15

阅读

关系型数据库怎样工作的 【recommended】

数组的完全随机排列

聚沙

经典洗牌算法 Fisher–Yates Shuffle

这样：

1
2
3
4
5
6
7
8
9
10

function shuffle(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    var idx = Math.floor(Math.random() * (len - i));
    var temp = arr[idx];
    arr[idx] = arr[len - i - 1];
    arr[len - i -1] = temp;
  }
  return arr;
}

或者这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function shuffle(arr) {
  var len = arr.length;
  var i = len;
  var j;
  var temp;

  while (--i) {
    j = Math.floor(Math.random() * (i+1));
    temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
  }

  return arr;
}

测试方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var arr = [0,1,2,3,4,5,6,7,8,9];
var res = [0,0,0,0,0,0,0,0,0,0];

var t = 100000;
for(var i = 0; i < t; i++){
  var sorted = shuffle(arr.slice(0));
  sorted.forEach(function(o,i){
      res[i] += o;
  });
}

res = res.map(function(o){
    return o / t;
});

console.log(res);

至于广为流传的这种写法：

1
2
3
4
5

function shuffle(arr){
  return arr.sort(function() {
    return Math.random() - 0.5;
  });
}

它确实可以达到乱序的效果，但并非完全随机

https://bost.ocks.org/mike/shuffle/

http://coolshell.cn/articles/8593.html

Comments