乱序

2018-09-04

Math.random

常见的写法是使用 Math.random()：

var values = [1, 2, 3, 4, 5];
values.sort(function(){
  return Math.random() - 0.5;
});
console.log(values)

但 sort 返回的是伪随机数，不同浏览器实现 sort 函数的方式还不一样，以 v8 为例，v8 在处理 sort 方法时，当目标数组长度小于 10 时，使用插入排序；反之，使用快速排序和插入排序的混合排序

插入排序

插入排序的源码：

function comparefn(x, y) {
  // 忽略其他转换等代码，判断大小并返回-1或0或1
  if (x == y) return 0;
  else return x < y ? -1 : 1;
}
function InsertionSort(a, from, to) {
  for (var i = from + 1; i < to; i++) {
    var element = a[i];
    for (var j = i - 1; j >= from; j--) {
      var tmp = a[j];
      // 每个元素都与当前元素进行比较，确保比当前元素大的元素都在右面
      var order = comparefn(tmp, element);
      if (order > 0) { 
        a[j + 1] = tmp;
      } else {
        break;
      }
    }
    a[j + 1] = element;
  }
};

分析原因

示例代码：

var values = [1, 2, 3];
values.sort(function() {
  return Math.random() - 0.5;
});

数组长度小于10，此时sort函数底层是使用插入排序实现，InsertionSort函数的from的值为0，to的值为3，comparefn为传入的匿名函数。Math.random() - 0.5的结果有50%的概率小于0（位置不变），有50%的概率大于0（交换位置），即每次比较都有一半的可能性保持位置不变。

数组	i = 1	i = 2	总计
[1, 2, 3]	50% [1, 2, 3]	50% [1, 2, 3]	25% [1, 2, 3]
		25% [1, 3, 2]	12.5% [1, 3, 2]
		25% [3, 1, 2]	12.5% [3, 1, 2]
	50% [2, 1, 3]	50% [2, 1, 3]	25% [2, 1, 3]
		25% [2, 3, 1]	12.5% [2, 3, 1]
		25% [3, 2, 1]	12.5% [3, 2, 1]

Fisher–Yates

这个算法是由 Ronald Fisher 和 Frank Yates 首次提出

function shuffle(a) {
  var j, x, i;
  for (i = a.length; i; i--) {
    j = Math.floor(Math.random() * i);
    x = a[i - 1];
    a[i - 1] = a[j];
    a[j] = x;
  }
  return a;
}

原理就是遍历数组元素，然后将当前元素与随机位置的元素进行交换，真正的实现了乱序的效果
利用 ES6，代码还可以简化：

function shuffle(a) {
  for (let i = a.length; i; i--) {
    let j = Math.floor(Math.random() * i);
    [a[i - 1], a[j]] = [a[j], a[i - 1]];
  }
  return a;
}