JS数组随机排序的3种方法

在 JavaScript 中，随机打乱数组是一个常见的需求，但并非所有方法都能保证真正的随机性。本文深入探讨了三种打乱数组的方法，重点推荐使用 Fisher-Yates 洗牌算法。该算法通过从数组末尾向前遍历，每次随机选择一个未处理的元素与当前位置交换，确保每个元素出现在任何位置的概率均等，实现真正的均匀随机排列。相比之下，使用 `sort()` 配合 `Math.random()` 的方法存在偏态分布问题，应尽量避免。Fisher-Yates 算法因其 O(n) 的时间复杂度和 O(1) 的空间复杂度，以及在抽奖、游戏发牌、A/B测试、考试系统和数据采样等高随机性要求场景下的可靠性，成为 JavaScript 数组随机打乱的首选方案。

最可靠的方法是使用Fisher-Yates洗牌算法，因为它能确保每个元素出现在任何位置的概率均等；1. 该算法从数组末尾开始向前遍历，每次随机选择一个未处理的元素与当前位置交换；2. 通过逐步缩小随机选择范围，保证每一步都从剩余元素中等概率选取；3. 具有O(n)时间复杂度和O(1)空间复杂度，效率高且可原地操作；4. 相比sort()配合Math.random()的伪随机方法，Fisher-Yates避免了偏态分布问题，实现真正均匀的随机排列；因此在抽奖、游戏发牌、A/B测试、考试系统、数据采样等对随机性要求高的场景中，必须使用该算法以确保公平性和结果准确性。

在 JavaScript 中要随机打乱一个数组，最可靠且被广泛推荐的方法是使用 Fisher-Yates（或 Knuth）洗牌算法。它能确保数组中的每个元素被放置到任何位置的概率都是均等的，从而实现真正的随机排列。

解决方案

/**
 * 使用 Fisher-Yates (Knuth) 算法随机打乱数组。
 * 这种方法保证了每一张牌（元素）都有同等的机会被放置到任何一个位置。
 *
 * @param {Array} array 需要打乱的数组。
 * @returns {Array} 已经打乱的数组。
 */
function shuffleArray(array) {
    // 复制一份数组，避免直接修改原始数组，这在很多场景下是个好习惯。
    // 如果你确定可以修改原数组，直接操作传入的array即可。
    const shuffled = [...array];
    let currentIndex = shuffled.length;
    let randomIndex;

    // 当还有元素未洗牌时...
    while (currentIndex !== 0) {
        // 从剩余的未洗牌元素中随机选择一个。
        randomIndex = Math.floor(Math.random() * currentIndex);
        currentIndex--;

        // 将当前元素与随机选中的元素进行交换。
        // 这种 ES6 的解构赋值语法非常简洁。
        [shuffled[currentIndex], shuffled[randomIndex]] = [
            shuffled[randomIndex],
            shuffled[currentIndex],
        ];
    }

    return shuffled;
}

// 实际应用示例：
let myNumbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];
console.log("原始数组:", myNumbers);
let shuffledNumbers = shuffleArray(myNumbers);
console.log("打乱后的数组:", shuffledNumbers);

let myStrings = ["苹果", "香蕉", "橙子", "葡萄", "芒果"];
console.log("原始字符串数组:", myStrings);
let shuffledStrings = shuffleArray(myStrings);
console.log("打乱后的字符串数组:", shuffledStrings);

为什么直接使用 sort() 配合 Math.random() 是一个糟糕的主意？

你可能在网上看到过一些教程，或者自己尝试过这样的代码：arr.sort(() => Math.random() - 0.5); 这种写法看起来很简洁，甚至初次运行效果也“貌似”随机，但从专业的角度来看，这是一个非常糟糕的打乱数组的方法。

问题出在 Array.prototype.sort() 方法的工作原理上。sort() 接收一个比较函数，这个函数应该返回负数、零或正数，来指示两个元素谁在前谁在后。当你的比较函数返回 Math.random() - 0.5 时，它确实会随机返回正数或负数，但这并不能保证每个元素被放置到任何位置的概率是均等的。实际上，sort() 方法的内部实现（比如 V8 引擎使用的 TimSort 或 QuickSort）并不是为这种随机比较设计的。它依赖于比较结果的传递性，即如果 A < B 且 B < C，那么 A < C。而 Math.random() 引入的随机性破坏了这种传递性，导致 sort() 无法有效地进行排序，最终的结果就是某些元素更容易“挤”到数组的两端，或者某些排列出现的概率远高于其他排列，形成一种“偏态分布”。

在我看来，这种“伪随机”的方法不仅不严谨，还可能在一些对随机性有严格要求的场景（比如抽奖、A/B 测试分组）中引入难以察觉的偏差，最终导致结果不准确甚至产生不公平的情况。所以，即使它写起来很短，也请务必避免使用。

Fisher-Yates 洗牌算法的工作原理和优势是什么？

Fisher-Yates 洗牌算法之所以被认为是“黄金标准”，是因为它在数学上被证明可以产生均匀的随机排列，即每一种可能的排列组合都有相同的出现概率。它的工作原理其实非常直观且优雅：

1. 从数组的最后一个元素开始：算法不是从头开始，而是从数组的末尾向前遍历。
2. 随机选取一个未处理的元素：在每次迭代中，它会从当前位置（包括当前位置）到数组开头的所有元素中，随机选择一个元素。
3. 交换位置：将当前位置的元素与随机选中的元素进行交换。
4. 缩小范围：一旦一个元素被交换到当前位置（即它被“处理”了），它就不再参与后续的随机选择，因为我们已经为它找到了一个“最终”的随机位置。算法通过递减 currentIndex 来缩小随机选择的范围。

优势：

• 真正的均匀分布（Unbiased）：这是它最大的优势，保证了所有排列出现的概率相同。
• 效率高（Efficient）：算法的时间复杂度是 O(n)，这意味着它只需要遍历数组一次。对于包含 n 个元素的数组，它执行的步骤数与 n 成正比，这使得它在大规模数据处理时也非常高效。
• 原地洗牌（In-place）：如果你选择直接修改原数组（而不是像我示例中那样先复制一份），Fisher-Yates 算法可以在不使用额外大量内存的情况下完成洗牌操作，空间复杂度是 O(1)。
• 简单易懂：一旦理解了其核心逻辑，代码实现也相对简洁明了。

这种算法的精妙之处在于，它每次都确保了当前位置的元素是从所有尚未确定最终位置的元素中随机选取的。

在实际项目中，何时需要特别注意数组打乱的“真随机性”？

虽然对于一些简单的、对随机性要求不高的场景（比如前端展示的图片轮播顺序），你可能觉得随便打乱一下都行，但很多实际项目对“真随机性”有着非常严格的要求。忽视这一点可能会带来意想不到的问题，甚至影响业务的公平性或数据的准确性。

• 抽奖系统或游戏发牌：这是最典型的例子。如果你的抽奖系统不是真随机的，那么某些用户中奖的概率会高于其他人，这会引发公平性问题，甚至可能涉及法律风险。纸牌游戏（如扑克、麻将）的发牌，如果洗牌算法有偏见，会严重影响游戏的平衡性和玩家体验。
• A/B 测试或实验设计：在进行用户体验优化、产品功能测试时，你通常需要将用户随机分配到不同的组（A组看到旧设计，B组看到新设计）。如果分组不是真随机的，那么两组用户之间可能存在系统性差异（例如，某个渠道来的用户更多地被分到了A组），导致实验结果不准确，无法得出有效的结论。
• 在线教育或考试系统：为了防止学生作弊或背题，试卷中的题目顺序、选项顺序通常需要随机打乱。如果打乱不够随机，可能会出现某些学生总是遇到相同顺序的题目，或者某些选项总是出现在特定位置，影响考试的公平性和有效性。
• 数据采样与分析：当需要从一个大数据集中随机抽取一部分样本进行分析时，如果采样过程不是真随机的，那么样本可能无法代表总体，导致分析结果出现偏差，甚至得出错误的结论。
• 音乐播放器或内容推荐：虽然不是严格的“公平性”问题，但用户对音乐播放器的“随机播放”功能经常有抱怨，觉得它不够随机。一个真正随机的洗牌算法能提升用户体验，避免用户总是听到相似的歌曲序列。

在这些场景下，使用 Fisher-Yates 算法就显得尤为重要。它提供了一个可靠的、经过数学验证的解决方案，确保你的随机化操作是真正公平和无偏的。

文中关于JavaScript,随机性,数组打乱,均匀分布,Fisher-Yates算法的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《JS数组随机排序的3种方法》文章吧，也可关注golang学习网公众号了解相关技术文章。