Daily Notes

Just Some Notes

洗牌算法

洗牌算法,用于随机打乱一个有限列表内的元素顺序,目前公认最好的洗牌算法就是Fisher-Yates算法,使用JavaScript实现Fisher-Yates算法对一个数组进行顺序打乱的代码如下.

/**
 * Fisher-Yates算法
 * 将数组元素的顺序原地打乱
 * 时间复杂度O(N)
 * @param {Array<any>} 数组
 */
function shuffle(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
        const idx = Math.floor(Math.random() * (i + 1));
        const tmp = arr[i];
        arr[i] = arr[idx];
        arr[idx] = tmp; 
    }
}