数组乱序的正确姿势

Jul 25, 2016

在 underscore 中有一个函数，其作用是将数组乱序排序，实现如下：

// Shuffle a collection, using the modern version of the
// [Fisher-Yates shuffle](http://en.wikipedia.org/wiki/Fisher–Yates_shuffle).
// `shuffle` 函数。
_.shuffle = function(obj) {
  var set = isArrayLike(obj) ? obj : _.values(obj);
  var length = set.length;
  var shuffled = Array(length);
  for (var index = 0, rand; index < length; index++) {
    rand = _.random(0, index);
    if (rand !== index) shuffled[index] = shuffled[rand];
    shuffled[rand] = set[index];
  }
  return shuffled;
};

其中使用的数组乱序的算法是 Fisher–Yates shuffle。这是一个 O(n) 复杂度的随机排列数组元素的经典算法。

每次循环从前面的 index 个元素中随机选择一个元素 shuffle[rand]。将这个元素与第 index 个元素进行交换，直到 index == length 为止。这样对元素进行随机交换，对于每个结果所获得概率是均匀的。_.shuffle 方法是返回一个新的乱序数组，所以需要一个新的数组来存储。

对原有数组进行乱序：

function shuffle(arr) {
  var length = arr.length;
  for (var index = 0, rand; index < length; index ++) {
    rand = Math.floor(Math.random() * (length - 1));

    var temp = arr[rand];
    arr[rand] = arr[index];
    arr[index] = temp;
  }
  return arr;
}

More