数组乱序之洗牌算法

发布于 2017-11-20

复习javascript对象原型的时候碰到一道编程题：
实现随机打乱函数shuffle()，执行效果如下：

1
2
3

>> [1,2,3,4,5,6,7,8,9,0].shuffle()

>> [2,4,1,8,9,6,5,3,0,7]

我的审题思路：

利用 prototype 属性来增加 Array 构造器的 shuffle() 方法。
需要新建一个数组 result 用来存放打乱后的数组。
用for循环从前往后遍历原来的数组。（从后往前亦可）
利用Math.random()方法生成新数组的下标。
每遍历一个原数组的元素，将它赋值给新数组的随机下标位置。
由于生成的随机下标会有重复的几率，先判断当前下标指向的元素是否为空，如果为空，直接赋值，并且继续遍历，否则暂停遍历，重新生成随机下标。

Array.prototype.shuffle = function () {
    var arr = this;
    var len = arr.length;
    var result = [];
    
    for(var i = 0;i < len;){
        var index = ~~(Math.random()*len);
    
        if(result[index] == null){
            result[index] = arr[i];
            i++;
        }
    }
    return result;
}

//~是按位取反运算，~~是取反两次,在这里~~的作用是去掉小数部分

这里涉及到一个知识点：

因为位运算的操作值要求是整数，其结果也是整数，所以经过位运算的都会自动变成整数。
与Math.floor()不同的是，它只是单纯的去掉小数部分，不论正负都不会改变整数部分。
除了~~n 还可以用 n<<0 或 n>>0 或 n|0 取整。

以上实现后，console出每一次的结果，会发现这种实现效率并不高。然后发现了此类问题的一个正解方法：洗牌算法。

Fisher-Yates shuffle

思想 : 每次随机选取一个数，然后将该数与数组中最后(或最前)的元素相交换(如果随机选中的是最后/最前的元素，则相当于没有发生交换)

underscore源码中也是采取这种算法实现的。

//underscore 中采用从前往后遍历元素的方式
function shuffle(a) {
    var length = a.length;
    var shuffled = Array(length);

    for (var index = 0, rand; index < length; index++) {
        rand = ~~(Math.random() * (index + 1));
        if (rand !== index) {
            shuffled[index] = shuffled[rand];
        }
        shuffled[rand] = a[index];
    }

    return shuffled;
}

console.log(shuffle([1,2,3,4,5,6,7,8,9,0]));

//从后往前的版本：
function shuffleFromEnd(a) {
    var len = a.length;

    for(var i = len ;i--;){
        var j = ~~(Math.random()*len);
        var temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    return a;
}

console.log(shuffleFromEnd([1,2,3,4,5,6,7,8,9,0]));

参考文章：
JavaScript 数组乱序 #15

Fisher–Yates Shuffle

上一篇: 关于数组去重的多种方法下一篇: Hello World

Artist Unknown

佚名艺术家

Fisher-Yates shuffle

思想 : 每次随机选取一个数，然后将该数与数组中最后(或最前)的元素相交换(如果随机选中的是最后/最前的元素，则相当于没有发生交换)