实现一个函数 shuffle(arr)，对数组进行洗牌

推荐答案

function shuffle(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
}

本题详细解读

1. 问题描述

实现一个函数 shuffle(arr)，对数组进行洗牌。洗牌的目的是将数组中的元素随机打乱顺序，使得每个元素出现在每个位置的概率相等。

2. 解题思路

洗牌算法通常使用 Fisher-Yates 算法，也称为 Knuth 洗牌算法。该算法的核心思想是从数组的末尾开始，随机选择一个元素与当前元素交换，直到遍历到数组的开头。

3. 代码解析

• 循环遍历数组：从数组的最后一个元素开始，向前遍历到第二个元素（i > 0）。
• 随机选择索引：在每次循环中，随机选择一个索引 j，范围是从 0 到当前索引 i。
• 交换元素：将当前元素 arr[i] 与随机选择的元素 arr[j] 交换。
• 返回结果：遍历结束后，返回洗牌后的数组。

4. 时间复杂度

• 时间复杂度：O(n)，其中 n 是数组的长度。因为每个元素只需要交换一次。
• 空间复杂度：O(1)，因为只使用了常数级别的额外空间。

5. 示例

const arr = [1, 2, 3, 4, 5];
console.log(shuffle(arr)); // 可能的输出: [3, 1, 5, 2, 4]

6. 注意事项

• 该算法保证了每个元素出现在每个位置的概率相等，是一种公平的洗牌算法。
• 如果数组很大，可以考虑使用更高效的随机数生成器来提高性能。