JavaScript随机打乱数组元素的位置(洗牌算法)

来源:岁月联盟 编辑:exp 时间:2012-10-22

[javascript] 
function mess(arr){ 
    var _floor = Math.floor, _random = Math.random, 
        len = arr.length, i, j, arri, 
        n = _floor(len/2)+1; 
    while( n-- ){ 
        i = _floor(_random()*len); 
        j = _floor(_random()*len); 
        if( i!==j ){ 
            arri = arr[i]; 
            arr[i] = arr[j]; 
            arr[j] = arri; 
        } 
    } 
    return arr; 

var testa = [1, 2, 3, 4, 5, 6, 7]; 
mess(testa); 
console.log(testa); 
要注意一点的是,这是改变原数组的,不想改变原数组的话请先拷贝原数组:

[javascript] 
var testa = [1, 2, 3, 4, 5, 6, 7]; 
var newarr = mess( testa.slice(0) ); //这里只是浅拷贝数组 
console.log(testa); 
console.log(newarr); 
这个洗牌函数算好么?
呵呵,或许经过测试你会发现:有一些元素在洗完牌后位置依然是原来的位置,而且出现这种元素的几率很大。那怎么改进呢?

在现实当中,我们洗完牌后,通常还会把扑克一分为二(俗称“切牌”),然后交换这两部分的上下位置。嗯,对,这个洗牌函数里我们没有切牌!

所以我们可以做如下改进:

[javascript] 
//洗牌算法 
function mess(arr){ 
    var _floor = Math.floor, _random = Math.random, 
        len = arr.length, i, j, arri, 
        n = _floor(len/2)+1; 
    while( n-- ){ 
        i = _floor(_random()*len); 
        j = _floor(_random()*len); 
        if( i!==j ){ 
            arri = arr[i]; 
            arr[i] = arr[j]; 
            arr[j] = arri; 
        } 
    } 
    //增加切牌操作 
    i = _floor(_random()*len); 
    arr.push.apply(arr, arr.splice(0,i)); 
    //return arr; //要不要返回打乱后的数组呢? 

var testa = [1, 2, 3, 4, 5, 6, 7, 8, 9]; 
var newarr = testa.slice(0); 
mess(newarr); 
console.log(testa); 
console.log(newarr); 
好,现在看来,已经很少出现洗牌前后位置不变的元素了,可以说大功告成了。
巴特,稍等,我们已经发现,这个洗牌函数是会改变原始数组的,那么,接下来有一个问题:这个函数要不要返回值,返回打乱后的数组?因为我可能想这么来调用它:
[javascript]  
var testa = [1, 2, 3, 4, 5, 6, 7]; 
var newarr = mess( testa.slice(0) ); //这里只是浅拷贝数组 
这种调用方式好吗?如果加上这种调用方式,那么可以算一共有两种调用方式。
其实,对这么一个简单函数而言,调用方法应该越简单越好,简单易用,最好只提供一种调用方式。使用方法多了就需要人多记东西,容易让人迷糊。所以,我不想给这个洗牌函数返回值,不想提供这种调用方式。
而且还有一个原因:这有利于强调这是一个改变原数组的函数,而不是通过返回值来给出调用结果,这样可以让调用者明确知道调用函数的影响。