摘要：描述拷贝数组从扫描数组，选择一个随机数新数组的新数组的新数组的原始数组重复第步，直到末尾最终的新数组就是随机的参考三种洗牌算法
洗牌算法 Fisher-Yates Shuffle
Fisher–Yates 随机置乱算法，通俗说就是生成一个有限集合的随机排列。
描述：
写下从 1 到 N 的数字
取一个从 1 到剩下的数字（包括这个数字）的随机数 k
从低位开始，得到第 k 个还没有被取出的数字，把它写在独立的一个列表的最后一位
重复第 2 步，直到所有的数字都被取出
第 3 步写出的这个序列，现在就是原始数字的随机排列
function getRandom(arr, length) {
const random = Math.floor(Math.random() * length)
// 原始算法将在此处消耗较多资源
if (arr.includes(random)) {
return getRandom(arr, length)
} else {
return random
}
}
function randomArray(arr) {
let newArr = []
const length = arr.length
let index = length - 1
let indexArr = []
while (index >= 0) {
const random = getRandom(indexArr, length)
indexArr.push(random)
newArr.push(arr[random])
--index
}
return newArr
}
Knuth-Durstenfeld Shuffle
Knuth 和 Durstenfeld 在 Fisher 等人的基础上对算法进行了改进，不借助新的组数，直接在原地交换。该算法的基本思想和 Fisher 类似，每次从未处理的数据中随机取出一个数，并和最后一个剩余元素交换，然后剩余元素的数量减一。
function randomArray(arr) {
const length = arr.length
for (let index = length - 1; index > 0; index--) {
const random = Math.floor(Math.random() * index)
const temp = arr[index]
arr[index] = arr[random]
arr[random] = temp
}
return arr
}
Inside-Out Algorithm
Inside-Out Algorithm 算法的思想是从前往后，借助旧数组，将新数组中位置 k 和位置 i 的数字进行交互。
描述
拷贝数组
从 i(0 - N)扫描数组，选择一个随机数 k( 0 <= k <= i)
新数组的[i] = 新数组的[k], 新数组的[k] = 原始数组[i]
重复第 2 步，直到末尾
最终的新数组就是随机的
function randomArray(arr) {
let newArr = arr.concat([])
const length = arr.length
for (let index = 0; index < length; index++) {
const random = Math.floor(Math.random() * (index + 1))
newArr[index] = newArr[random]
newArr[random] = arr[index]
}
return newArr
}
参考
三种洗牌算法 shuffle
Fisher–Yates shuffle From Wikipedia
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/104294.html
摘要：代码实现代码一测试用例输出其中，代码二测试用例输出其中，参考资料洗牌算法学习笔记数组随机排序洗牌算法给数组随机排序洗牌算法原理 原理及步骤 1.定义一个数组（shuffled），长度（length）是原数组（arr）长度2.取 0 到 index (初始0) 随机值 rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr...
摘要：的结果与原书的结果不符。上一篇程序员的算法趣题欲速则不达程序员的算法趣题欲速则不达下一篇程序员的算法趣题同时结束的沙漏本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 2.1 思路1 2.2 思路2 3. 代码及测试 4....
摘要：随机洗牌算法说实话，以前理解数组的排序，都是将数组按照一定的逻辑由大到小或者由小到大排序，我自己是没有碰到过随机打乱数组排序的问题。然后里用的是所谓的洗牌算法，很高效。总结又是三个知识点，分别是随机洗牌分组和函数的实现，没什么复杂的。 这是第三篇关于 Underscore 的源码解读，最近一段时间学的东西很少，自己太忙了，一方面忙着找实习，晚上回去还要写毕业论文。毕业论文真的很忧伤，因...
摘要：首先通过数组调用是令系统随机选取大于等于且小于的伪随机值进入到函数后分别定义了变量和变量为当前数组的长度，先声明，以便在下面中使用。循环一圈后就形成了对数组的洗牌。 这次分享一个随机数组洗牌的一个算法，让你得到随机数组。 假如1个数组的值是这样的： const arr = [a, b, c, d, e, f, g]; 因为在实践操作中，在网上搜可以搜到一大堆随机的这些代码。但是实际上究...
阅读 2993·2021-09-08 10:43
阅读 1014·2019-08-30 15:53
阅读 939·2019-08-30 13:51
阅读 820·2019-08-29 14:03
阅读 781·2019-08-26 18:35
阅读 1215·2019-08-26 13:38
阅读 1559·2019-08-26 10:34
阅读 3460·2019-08-26 10:21
