JS中数组随机排序实现(原地算法sort/shuffle算法)

这篇具有很好参考价值的文章主要介绍了JS中数组随机排序实现(原地算法sort/shuffle算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🐱个人主页:不叫猫先生
🙋‍♂️作者简介:专注于前端领域各种技术,热衷分享,期待你的关注。
💫系列专栏: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
		}
  • 输出:
    JS中数组随机排序实现(原地算法sort/shuffle算法)
  • 图示:
    JS中数组随机排序实现(原地算法sort/shuffle算法)

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、抽牌

逻辑:从一副牌抽取一张放置一旁,则这幅牌会越抽越少,直至到最后一张。

  • 随机抽取一张
  • 抽取的牌放置旁边
  • 在抽取的那副牌冲除去随机抽取的那张牌
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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [排序算法]:归并排序(Merge Sort)(递归与非递归实现详解)

            归并排序,是创建在归并操作上的一种有效的排序算法。算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。归并排序思路简单,速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。

    2024年01月20日
    浏览(44)
  • 【第42天】Arrays.sort 与 Collections.sort 应用 | 整形数组与集合的排序

    本文已收录于专栏 🌸《Java入门一百练》🌸

    2024年02月02日
    浏览(44)
  • 数组排序 sort() 方法 (映射对含有大小写的字符串进行排序)

    结论先行: sort() 方法: 用于对数组元素进行 排序 ,默认升序。如果指明了参数,那数组会按照 比较函数 的返回值进行排序。    sort() 方法比较两个值时,将值发送给比较函数,根据返回的(负、零、正)值对值进行排序。 举例,a 和 b 两个将要被比较的元素: 如果 a-

    2024年04月25日
    浏览(46)
  • Java创建一个长度为10的数组,利用Arrays.sort(), 为数组元素排序

    程序要求:1)创建一个整型数组,数组的长度为10.                     2)给数组元素赋值,要求乱序。                   3)利用fori循环将数组元素依次输出。                      4)利用Arrays.sort(), 为数组元素排序                   5)采用增加for循环将

    2024年02月08日
    浏览(52)
  • JAVA的sort用法详解(二维数组排序,List<>排序,lambada表达式,自定义类型排序)

    目录 前言: 一维数组降序: 方法1.Comparator接口: 代码实现: 方法2.Collections.reverseOrder(): 代码实现:  二维数组排序: 代码如下: List排序: 代码如下: 自定义类型比较排序: 按照年龄逆序排序: 按照姓名升序排序: lambada表达式简写: 一维数组逆序代码: 二维数组排

    2024年04月09日
    浏览(64)
  • 原生JS之sort排序方法详解

    在JavaScript中排序主要用到的api就是sort了,但是使用sort有几个坑需要注意,让我们一起来看看 sort() 方法用于对 数组 的元素进行排序。排序顺序可以是字母或数字,并按升序或降序。 默认排序顺序为按字典升序。 在不使用参数时,sort使用的是字典排序 如果数组中元素都是

    2024年02月03日
    浏览(35)
  • 【排序算法详细介绍】桶排序(Bucket Sort)冒泡排序(Bubble Sort)快速排序(Quick Sort)

    今天学习了一些简单的 排序算法 ,其实在我们平时解决问题中经常用到,今天正好一起看了看,记录一下。 如果对你也有帮助,我很开心~ 桶排序是一种排序算法,它将数组划分为一些 有序的桶 ,然后 每个桶再分别排序 。最后,将所有的桶合并起来,得到一个有序的数组。桶排

    2024年01月25日
    浏览(49)
  • d3.shuffle、Fisher–Yates算法以及js 中的slice

    D3.shuffle() 方法用于将数组中的元素随机排序。它使用 Fisher–Yates 洗牌算法,该算法是无偏的,具有最佳的渐近性能(线性时间和常数内存)。 D3.shuffle() 方法的语法如下: 其中: array 是原数组。 start 是开始索引,默认为 0。 end 是结束索引,默认为数组的长度。 如果 end 是

    2024年02月08日
    浏览(37)
  • 排序算法(stable_sort(), sort())

    sort函数我相信大家都不陌生,今天介绍一个新的排序算法stable_sort stable_sort:稳定排序算法,维持相等元素的原有顺序。 假如我们定义一个字符串数组 这些字符串是按照字典序排列的,我们现在想要words按照单词长度从小到大重排的同时,还希望具有相同长度的元素按照字典

    2024年02月07日
    浏览(53)
  • 【排序算法】堆排序(Heap Sort)

    堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 学习堆排序之前,有必要了解堆!若读者不熟悉堆,建议先了解堆(建议可以通过二叉堆,左倾堆,

    2024年02月01日
    浏览(69)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包