随机播放歌曲的算法，原来是这么做的，我一直都搞错了

2023-10-07 19:57:07 浏览数 (1)

本篇文章，我将以数组为基础，探索“在线洗牌”的原理。同时，我会以多种方式编写这个原理的代码。还等什么，继续往下看~

方法一：Fisher-Yates 算法

Fisher-Yates 算法的基本前提是遍历条目，将数组中的每个元素与从数组中剩余的未洗牌部分随机选择的元素进行交换。下面的代码中就依据这个算法进行实现的:

代码语言：javascript复制
const shuffle = (array: string[]) => { 
  for (let i = array.length - 1; i > 0; i--) { 
    const j = Math.floor(Math.random() * (i   1)); 
    [array[i], array[j]] = [array[j], array[i]]; 
  } 
  return array; 
}; 
  
const myArray = ["apple", "banana", "cherry", "date", "elderberry"]; 
const shuffledArray = shuffle(myArray); 

console.log(shuffledArray);

上述代码中，我们首先创建了一个 for 循环。在这个循环中，我们将遍历数组中的每个元素，将其位置与数组中的另一个元素交换。

接着，创建一个 i 变量，将 array.lenght-1 值赋给它。

通过从最后一个元素开始并向后操作，可以保证数组末尾的元素与任何其他元素交换的机会相等。

如果你要从开头开始进行洗牌，那么数组开头的元素将有更高的机会被交换多次，从而导致有偏差或不均匀的洗牌。

接着，创建一个 j 变量，它将用于交换索引指针。

然后将索引为 i 的数组赋值给索引为 j 的数组，反之亦然。这将交换数组中的每个项的值并将它们洗牌。

数组解构赋值

接着看到这句代码：[array[i]， array[j]] = [array[j]， [array[i]] 称为数组解构赋值。它允许在两个变量或数组元素之间交换值，而不需要临时变量。

下面我们解释一下，在使用 Fisher-Yates 算法对数组进行洗牌的情况下，数组解构赋值是如何工作的:

  • Array [i] 和 Array [j] 表示数组中需要交换的两个元素。
  • [array[j]， [array[i]] 创建一个临时数组，其中包含 array[j] 和 array[i] 的值，但顺序相反。
  • 通过将 [array[j]， array[i]] 赋值给 [array[i]， array[j]]， array[j] 和 array[i] 的值被交换。

如果我们一步一步地打印出函数的步骤，我们会得到以下结果:

代码语言：javascript复制
["apple", "banana", "cherry", "date", "elderberry"]; 

//1. 交换 elderberry 和 date 
i = 4; // elderberry 
j = 3; // date 
[("apple", "banana", "cherry", "elderberry", "date")]; 

// 2. 交换 elderberry 和 apple 
i = 3; // 
elderberry j = 0; // apple 
[("elderberry", "banana", "cherry", "apple", "date")]; 

// 3. 交换 cherry 和 banana
i = 2; // cherry 
j = 1; // banana 
[("elderberry", "cherry", "banana", "apple", "date")]; 

// 4. 交换 cherry 自己
i = 1; // cherry 
j = 1; // cherry 
[("elderberry", "cherry", "banana", "apple", "date")];

最终，我们就完成了使用 Fisher-Yates 算法进行洗牌的工作。

方法二：使用 sort() 方法和 Random 函数

代码语言：javascript复制
const shuffle = (array: string[]) => { 
    return array.sort(() => Math.random() - 0.5); 
}; 

const myArray = ["apple", "banana", "cherry", "date", "elderberry"]; 
const shuffledArray = shuffle(myArray); 
console.log(shuffledArray);

这是一个简单的 sort() 函数，它会返回一个随机数，该随机数可以是 负数、0 或 正数。sort() 方法在内部比较数组中的元素对，并根据比较函数的返回值确定它们的相对顺序，返回值有三种结果：

  • 如果返回一个负值，则认为第一个元素较小，应该放在排序数组中第二个元素之前。
  • 如果返回一个正值，则认为第一个元素更大，应该放在排序数组中第二个元素之后
  • 如果返回0，则元素的相对顺序保持不变。

Math.random()

当调用 Math.random() 时，它会生成一个伪随机数。“伪随机” 意味着生成的数字看起来是随机的，但实际上是由确定性算法确定的。它返回的数字总是一个介于0到1之间的浮点数。浮点数是可以是正的或负的，并且可以有小数部分的数字，例如 3.14、-0.5、1.0、2.71828 等等。

为什么要从 Math.random() 的结果中减去 0.5 ?

通过从 Math.random() 的结果中减去 0.5，将会引入一个介于 -0.5 和 0.5 之间的随机值。这个随机值**将导致比较函数以随机的方式为不同的元素对返回负、正或零值。**因此，sort() 方法随机打乱数组。

方法3：使用 Array.map() 函数

map() 函数允许迭代数组的每个元素，并根据提供的映射函数将它们转换为新值。map() 函数返回一个包含转换后的值的新数组，而原始数组保持不变。

代码语言：javascript复制
const shuffle = (array: string[]) => { 
    return array.map((a) => ({ sort: Math.random(), value: a }))
        .sort((a, b) => a.sort - b.sort)
        .map((a) => a.value); 
}; 

const myArray = ["apple", "banana", "cherry", "date","elderberry"]; const shuffledArray = shuffle(myArray); 
console.log(shuffledArray);

在这里，循环遍历数组，并在 map() 函数中使用与上面示例中相同的Math.random() 函数，返回具有排序编号和值的对象数组。然后，可以使用 sort() 函数根据这些值对数组进行排序，然后再次调用 map() 函数创建值数组。

代码语言：javascript复制
const shuffle = (array: string[]) => { 
  const shuffled = array.slice(); 
  let currentIndex = shuffled.length; 
  let temporaryValue, randomIndex; 
  while (currentIndex !== 0) { 
    randomIndex = Math.floor(Math.random() * currentIndex); 
    currentIndex -= 1; 
    temporaryValue = shuffled[currentIndex]; 
    shuffled[currentIndex] = shuffled[randomIndex]; 
    shuffled[randomIndex] = temporaryValue; 
  }
  return shuffled; 
}; 

const myArray = ["apple", "banana", "cherry", "date", "elderberry"]; const shuffledArray = shuffle(myArray); 
console.log(shuffledArray);

不过，经过使用上面三种方法，我还是推荐 Fisher-Yates 算法，因为它的时间复杂度很低：O(n)。这意味着输入的数组的大小增加一倍将大致增加一倍的执行时间。类似地，如果输入的数组的大小减半，执行时间也将大约减半。所以数组越大，洗牌的复杂度和时间就越大。

因此，在对大型数组进行洗牌时，这一点值得注意。可能值得考虑其他方法，或者将数组分块并并行运行变换，然后再将其拼凑在一起。

该方法还允许更容易地对任何类型的数组进行洗牌，而不仅仅是 string[] 类型。同时，当使用 TypeScript 泛型时，它也能很好地工作。这允许将任何类型的数组可以传递给函数并进行洗牌。

代码语言：javascript复制
const shuffle = <T>(array: T[]) => { 
  for (let i = array.length - 1; i > 0; i--) { 
    const j = Math.floor(Math.random() * (i   1)); 
    [array[i], array[j]] = [array[j], array[i]]; 
  }
  return array; 
}; 

const strings = ["apple", "banana", "cherry", "date", "elderberry"]; 
const users = [ { name: "John", surname: "Doe" }, { name: "Jane", surname: "Doe" }];

const shuffledArray = shuffle(strings); 
const shuffledObjects = shuffle(users); 

console.log(shuffledArray); 
console.log(shuffledObjects);

这个方法，在日常开发案例中有很多实际的应用。例如:

  • 随机播放歌曲列表
  • 麻将、斗地主游戏随机洗牌
  • 创建随机问题进行样本测验

希望对你有帮助。

这里是编程轨迹，下篇文章再见。

变量 函数 排序 数组 算法

0 人点赞