如何实现数组的乱序（洗牌算法）？

推荐答案

-- -------------------- ---- -------
-------- ----------------- -
  --- ---- - - ---------- - -- - - -- ---- -
    ----- - - ------------------------ - -- - ----
    -------- ------- - -------- --------
  -
  ------ ----
-

-- --
--- ------- - --- -- -- -- -- -- -- -- -- ----
--- ------------- - ----------------------
--------------------------- -- --------

本题详细解读

核心思想：Fisher-Yates (Knuth) Shuffle 算法

Fisher-Yates 洗牌算法是一种高效且公平的乱序数组算法。其核心思想是从数组的最后一个元素开始，向前遍历数组，对于每个元素，随机选择一个小于或等于当前索引的元素，然后交换这两个元素的位置。

算法步骤：

1. 倒序遍历： 从数组的最后一个元素（索引 arr.length - 1）开始，向前遍历到第一个元素（索引 0）。
2. 生成随机索引： 对于当前遍历到的元素（索引为 i），生成一个 0 到 i 之间的随机整数 j。
3. 交换元素： 将索引为 i 的元素和索引为 j 的元素进行交换。
4. 循环结束： 当遍历到数组的第一个元素时，算法结束。

代码解析：

1. 函数定义：

   function shuffleArray(arr) { ... }

   定义一个名为 shuffleArray 的函数，接收一个数组 arr 作为参数。

2. 循环遍历：

   for (let i = arr.length - 1; i > 0; i--) { ... }

   使用 for 循环，从数组的末尾开始向前遍历。注意，循环条件是 i > 0，因为当 i 为 0 时，没有必要进行交换（j 的范围是 0 到 i）。

3. 生成随机索引：

   const j = Math.floor(Math.random() * (i + 1));

   Math.random() 返回一个 0（包括）到 1（不包括）的随机浮点数。乘以 (i + 1) 之后，得到 0 到 i+1 （不包括）之间的随机浮点数。Math.floor() 向下取整，得到一个 0 到 i 之间的随机整数。

4. 交换元素：

   [arr[i], arr[j]] = [arr[j], arr[i]];

   使用 ES6 的解构赋值语法，简洁地交换数组中索引为 i 和 j 的两个元素。

5. 返回数组：

   return arr;

   返回洗牌后的数组。

为什么使用倒序遍历？

倒序遍历是 Fisher-Yates 算法的关键。这样做可以确保在每次迭代中，每个元素都有相同的概率被放到随机的位置，从而保证洗牌的公平性。

示例：

示例代码展示了如何使用 shuffleArray 函数，并打印输出洗牌后的数组。

复杂度分析：

• 时间复杂度： O(n)，其中 n 是数组的长度。算法需要遍历数组一次。
• 空间复杂度： O(1)，算法是原地操作，只需要常数级的额外空间。