JavaScript·洗牌算法实现数组乱序

作者 : jamin 本文共865个字,预计阅读时间需要3分钟 发布时间: 2020-10-18 共1090人阅读

洗牌算法实现数组乱序

关于 JavaScript 数组乱序的方法有多种实现方式,或者借助一些第三方开源工具库如 loadsh 也可以轻松实现,然而要做到数组足够的无规律乱序也非易予,还是有一些要点需要考虑。

sort 方法

最简单的便是使用 sort 函数,代码如下:

const shuffle = arr => {
  arr.sort(() => Math.random() > 0.5)
  return arr
}

在一般场景中以上代码实现便可满足功能需求,但仅是使用 sort 函数的乱序方式并不完美,出于 v8 引擎的底层原因,它对长短数组采用不同的排序方式,并不能真正随机打乱数组排序,简而言之就是最后得到的数组不能足够乱。

由于 v8 引擎出于对性能的考虑,sort 函数对短数组(长度小于 10)使用的是插入排序,对长数组则使用了快速排序。其实不管用什么排序方法,大多数排序算法的时间复杂度介于 O(n) 到 O(n2) 之间,元素之间的比较次数通常情况下要远小于 n(n-1)/2,也就意味着有一些元素之间根本就没机会相比较(也就没有了随机交换的可能),这使 sort 随机排序的算法自然也不能真正随机。通俗的说,其实我们使用 array.sort 进行乱序,理想的方案或者说纯乱序的方案是:数组中每两个元素都要进行比较,这个比较有 50% 的交换位置概率。如此一来,总共比较次数一定为 n(n-1)。而在 sort 排序算法中,大多数情况都不会满足这样的条件。因而当然不是完全随机的结果了。

Fisher–Yates Shuffle 洗牌算法

Fisher–Yates Shuffle 洗牌算法是目前业界最著名的数组乱序算法之一,并且能够使数组足够乱,实现如下:

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

关于更多洗牌算法的细节详见 Fisher–Yates Shuffle,里面通过动画生动地介绍了洗牌算法地高效乱序实现方式。

本站所提供的部分资源来自于网络,版权争议与本站无关,版权归原创者所有!仅限用于学习和研究目的,不得将上述内容资源用于商业或者非法用途,否则,一切后果请用户自负。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容资源。如果上述内容资对您的版权或者利益造成损害,请提供相应的资质证明,我们将于3个工作日内予以删除。本站不保证所提供下载的资源的准确性、安全性和完整性,源码仅供下载学习之用!如用于商业或者非法用途,与本站无关,一切后果请用户自负!本站也不承担用户因使用这些下载资源对自己和他人造成任何形式的损失或伤害。如有侵权、不妥之处,请联系站长以便删除!
金点网络 » JavaScript·洗牌算法实现数组乱序

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用?
本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。
是否提供免费更新服务?
持续更新,永久免费
是否经过安全检测?
安全无毒,放心食用

提供最优质的资源集合

立即加入 友好社区
×