如何使用 JavaScript 随机打乱数组

打乱数组顺序是一个基本的编程过程，特别是在涉及随机化的情况下，例如游戏限制或仅仅是创建随机列表。可以使用 Fisher-Yates 算法（也称为 Knuth 算法）来打乱 JavaScript 数组。该算法使用 math.random() 方法以随机顺序对给定数组进行排序。

数组洗牌概述

在使用 JavaScript 时，经常需要打乱或随机排列数组中的元素。本文将解释如何在 JavaScript 中打乱 数组 顺序，探讨几种方法和策略，包括最有效和推荐的方法。

打乱顺序是指不按固定顺序随机重排数组的元素。这在各种情况下经常需要，例如：

• 以随机顺序排列元素列表（如测验问题）。
• 为游戏重新排列一副牌。
• 从输入信息中随机选择样本。

在 JavaScript 中打乱数组顺序有多种方法。随机性和随机算法与过程确保每个元素出现在任何位置的几率均等。

为什么要使用数组洗牌？

以下是一些数组洗牌至关重要的典型使用场景：

• 游戏：玩纸牌游戏时，可能需要打乱牌堆（表示为数组）。
• 随机化：该方法用于以不同顺序排列测验问题。它还用于以不同顺序排列文本或图形组件。
• 采样：从一组数据点中选择随机样本称为采样。
• 模拟：蒙特卡罗模拟等随机模拟需要打乱的数据。

数组洗牌技术

打乱数组的方法有多种，其中主要的方法是 Fisher-Yates 算法。它被认为是打乱数组元素的最佳技术。

1. 使用 Fisher-Yates 算法打乱 JavaScript 数组

Fisher-Yates 算法，有时也称为 Knuth 算法，是重排数组最流行和最有效的方法之一。这种方法是随机化元素的最佳方式，因为它确保数组的每种可能组合都是等概率的。

Fisher-Yates 算法如何工作

Fisher-Yates 算法通过从最后一个成员到第二个元素（从右到左）遍历数组来操作。它通过从当前位置到数组开头选择一个随机索引，在每个位置交换元素。

说明

让我们从最后一个元素开始：选择数组的最后一个元素。

• 选择一个随机索引
  选择一个介于第一个位置和当前位置之间的随机索引。
• 交换元素
  将随机索引处的元素与当前位置的元素交换。
• 移至下一个元素
  重复此过程，直到到达第一个元素，然后移至左边的下一个元素。

语法

以下语法展示了使用 Fisher-Yates 方法打乱数组。

说明

• 使用“for 循环”，我们从最后一个元素 (arr.length - 1) 开始循环，一直到第一个元素。
• 使用 Math.random()，生成一个 0 到 1 之间的随机数。
• floor(): 这确保随机数是一个介于 0 和当前索引 (i) 之间的整数。
• [arr[i], arr[j]] = [arr[j], arr[i]]; 这个表达式用于通过交换索引 i 和 j 处的成员来解构数组。

示例

以下示例展示了打乱数字或字符串元素数组的操作。

示例 1

以下示例展示了使用 JavaScript Fisher-Yates 算法打乱数字数组。

输出

输出显示了打乱后的数组。

示例 2

以下示例展示了使用 JavaScript Fisher-Yates 算法打乱字符串数组。

输出

输出显示了打乱后的数组。

示例 3

以下示例展示了使用 JavaScript Fisher-Yates 算法打乱小数数组。

输出

输出显示了打乱后的数组。

Fisher-Yates 的时间复杂度

• Fisher-Yates 算法的时间复杂度为 O(n)，其中 n 是数组的长度。
• 这种方法效率很高，因为它只需要遍历数组一次，并且每个元素只交换一次。

2. 在 JavaScript 中应用 array.sort() 方法

我们可以使用自定义比较函数和 JavaScript 的 array sort() 方法来创建一个打乱后的数组。sort() 函数接收一个返回（随机值 - 0.5）作为比较器的函数。

随机比较器是一种流行但效率不高的使用 sort() 方法打乱数组的方式。虽然这种方法会以随机顺序对数组进行排序，但它不能保证排列的均匀分布。不建议在生产环境中使用，因为它可能产生有偏差的结果。

语法

以下语法展示了在 JavaScript 中应用 array.sort() 方法来打乱数组。

示例

以下示例展示了在 JavaScript 中使用 array.sort() 方法打乱数字或字符串元素数组。

示例 1

以下示例展示了在 JavaScript 中使用 array.sort() 方法打乱数字数组。

输出

输出显示了打乱后的数组。

示例 2

以下示例展示了在 JavaScript 中使用 array.sort() 方法打乱字符串数组。

输出

输出显示了打乱后的数组。

使用 sort() 进行洗牌的困难

• 时间复杂度：排序算法的时间复杂度通常为 O(n log n)，这比 Fisher-Yates 的 O(n) 技术效率低，因为它没有为随机化进行优化。
• 不可靠的随机性：打乱后的数组可能会有偏差，因为排序算法依赖于随机比较值，这可能导致结果分布不均匀。

3. 将 Math.random() 方法应用于 array.reduce()

在为每个元素实现逻辑后，array.reduce() 方法会返回一个单一的输出。每次 reduce 方法迭代时，我们可以使用 math.random() 方法来打乱组件。

语法

以下语法展示了将 Math.random() 方法应用于 array.reduce() 方法来打乱数组。

示例

以下示例展示了使用 Math.random() 方法和 array.reduce() 方法来打乱数字或字符串元素数组。

示例 1

以下示例展示了使用 JavaScript 的 random 和 reduce 方法打乱数字数组。

输出

输出显示了打乱后的数组。

示例 2

以下示例展示了使用 JavaScript 的 random 和 reduce 方法打乱字符串数组。

输出

输出显示了打乱后的数组。

与递归相关的困难

• 性能：这种方法可能效率低下，因为 splice() 的时间复杂度为 O(n)。
• 栈溢出：如果数组非常大，可能会发生栈溢出错误，因为递归会重复调用该方法。

修改数组的最佳方法

• 使用 Fisher-Yates：事实证明，打乱数组最有效和最公平的方法是使用 Fisher-Yates 算法。为了获得最佳性能和随机化效果，应始终选择此算法而不是其他算法。
• 谨慎使用 sort()：虽然使用带有随机比较器的 sort() 看起来很简单，但通常应避免使用这种方法进行洗牌，因为它速度慢且缺乏真正的随机性。
• 考虑使用库：如果您不想创建自己的洗牌逻辑，像 Lodash 这样的流行库提供了可靠且高效的洗牌例程。

下表显示了三种打乱数组方法的时间和空间复杂度。

结论

在许多应用中，如模拟和游戏，打乱数组是必要的。由于其效率和无偏的随机化，Fisher-Yates 算法是数组随机化的行业标准。虽然存在其他洗牌技术，如排序或递归洗牌，但它们通常在准确性或性能方面存在问题。

在开发需要洗牌的 JavaScript 应用程序时，您应该使用 Fisher-Yates 算法。它简单高效，并通过确保每个数组排列具有相等的概率来保证公平的随机化。