当前位置:首页 > 技术 > 正文内容

JavaScript冒泡排序+Vue可视化冒泡动画

Lotus2022-12-19 10:19技术

1.gif

冒泡排序(Bubble Sort)算是前端最简单的算法,也是最经典的排序算法了。网上JavaScript版本的冒泡排序很多,今天用Vue实现一个动态的可视化冒泡排序。

01、JavaScript冒泡排序

冒泡排序原理也比较简单,就是相邻元素两两比较排序,把大的元素冒泡排序到后面,递归所有相邻元素组合完成排序。

1.1、原理

有一个无序数组:let arr = [100, 5, 6, 17, 3, 1],长度为len=6

  • 、从第一位元素100(0索引)开始,比较相邻arr[0]、arr[1]元素的大小,大的排后面,如果arr[0]>arr[1]则交换值位置。
  • 、如下图,依次相邻元素比较、交换,一轮完成后,最大元素就到了最右边了。这个过程中,最大的元素(最大的泡泡)就像冒泡一样到了末尾。

image

  • ③、然后继续对剩下的前面len-1=5个元素重复上述步骤,直到只剩下一个元素。这是一个递归的过程,递归到第一个元素,就完成了冒泡排序。

image

冒泡排序的动画过程如下图,排序过程很直观,一目了然,下一章节也实现一个跟好的。

1.2、JavaScript实现

经典冒泡排序算法,用两个for循环来实现所有元素的两两对比排序。统计了一下排序次数,一共比较了15次。冒泡排序的时间复杂度是O(n^2),这是最大值,最小为O(n)。

//经典冒泡排序算法
//从小到大冒泡排序
let arr = [100, 5, 6, 17, 3, 1];
let count=0; //计数器
function bubbleSort(arr) {
    const len = arr.length;
    let t;count=0;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            count++;
            //比较相邻两个元素
            if (arr[j] > arr[j + 1]) {
                //交换两个元素,大的往后排列
                t = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = t;
            }
        }
    }
    return arr;
}
console.log(bubbleSort(arr),"比较次数:",count);
//[1, 3, 5, 6, 17, 100] '比较次数:' 15

上面代码中交换两个元素位置的时候,用了一个中间变量(t),可以改进一下。用一个解构赋值来交换值,就不用额外的一个中间变量(t)了。

let arr = [100, 5, 6, 17, 3, 1];
function bubbleSort(arr) {
    const len = arr.length;
    for (let i = 0; i < len - 1; i++) {
        for (let j = 0; j < len - i - 1; j++) {
            //比较相邻两个元素
            if (arr[j] > arr[j + 1]) {
                //用结构赋值进行交换
                [arr[j], arr[j + 1]] = [arr[j+1], arr[j]];
            }
        }
    }
    return arr;
}
console.log(bubbleSort(arr));
//[1, 3, 5, 6, 17, 100]

02、Vue实现一个冒泡动画

用Vue来实现一个可视化的冒泡排序,用Vue就不用去操作Dom了,只需要要处理好排序过程即可,因此首先要对排序过程进行改造。

2.1、排序过程改造

上一章节的排序是连续执行,瞬间完成的。要实现可视化的排序效果,每一个排序步骤之间得有间隔,给过渡动画留时间。就需要把排序的每一个步骤拆开,可以单独控制执行。

  • 定义一个排序对象SortItem,包装待排序元素,用于可视化展示,属性包括排序值、泡泡大小、泡泡颜色。
  • 用上面的排序对象SortItem,生成排序对象集合,正式排序步骤中用该集合。方法的参数为排序元素字符串,空格隔开,如“9 100 6 17 3 1”。
//定义一个排序对象,包装待排序元素
function SortItem(n) {
    this.value = n;
    this.size = 30 + n + 'px';  //泡泡大小,初试大小30px
    this.color = bubbleColor.default;
}
//生成排序对象集合,参数为排序元素字符串,如“9 100 6 17 3 1”
function generateSortItems(arrStr) {
    let arrItems = [];
    let arr = arrStr.trim().split(' ');
    for (let i = 0; i < arr.length; i++) {
        arrItems[i] = new SortItem(window.parseInt(arr[i]));
    }
    return arrItems;
}

泡泡列表展示效果如下:

image.png

  • 然后就是排序过程了,对排序对象集合进行遍历,把每一次排序操作包装成一个(闭包)函数,放到一个集合里,后面就可自定义调用执行了。
  • 先是用集合实现了一遍,发现这个场景用迭代器Generator更优雅,马上重构,上迭代器!每次迭代yield返回排序的函数。
//迭代器实现排序步骤的拆分
function* generateSortFunc(items) {
  const len = items.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      //迭代器返回的是一个(闭包)函数,为每一个排序步骤
      yield () => {
        //执行排序前重置泡泡颜色
        resetColor(items);
        //正在排序的泡泡元素高亮
        items[j].color = bubbleColor.inprocess;
        items[j + 1].color = bubbleColor.inprocess;
        if (items[j].value > items[j + 1].value) {
          [items[j], items[j + 1]] = [items[j + 1], items[j]];
        }
      }
    }
    //完成一轮排序,末尾泡泡元素标记为完成态颜色
    items[len - i - 1].color = bubbleColor.completed;
  }
}

????什么是Generator?

  • 她是一个迭代器,返回一个遍历器对象,符合可迭代协议和迭代器协议,可用next()for(of)迭代。
  • 她是可控函数:内部代码可以自由控制暂停和继续执行。标准的函数是一次性执行完毕,直到末尾或return语句。而生成器的函数可以由yield暂停执行(交出控制权),next()恢复执行。
  • 她是一个状态机,封装了多个内部状态。
  • 她是异步任务管理容器,提供一种异步的实现方案。

Generator 使用一个特殊的函数语法function*(带星*号)创建生成器generator,调用生成器函数获得一个生成器对象,该对象的实例方法:

实例方法 描述
next() 恢复执行,返回一个由 yield表达式生成的值:{value: 1, done: false}
return(value?) 返回给定的值并结束生成器,可提前中止生成器。
throw() 向生成器抛出一个错误,生成器内部如没处理则会中止

2.2、可视化排序

接下来就不难了,排序的执行就是调用执行器的next()方法,如果返回对象的done属性为true,则表示迭代完成,否则继续迭代,执行排序函数。

//单步执行
play() {
  let next = this.sortFunc.next();
  if (next.done) {
    this.sortItems.forEach(item => item.color = bubbleColor.completed);
    this.stop();
  }
  else
    next.value();
},
  • <li>元素来显示排序对象。
  • 移动动画用的Vue的<transition-group>组件来实现。
  • “单步执行”就是点击一次只执行一步,“自动执行”则会自动顺序执行。
  • 修改参数后需”重置“进行初始化。

手动单步执行效果:

1.gif

自动执行或更多排序参数可以直接查看在线代码示例:掘金-代码(可视化冒泡),完整代码也在这里。

点击查看【juejin】


参考资料


©️版权申明:版权所有@安木夕,本文内容仅供学习,欢迎指正、交流,转载请注明出处!原文编辑地址-语雀

原文链接

扫描二维码推送至手机访问。

版权声明:本文来源于网络,仅供学习,如侵权请联系站长删除。

本文链接:https://news.layui.org.cn/post/1170.html

分享给朋友:

“JavaScript冒泡排序+Vue可视化冒泡动画” 的相关文章

ETL工具Datax、sqoop、kettle 的区别

一、Sqoop主要特点: 1.可以将关系型数据库中的数据导入到hdfs,hive,hbase等hadoop组件中,也可以将hadoop组件中的数据导入到关系型数据库中; 2.sqoop在导入导出数据时,充分采用了map-reduce计算框架(默认map数为4),根据输入条件生成一个map-reduce作业(只有map,没有reduce),在hadoop集群中运行。采用map-reduce框架同时在...

激活数据价值,探究DataOps下的数据架构及其实践丨DTVision开发治理篇

据中国信通院发布,2012 年到 2021 年 10 年间,我国数字经济规模由 12 万亿元增长到 45.5 万亿元,在整个 GDP 中的比重由 21.6% 提升至 39.8%。顺应时代发展新趋势,“数据” 成为新的生产要素已是毋庸置疑的共识。 如果说数据中台的崛起代表着企业数字化转型从流程驱动走向数据驱动,从数字化走向智能化。那么 DataOps,则是实现数据中台的一个优秀的理念或方法论。 D...

多功能手持VH501TC采集仪如何设置振弦传感器的激励方法和激励电压

河北稳控科技多功能手持VH501TC采集仪如何设置振弦传感器的激励方法和激励电压 VH501TC 提供多种振弦传感器激励方法,以最大限度兼容所有厂家和型号的振弦传感器。 振弦传感器激励方法参数位于实时数据窗口右侧,共有 5 种方法可选,分别用 MODTH0~MODTH4 表示。各方法说明如下: 激励电压数据在屏幕上显示为 xxx/xxx 的形式,其中前面的数字表示实际的激励电压,后面的数字...

十年技术进阶路,让我明白了三件要事(8000字长文)

前言   【本文于2022-5-10日首发于ITPUB微信公众号平台】   该篇文章是我第一次跟DTCC合作编写的,整篇文章大概8000字,可能花您15分钟阅读。我和DTCC的韩楠老师,共花7了天时间,每天把该文章打磨到晚上12点,在这非常感谢编辑老师的负责与付出。   这篇也是我分享里为数不多“进阶”与“成长经历”的文章之一。被别人送到嘴边的食物永远是最香的,但是咱们还是得学会主动去"如何找吃的...

【大话云原生】微服务篇-五星级酒店的服务方式

文章开始之前,我给大家推荐一个人工智能学习网站,首先说我之前是完全不涉及人工智能领域的,但是我尽然看懂了,以后老哥我就要参与人工智能了。如果你也想学习,点击跳转到网站 《大话云原生》系列文章期望用最通俗、简单的语言说明云原生生态系统内的组成及应用关系。此专栏的前两篇文章 《【大话云原生】煮饺子与docker、kubernetes之间的关系》 《【大话云原生】负载均衡篇-小饭馆的流量变大了》 欢迎...

基于.NetCore开发博客项目 StarBlog - (18) 实现本地Typora文章打包上传

前言 九月太忙,只更新了三篇文章,本来这个功能是从九月初就开始做的,结果一直拖到现在国庆假期才有时间完善并且写文章~ 之前我更新了几篇关于 Python 的文章,有朋友留言问是不是不更新 .Net 了,那肯定不能啊,我只能说「我 全 都 要」,所以我反手就更新了一篇Asp-Net-Core开发笔记。 然后顺便立个Flag:今年底前完成StarBlog系列文章的主体部分(即API开发+后台前端开发,...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。