Expose shuffle function of underscore.js

underscore.js 里有一个数组重新随机排序的函数 _.shuffle

1
2
3
4
5
6
7
8
9
10
11
12
13
// Shuffle an array.
_.shuffle = function (obj) {
var rand;
var index = 0;
var shuffled = [];
each(obj, function (value) {
// _.random函数返回[0, index]之间的随机数
rand = _.random(index++);
shuffled[index - 1] = shuffled[rand];
shuffled[rand] = value;
});
return shuffled;
};

函数的算法

  1. 创建 数组 shuffled = [],用于保存随机排序后的数组;
  2. 迭代 待排序数组,设定当前迭代索引 index = 0
  3. 生成 随机索引 randrand 的值介于 [0, index]
  4. 添加 元素到 shuffled 数组,值为 shuffled[rand]
  5. 赋予 shuffle[rand] 当前迭代元素的值

运行过程

假定现有待随机排序数组 array = [1, 2, 3, 4, 5],那么第一次迭代的时候情形如下:

1
2
3
4
5
6
7
8
9
array[index]: 1, index: 0, rand: 0, shuffled: []

rand

■ □ □ □ □

index

shuffled = [1];

此时,rand 的值只能与 index 的值相等,所以 shuffled 第一个元素取值为待排序数组的第一个元素。

第二次迭代时,假定 rand 随机值为 0rand 的值只能在 [0, index] 之间):

1
2
3
4
5
6
7
8
9
array[index]: 2, index: 1, rand: 0, shuffled: [1]

rand(assume)

■ ■ □ □ □

index

shuffled = [2, 1];

shuffle[1] 被赋值为 shuffle[0]shuffle[0] 被赋值为 array[1]

最后一次迭代假设此时 rand = 1shuffled = [2, 4, 1, 5]

1
2
3
4
5
6
7
8
array[index]: 3, index: 4, rand: 1, shuffled: [2, 4, 1, 5]

rand(assume)

■ ■ ■ ■ ■

index
shuffle = [2, 3, 1, 5, 4]

shuffled[4] 将会被赋值为 shuffled[1]shuffled[1] 被赋值为 3。所以 shuffled 最后为 [2, 3, 1, 5, 4]

另一种思路

  1. 迭代 待排序数组;
  2. 生成 随机索引 rand,索引的范围为 [0 ~ 待排序数组 - 1]
  3. 抽取 待排序数组中索引为 rand 的元素,抽取行为改变了待排序数组;
  4. 追加 抽取的元素到结果数组的末尾
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function shuffle(array) {
var rand;
var shuffled = [];
for (var i = 0, l = array.length; i < l; i++) {
// 获取随机索引值。
// 随机索引值的范围为[0 ~ 原始数组的长度 - 1]
rand = random(array.length - 1);

// 使用splice方法抽取数组元素
shuffled[i] = array.splice(rand, 1)[0];
}
return shuffled;
}

function random(min, max) {
(Object.prototype.toString.call(max) !== "[object Number]") && (max = min);
return min + Math.floor(Math.random() * (max - min + 1));
}

相对于 _.shuffle,这个方法每个元素在每次迭代过程中就确定下来了,而 _.shuffle 结果数组中每个元素在最后一步完成前都可能改变。