Appearance
数组乱序
乱序的意思就是将数组打乱。
Math.random
一个经常会遇见的写法是使用 Math.random()
:
js
var arr = [1, 2, 3, 4, 5]
arr.sort((a, b) => Math.random() - 0.5);
console.log(arr);
Math.random() - 0.5
会随机得到一个正数、负数或者 0。如果是正数则降序排列,如果是负数则升序排列,如果是 0 就不变,然后不断的升序或者降序,最终得到一个乱序的数组。
看起来很完美的方案,但是实际上不尽人意,写个 demo 测试:
js
var times = { 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
for (let i = 0; i < 100000; i ++) {
var arr = [1, 2, 3, 4, 5]
arr.sort((a, b) => Math.random() - 0.5);
times[arr[4]]++;
}
console.log(times); // {1: 24904, 2: 7057, 3: 21116, 4: 18826, 5: 28097}
测试原理是:将 [1, 2, 3, 4, 5]
乱序 10 万次,然后统计最后一位元素是 1、2、3、4、5 的次数分别是多少。
一次随机得到的结果是:
[30636, 30906, 20456, 11743, 6259]
可以看到,这几数字出现的次数之间的差别是很大的,最后一个元素是 2 的次数远远小于 1 的次数。所以这个方案有问题。
可是明明感觉这个方法还不错呐?而实际上上,这是受到 sort()
底层实现的排序算法影响的。v8 在处理 sort
方法时,当目标数组长度小于 10 时,使用插入排序;反之,使用快速排序和插入排序的混合排序(现在已经使用 Timsort)。通过这种排序方法的乱序并不彻底。
那么如何实现真正的乱序呢?而这就要提到经典的 Fisher–Yates 算法。
Fisher–Yates
Fisher–Yates shuffle 洗牌算法是一种生成有限序列的随机排列的算法,之所以有这个命名,当然是由Fisher和Yates这两个人的发明的。
原始算法步骤
开始只是用来人工混排一组数字序列,原始算法的步骤非常容易理解:
- 写下从 1 到 N 的数字
- 取一个从 1 到剩下的数字(包括这个数字)的随机数 k
- 从低位开始,得到第 k 个数字(这个数字还没有被取出),把它写在独立的一个列表的最后一位
- 重复第 2 步,直到所有的数字都被取出
- 第 3 步写出的这个序列,现在就是原始数字的随机排列
经典的算法
第三步真的去从低位开始数数,实际上可以通过数组的随机访问性直接读取:
- 给定一组待混排的有限序列 P
- 新初始化一个空的序列 Q
- 从 P 中随机选取一个元素
- 将该元素放到序列 Q 的最后面,并从序列 P 中移除该元素
- 重复 3-4 的步骤,直到序列 P 中元素全部选取到了序列 Q 中,得到的序列 Q 即为一组 P 的混排序列
js
function shuffle(arr) {
if(!Array.isArray(arr)) return [];
const res = []
for (let i = arr.length; i > 0; i --) {
// 随机生成元素的索引地址
const idx = Math.floor(Math.random() * i) // 0 ~ arr.length - 1
res.push(arr[idx])
arr.splice(idx, 1)
}
return res
}
流行的算法
经典算法中需要借助 res
所以空间复杂度为 O(n)
。现代算法在操作过程中不需要借助一个新的序列,而可以直接在当前序列中完成.算法步骤大致相同:
- 给定一组待混排的有限序列 P
- 从 P 中随机选取一个未混排的元素
- 将该元素与序列 P 的最后一个未混排的元素交换
- 重复 2-3 的步骤,直到序列 P 中元素全部混排过
js
function shuffle(arr) {
for (let i = arr.length; i > 0; i--) {
// 从 arr 中选取一个未混排的元素的索引
let idx = Math.floor(Math.random() * i); // 0 ~ arr.length - 1
// 将它和最后一个未混排的元素,即当前元素交换
let temp = arr[i - 1];
arr[i - 1] = arr[idx];
arr[idx] = temp;
}
return arr;
}
原理很简单,就是遍历数组元素,然后将当前元素与以后随机位置的元素进行交换,从代码中也可以看出,这样乱序的就会更加彻底。
js
var times = 100000;
var res = {};
for (var i = 0; i < times; i++) {
var arr = shuffle([1, 2, 3]);
var key = JSON.stringify(arr);
res[key] ? res[key]++ : res[key] = 1;
}
// 为了方便展示,转换成百分比
for (var key in res) {
res[key] = res[key] / times * 100 + '%'
}
console.log(res)
真正的实现了乱序的效果!
lodash 中的实现
在 lodash 中 shuffle
的实现如下,Lodash 库中 Shuffle
就是现代算法的实现,不同的是其交换的元素是从数组首位开始的,并且返回一个新数组:
js
function shuffle(array) {
const length = array == null ? 0 : array.length;
if (!length) return [];
let index = -1;
const lastIndex = length - 1;
// const result = copyArray(array);
const result = array.concat();
while (++index < length) {
// 通过 index +,保证向后推移,避免重复
const rand = index + Math.floor(Math.random() * (lastIndex - index + 1));
const value = result[rand];
result[rand] = result[index];
result[index] = value;
}
return result;
}