js打乱数组的实战应用

在 js 中，能把数组随机打乱的方法有很多，每个方法都有自己的特点。

1. 打乱数组的方法 #

这里主要讲解 3 个打乱数组的方法。

1.1 随机从数组中取出数据 #

这个方法的详细操作步骤是：随机从数组中取出一个数组放入到新数组中，然后将该数据从原数组中删除，然后再随机取出下一个数，直到原数据的长度为 0。

function randomArrByOut(arr) {
  let result = [];
  let arrTemp = arr.concat(); // splice会影响原数组，复制一个新的数组，防止影响原数组
  while (arrTemp.length) {
    let index = Math.floor(Math.random() * arrTemp.length);
    result.push(arrTemp[index]);
    arrTemp.splice(index, 1);
  }
  return result;
}
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
randomArrByOut(arr); // [7, 1, 3, 8, 2, 4, 6, 5, 9]
randomArrByOut(arr); // [8, 4, 3, 7, 9, 2, 1, 5, 6]

这个算法看似是O(n)的算法，但实际上arr.splice内部是一个O(n^2)的算法Array.prototype.splice 的内部实现：外部循环用来删除元素，内部的循环用来填充新添加的元素，或后面的元素向前移动，填充刚才被删除的元素的坑。总的算下来，这个算法的时间复杂度就是O(n^3)了。

1.2 sort 方法打乱 #

还有一种常见的方法就是使用数组自带的 sort 方法来打算数组，sort 方法是直接修改当前的数组：

function randomSortBySort(arr) {
  arr.sort(() => Math.random() - 0.5);
}

当前环节里所有的测试均在 Chrome 中。当我们使用 9 个数据，经过多次的测试发现，打乱的数据排布并不均匀：

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var n = 10000;
var count = {};
while (n--) {
  randomSortBySort(arr);
  var index = arr.indexOf(1);

  count[index] ? count[index]++ : (count[index] = 1);
}
console.log(count);
/*

数据1经过10000次打乱后的分布规律，主要集中在前2个

0: 2047

1: 1403

2: 947

3: 822

4: 777

5: 822

6: 992

7: 1008

8: 1182

*/

我们再把 arr 的数组扩展为 15，再进行测试：

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
var n = 10000;
var count = {};
while (n--) {
  randomSortBySort(arr);
  var index = arr.indexOf(1);

  count[index] ? count[index]++ : (count[index] = 1);
}
console.log(count);
// {0: 668, 1: 647, 2: 652, 3: 665, 4: 692, 5: 652, 6: 679, 7: 657, 8: 665, 9: 683, 10: 685, 11: 690, 12: 662, 13: 663, 14: 640}

可以发现每次打乱后的分布比较均匀，每个数字出现在每个位置的机会都是均等的！

在V8 的源码中 L710 行中可以看到：

function InnerArraySort(array, length, comparefn) {
  // In-place QuickSort algorithm.
  // For short (length <= 22) arrays, insertion sort is used for efficiency.
  // 虽然注释是length<=22，但代码里是<=10

  // 插入排序
  var InsertionSort = function InsertionSort(a, from, to) {};

  var QuickSort = function QuickSort(a, from, to) {
    var third_index = 0;
    while (true) {
      // Insertion sort is faster for short arrays.
      if (to - from <= 10) {
        InsertionSort(a, from, to);
        return;
      }
      // 快排其他的内容
    }
  };
  QuickSort(array, 0, num_non_undefined);
}

sort 的内部使用快速排序，当快排拆分后的分区里的数据个数小于等于 10 个时，则采用插入排序！因此，当数据量比较小的时候，使用sort打乱排序时，会造成不均等的分布！

1.3 洗牌算法 #

最后一个经典的数组打乱算法就是洗牌算法：从最后一个数据开始往前，每次从前面随机一个位置，将两者交换，直到数组交换完毕：

function shuffleSort(arr) {
  var n = arr.length;

  while (n--) {
    var index = Math.floor(Math.random() * n);
    var temp = arr[index];
    arr[index] = arr[n];
    arr[n] = temp;
    // ES6的解耦交换方式： [arr[index], arr[n]] = [arr[n], arr[index]];
  }
}

这种方式是O(n)的时间复杂度，而且还能保证一个比较均匀的分布！高效了很多

2. 从数组中随机取出多个元素 #

这是从数组中随机取出几个元素，上面的一节是将整个数组进行排序，而这里只是需要几个元素而已！

2.1 打乱整个数组取出数据 #

当然，先把整个数组打乱了，然后再取出前 n 个数据也是其中的一种方法，比如我们这里就使用洗牌算法打乱数组，然后取出数据：

function getRandomArr(arr, num) {
  var _arr = arr.concat();
  var n = _arr.length;

  // 先打乱数组
  while (n--) {
    var index = Math.floor(Math.random() * n);
    [_arr[index], _arr[n]] = [_arr[n], _arr[index]];
  }
  return _arr.slice(0, num);
}

不过实际上我们只是需要其中的几个元素而已，如果把整个数组都打乱排序，就显得很浪费。因此这里我们使用洗牌算法的思路，稍微改进一下。

2.2 改进型 #

从最后一个数据开始往前，每次从前面随机一个位置，将两者交换，拿到最后的那个数据，直到达到要获取的个数：

function getRandomArr(arr, num) {
  var _arr = arr.concat();
  var n = _arr.length;
  var result = [];

  // 先打乱数组
  while (n-- && num--) {
    var index = Math.floor(Math.random() * n); // 随机位置
    [_arr[index], _arr[n]] = [_arr[n], _arr[index]]; // 交换数据
    result.push(_arr[n]); // 取出当前最后的值，即刚才交换过来的值
  }
  return result;
}

3. 总结 #

数组中还是有很多的学问的，看看其中的源码，也会发现更多的奥妙！