JavaScript 基础排序的实现(一)
作为一个有追求的前端,忙里偷闲(闲得发慌)地复习了一下基础的排序算法,以此文留念.
本篇主要记录O(n²)复杂度的基础算法O(nlogn)的算法将在下次有空(闲得发慌)时更新
在记录时发现Es6语法中的解构赋值与传统的中间变量交换相比效率低下,经过几次测试发现其耗时大约为交换中间变量的两倍
1.冒泡排序
众所周知排序最基础的算法,也就是大名鼎鼎的冒泡了,为了方便日后回顾还是简单提一下冒泡的原理:
其核心思想在于不停地比较相邻元素的大小关系,如果前面的比后面的大则两个元素互换位置(此处以顺序为例);每当一次大的循环后总能将当前剩余数中最大的数交换到数组的末尾,类似于一个泡泡从底部浮出水面,故得名冒泡算法.下方代码为未使用任何优化的原始冒泡算法.
其时间复杂度为O(n²) 不需要额外空间;
1 //冒泡排序 2 function BubbleSort(arr) {//arr即需要排序的数组;本文后续中的arr均为此意 3 console.time('timer');//用于统计代码执行时间 4 for (let i = 0; i < arr.length; i++) { 5 for (let j = 0; j < arr.length; j++) { 6 if (arr[j] > arr[j + 1]) 7 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];//交换元素(解构赋值ES6) 8 } 9 } 10 console.timeEnd('timer'); 11 }
以一万个数构成的倒序(从大到小)数组变为顺序的时间如下图(与个人电脑及其它因素有关请勿较真)用解构赋值交换:
后续算法的时间均以同一数组测试
2.鸡尾酒排序
这种排序算法乃是对冒泡算法的一种小优化,其与冒泡的区别在于,在一趟排序中可以将一个最大的移到后端,同时将一个最小的移到前端,从而对冒泡算法进行优化
核心代码如下:
//鸡尾酒排序 function CocktailSort(arr) { console.time('timer'); let [start, end] = [0, arr.length]; while (start < end) {
//此循环与正常冒泡一致 for (let i = start; i < end; i++) { if (arr[i] > arr[i + 1]) [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; } end--;//由于数组最后一位已经是最大的所以没有必要再让其参与后续的排序 for (let i = end - 1; i >= start; i--) { if (arr[i] < arr[i - 1]) [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]]; } start++; } console.timeEnd('timer'); }
耗费时间如下
由于其本质与冒泡算法类似,虽然好上些许,但其本质仍为O(n²)的时间复杂度故时间并未得到太大的缩减(由于解构赋值的原因优化后的算法还不如不优化,是真的骚)
3.选择排序
选择排序也是大家所熟知的一种基础算法,其核心在于每一次选出最小(或最大)的一个数放到已经有序的数列后,经过如此重复操作后获得有序的数列
代码如下:
//选择排序 function SelecttionSort(arr) { console.time('timer'); for (let i = 0; i < arr.length; i++) { let min = i;//min表示当前最小值的下标 for (let j = i + 1; j < arr.length; j++) { min = arr[j] < arr[min] ? j : min; //如果当前下标的值比arr[min]的值要小则以当前值替换 } [arr[i], arr[min]] = [arr[min], arr[i]]; } console.timeEnd('timer'); }
花费时间如下:
按理说同为n平方的复杂度时间耗费应该相差不大才对,结果由于交换次数的减少导致耗时大幅下降,感觉Js在这方面效率有点低
4.插入排序
插入排序的原理为将当前下标的数插入之前已经有序的数列中,从后往前遍历找到合适的位置后将值插入,并将该位置之后的元素依次后移从而进行排序
代码如下:
function InsertionSort(arr) { console.time('timer'); for (let i = 1; i < arr.length; i++) { for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) { [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; } } console.timeEnd('timer'); }
同数组耗时如下:
总结:在Js的情况下交换数据应尽量少的使用解构赋值,虽然其便利性很强,但是当网页对性能要求较高时应减少解构赋值的使用,如果非用不可,在同等级时间复杂度算法的情况下应使用数字交换次数少的算法以提升页面性能
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
大神之路你必须了解的——Java 设计模式
一直想写一篇介绍设计模式的文章,让读者可以很快看完,而且一看就懂,看懂就会用,同时不会将各个模式搞混。自认为本文还是写得不错的,花了不少心思来写这文章和做图,力求让读者真的能看着简单同时有所收获。 设计模式是对大家实际工作中写的各种代码进行高层次抽象的总结,其中最出名的当属Gang of Four(GoF) 的分类了,他们将设计模式分类为 23 种经典的模式,根据用途我们又可以分为三大类,分别为创建型模式、结构型模式和行为型模式。是的,我不善于扯这些有的没的,还是少点废话吧~~~ 有一些重要的设计原则在开篇和大家分享下,这些原则将贯通全文: 面向接口编程,而不是面向实现。这个很重要,也是优雅的、可扩展的代码的第一步,这就不需要多说了吧。 职责单一原则。每个类都应该只有一个单一的功能,并且该功能应该由这个类完全封装起来。 对修改关闭,对扩展开放。对修改关闭是说,我们辛辛苦苦加班写出来的代码,该实现的功能和该修复的 bug 都完成了,别人可不能说改就改;对扩展开放就比较好理解了,也就是说在我们写好的代码基础上,很容易实现扩展。 目录 创建型模式 简单工厂模式 工厂模式 抽象工厂模式 单例模...
- 下一篇
Spring Boot 最佳实践(一)快速入门
一、关于Spring Boot 在开始了解Spring Boot之前,我们需要先了解一下Spring,因为Spring Boot的诞生和Spring是息息相关的,Spring Boot是Spring发展到一定程度的一个产物,但并不是Spring的替代品,Spring Boot是为了让程序员更好的使用Spring。说到这里可能有些人会迷糊,那到底Spring和Spring Boot有着什么样的联系呢? 1.Spring发展史 在开始之前我们先了解一下Spring,Spring的前身是interface21,这个框架最初是为了解决EJB开发笨重臃肿的问题,为J2EE提供了另一种简单又实用的解决方案,并在2004年3月发布了Spring 1.0正式版之后,就引起了Java界广泛的关注和热评,从此Spring在Java界势如破竹迅速走红,一路成为Java界一颗璀璨夺目的明星,至今无可替代,也一度成为J2EE开发中真正意义上的标准了,而他的创始人Rod Johnson也在之后声名大噪,名利双收,现在是一名优秀的天使投资人,走上了人生的巅峰。 2.Spring Boot诞生 那既然Spring已经...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8编译安装MySQL8.0.19
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- SpringBoot2整合Redis,开启缓存,提高访问速度
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Hadoop3单机部署,实现最简伪集群
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果