数组洗牌算法-shuffle

数组洗牌，最近直接的想法是从数组随机取出一个元素，放到另一个数组中，但是这样取出的元素会有重复，必须采取一定的方法保证：

1. 元素不能重复
2. 元素被抽取的概率相等，即随机性

数组洗牌经典算法有两种：

1. Fisher-Yates Shuffle(复杂度(n^2))

数组的删除以及新的copy数组都是耗费时间和空间的。

javascript实现

function FyShuffle(arr){

    var copy = [],

        len = arr.length,

        n;

    while(len)

        n = Math.floor(Math.random() * len--);

        res.push(arr.splice(n,1)[0]);

    }

    return copy;

}

2. Knuth-Durstenfeld Shuffle(复杂度(n)，是Fisher-Yates算法的改进版本)

kd方法是一种in-place的置换方法，节省空间，性能也好，随机性好，python内置的random.shuffle用了此算法。

javascript实现

function KdShuffle(arr){

    var len = arr.length,

        i,temp;

    while(len){

        i = Math.floor(Math.random() * len--);

        temp = arr[i];

        arr[i] = arr[len];

        arr[len] = temp;

    }

    return arr;

}

参考：http://www.cnblogs.com/Wayou/p/fisher_yates_shuffle.html
　　　http://www.cnblogs.com/tudas/p/3-shuffle-algorithm.html

巴特西

数组洗牌算法-shuffle

最新文章

热门文章