🐱个人主页:不叫猫先生
🙋♂️作者简介:专注于前端领域各种技术,热衷分享,期待你的关注。
💫系列专栏:vue3从入门到精通
📝个人签名:不破不立
一、原地算法
在谈sort之前,我们先了解一下原地算法,什么事原地算法呢?所谓原地算法就是说基于原有的数据结构进行一定的操作修改,而不借助额外的空间。使用原地算法时,其内存干净,空间复杂度是O(1),可以减少没必要的内存,避免造成内存浪费和冗余。当然,减小内存损耗会带来算法复杂度和时间消耗的增加,所以是一个Tradeoff。Tradeoff 是一种针对目标选择有效的路径的思维方式,需要对做的事情权衡利弊,选择最佳方式处理问题。
二、Array.property.sort()
含义:sort方法基于原地算法实现数组排序,直接对数据进行排序
参数:sort(compare(a,b)),指定顺序对数组进行排序,不写参数的时候,默认会将原数据转换成字符串按照字符的Unicode编码进行排序。
compare(a,b)中,a、b都是比较参数,当
a-b>0 ,交换位置
a-b=0,位置不变
a-b<0,位置不变
随机排序我们都会想到Math的random方法,具体实现如下,但是这样操作确有缺陷,理论很丰满,实践很残酷。
1、方法一(不推荐)
arr.sort(() => Math.random() - 0.5)
- 缺陷:chrome浏览器对于数组长度为10以内的使用插入排序,反之则为快速排序和插入排序的组合,故而并不能做到随机分布。
- 测试:测试某数据在数组中各个位置的次数。
let obj = {};
let count = 0;
let n = 10000;
while (n--) {
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14]
arr.sort(() => Math.random() - 0.5)
let index = arr.indexOf(1)//取1在数组排序后的位置
obj[index] ? obj[index]++ : obj[index] = 1
}
- 输出:
- 图示:
ECMAScript中关于Array.prototype.sort(comparefn)的标准,其中并没有规定具体的实现算法,但是提到一点: Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments.也就是说,
对同一组a、b的值,comparefn(a, b)需要总是返回相同的值。而上面的() => Math.random() -0.5(即(a, b) => Math.random() - 0.5)显然不满足这个条件
。 翻看v8引擎数组部分的源码,注意到它出于对性能的考虑,对短数组(例如长度小于10)使用的是插入排序,对长数组则使用了快速排序。
理解:(a, b) => Math.random() - 0.5,每次a,b都是固定的,但是Math.random() - 0.5)却是随机的,
2、方法一改良
构造一个新数组,如[{v:1,k:Math.random()},{v:1,k:Math.random()}]
,具体如下:
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14]
for(let i=0;i<arr.length;i++){
shuffle(arr)
}
function shuffle(arr){
let newArr = arr.map(item=>({v:i,k:Math.random())})
newArr.sort((a,b)=> (a.k - b.k))
arr.splice(0, arr.length, ...newArr.map(i => i.v));
}
三、洗牌算法实现随机排序
1、换牌
逻辑:从一副牌中抽取一张,与最后一张牌进行交换,放到最后证明该牌已经被随机抽选过,而被交换的牌就排在前面,就有机会被继续抽选。
- 随机抽取一张
- 抽取的放置到最后位置
- 最后位置的牌放置在随机抽取的位置
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14];
funtion shuffle(ar){
for(let i = arr.length;i>0;i--){
let temRandom = Math.floor(Math.random()*i)
arr[i] = arr[temRandom];
arr[temRandom] = arr[i]
}
return arr
}
shuffle(arr)
2、抽牌
逻辑:从一副牌抽取一张放置一旁,则这幅牌会越抽越少,直至到最后一张。文章来源:https://www.toymoban.com/news/detail-400957.html
- 随机抽取一张
- 抽取的牌放置旁边
- 在抽取的那副牌冲除去随机抽取的那张牌
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14];
funtion shuffle(ar){
let temp = [];
for(let i = arr.length;i>0;i--){
let temRandom = Math.floor(Math.random()*i)
temp.push(arr[temRandom])
arr.splice(temRandom,1)//抽取一张后,要除去这张牌,然后在剩下的牌中继续抽
}
return temp
}
shuffle(arr)
附:本文用到的JS基础
本文用到数组方法基本介绍文章来源地址https://www.toymoban.com/news/detail-400957.html
- splice返回被删除的元素,直接修改数组数据,可接受1/2/3个参数
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14];
arr.splice(0)//删除索引从0开始的所有数据,即删除所有数据
arr.splice(0)//删除索引从1开始的所有数据,即只保留第一位数据
arr.splice(2,1)//删除索引为2的数据
arr.splice(0,arr.length,5)//删除原数组的数据,并把数据5填充到arr中
- Math.floor() 向下取整
- Math.ceil() 向上取整
到了这里,关于JS中数组随机排序实现(原地算法sort/shuffle算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!