洗牌算法的实现

问题

实现一个洗牌算法，将数组打散，使每个元素在打散后的数组中的每个位置上等概率出现。

解答

Fisher-Yates 算法

从原始数组中随机抽取元素到新数组中，直到所有元素都被取出。

function shuffle(arr) {
    var result = [],
        random;
    while(arr.length > 0) {
        random = Math.floor(Math.random() * arr.length);
        result.push(arr[random]);
        arr.splice(random, 1);
    }
    return result;
}

这种方法需要删除原数组元素，时间复杂度为 O(n²)。

Knuth-Durstenfeld Shuffle

Fisher-Yates 的优化版本，原地打乱数组，时间复杂度为 O(n)。

从数组末尾开始，每次将当前元素与前面的随机元素交换：

function shuffle(arr) {
    var length = arr.length,
        temp,
        random;
    while(0 != length) {
        random = Math.floor(Math.random() * length);
        length--;
        // 交换元素
        temp = arr[length];
        arr[length] = arr[random];
        arr[random] = temp;
    }
    return arr;
}

ES6 版本使用解构赋值更简洁：

function shuffle(arr) {
    let n = arr.length, random;
    while(0 != n) {
        random = Math.floor(Math.random() * n);
        n--;
        [arr[n], arr[random]] = [arr[random], arr[n]];
    }
    return arr;
}

Array.sort() 方法

适用于小数组的简单实现，但随机性较差：

[1,2,3,4,5,6].sort(function() {
    return .5 - Math.random();
})

关键点

• Fisher-Yates 算法通过随机抽取元素生成新数组，时间复杂度 O(n²)
• Knuth-Durstenfeld 算法通过原地交换优化性能，时间复杂度 O(n)
• 从数组末尾向前遍历，每次将当前元素与前面随机位置的元素交换
• Array.sort() 方法简单但随机性不够好，不推荐用于生产环境
• 使用 ES6 解构赋值可以简化元素交换操作