xml地图|网站地图|网站标签 [设为首页] [加入收藏]
Web前端优化最佳实践及工具集锦,十大经典排序
分类:web前端

必看的 JavaScript 视频

2015/10/30 · 基础技术 · 视频

去年 Sergey Bolshchikov 发起了一个倡议,视频列表已挺丰富了。

小提示:

  • 视频均在 Youtube。如有搬运到国内的热心童鞋,请在评论中留言;
  • Clip Converter:Youtube 视频下载工具

十大经典排序算法

2016/09/19 · 基础技术 · 7 评论 · 排序算法, 算法

本文作者: 伯乐在线 - Damonare 。未经作者许可,禁止转载!
欢迎加入伯乐在线 专栏作者。

Web前端优化最佳实践及工具集锦

2015/03/11 · JavaScript · Web开发, 工具

原文出处: CSDN 王果 编译整理   

前端的性能对于一个Web应用来说非常重要,如果一个Web应用的页面加载速度非常快、对于用户的操作可以及时响应,那么产品的用户体验将会极大地提升。下图显示了页面加载速度对于用户体验的影响。

图片 1

你的Web页面的速度是否已经足够快了?其实可能还有很多可以提升的地方。Google和雅虎也提出了一些Web应用的前端优化建议,并发布了一些工具,你可以逐一检验你的Web应用,以便达到更高的性能。

这些优化不仅仅可以给用户提供更好的体验,从开发者角度来说,进行优化还可以减少页面的请求数、降低请求所占的带宽、减少资源的浪费。

下面来看看Google和雅虎提供的Web页面优化最佳实践。

2015

  1. Dr. Axel Rauschmayer: Using ECMAScript 6 today
    • Part 1 [40:44]
    • Part 2 [53:04]
  2. Brendan Eich: ECMAScript Harmony: Rise of the Compilers [19:17]
  3. Andreas Gal: Dirty Performance Secrets of HTML5 | HTML5 性能秘籍 [14:15]
  4. Andre Staltz: What if the user was a function | 假如用户是一个函数? [32:19] ♨

前言

读者自行尝试可以想看源码戳这,博主在github建了个库,读者可以Clone下来本地尝试。此博文配合源码体验更棒哦

  • 这世界上总存在着那么一些看似相似但有完全不同的东西,比如雷锋和雷峰塔,小平和小平头,玛丽和马里奥,Java和javascript….当年javascript为了抱Java大腿恬不知耻的让自己变成了Java的干儿子,哦,不是应该是跪舔,毕竟都跟了Java的姓了。可如今,javascript来了个咸鱼翻身,几乎要统治web领域,Nodejs,React Native的出现使得javascript在后端和移动端都开始占有了一席之地。可以这么说,在Web的江湖,JavaScript可谓风头无两,已经坐上了头把交椅。
  • 在传统的计算机算法和数据结构领域,大多数专业教材和书籍的默认语言都是Java或者C/C+ +,O’REILLY家倒是出了一本叫做《数据结构与算法javascript描述》的书,但不得不说,不知道是作者吃了shit还是译者根本就没校对,满书的小错误,这就像那种无穷无尽的小bug一样,简直就是让人有种嘴里塞满了shit的感觉,吐也不是咽下去也不是。对于一个前端来说,尤其是笔试面试的时候,算法方面考的其实不难(十大排序算法或是和十大排序算法同等难度的),但就是之前没用javascript实现过或是没仔细看过相关算法的原理,导致写起来浪费很多时间。所以撸一撸袖子决定自己查资料自己总结一篇博客等用到了直接看自己的博客就OK了,正所谓靠天靠地靠大牛不如靠自己(ˉ(∞)ˉ)。
  • 算法的由来:9世纪波斯数学家提出的:“al-Khowarizmi”就是下图这货(感觉重要数学元素提出者貌似都戴了顶白帽子),开个玩笑,阿拉伯人对于数学史的贡献还是值得人敬佩的。
    图片 2

一、Google的Web优化最佳实践

1.  避免坏请求

有时页面中的HTML或CSS会向服务器请求一个不存在的资源,比如图片或HTML文件,这会造成浏览器与服务器之间过多的往返请求,类似于:

  • 浏览器:“我需要这个图像。”
  • 服务器:“我没有这个图像。”
  • 浏览器:“你确定吗?这个文档说你有。”
  • 服务器:“真的没有。”

图片 3

如此一来,会降低页面的加载速度。因此,检查页面中的坏链接非常有必要,你可以通过 Google的PageSpeed工具 来检测,找到问题后,补充相应的资源文件或者修改资源的链接地址即可。

2.  避免CSS @import

使用 @import方法引用CSS文件可以能会带来一些影响页面加载速度的问题,比如导致文件按顺序加载(一个加载完后才会加载另一个),而无法并行加载。

你可以使用 CSS delivery工具 来检测页面代码中是否存在@import方法。比如,如果检测结果中存在

CSS

@import url("style.css")

1
@import url("style.css")

则建议你使用下面的代码来替代。

XHTML

<link rel="style.css" href="style.css" type="text/css">

1
<link rel="style.css" href="style.css" type="text/css">

3.  避免使用document.write

在JavaScript中,可以使用 document.write在网页上显示内容或调用外部资源,而通过此方法,浏览器必须采取一些多余的步骤——下载资源、读取资源、运行JavaScript来了解需要做什么,调用其他资源时需要重新再执行一次这个过程。由于浏览器之前不知道要显示什么,所以会降低页面加载的速度。

要知道,任何能够被document.write调用的资源,都可以通过HTML来调用,这样速度会更快。检查你的页面代码,如果存在类似于下面的代码:

JavaScript

document.write('<script src="another.js"></script>');

1
document.write('<script src="another.js"></script>');

建议修改为:

XHTML

<script src="another.js"></script>

1
<script src="another.js"></script>

4.  合并多个外部CSS文件

在网站中每使用一个CSS文件,都会让你的页面加载速度慢一点点。如果你有一个以上的CSS文件,你应该将它们合并为一个文件。

你可以通过  CSS delivery工具 来检测页面代码中的CSS文件,然后通过复制粘贴的方式将它们合并为一个。合并后记得修改页面中的引用代码,并删除旧的引用代码。

图片 4

5.  合并多个外部JavaScript文件

大部分情况下,网站往往会包含若干个 JavaScript文件,但并不需要将这些文件都独立出来,其中有些是可以合并为一个文件的。

你可以通过 resource check工具 来检测页面中所引用的JavaScript文件数,然后可以通过复制粘贴的方式将多个文件合并为一个。

6.  通过CSS sprites来整合图像

如果页面中有6个小图像,那么浏览器在显示时会分别下载。你可以通过CSS sprites将这些图像合并成1个,可以减少页面加载所需的时间。

CSS sprites需要有两个步骤:整合图像、定位图像。比如你可以通过下面的代码来分别定位下面图像中的上下两部分。

CSS

.megaphone {width:50px; height:50px; background:url(images/sprite.png) 0 0px;} .smile {width:50px; height:50px; background:url(images/sprite.png) 0 -50px;}

1
2
.megaphone {width:50px; height:50px; background:url(images/sprite.png) 0 0px;}
.smile {width:50px; height:50px; background:url(images/sprite.png) 0 -50px;}

图片 5

7. 延迟JavaScript的加载

浏览器在执行JavaScript代码时会停止处理页面,当页面中有很多JavaScript文件或代码要加载时,将导致严重的延迟。尽管可以使用defer、异步或将JavaScript代码放到页面底部来延迟JavaScript的加载,但这些都不是一个好的解决方案。

下面是Google的建议。

JavaScript

<script type="text/javascript"> function downloadJSAtOnload() { var element = document.createElement("script"); element.src = "defer.js"; document.body.appendChild(element); } if (window.addEventListener) window.addEventListener("load", downloadJSAtOnload, false); else if (window.attachEvent) window.attachEvent("onload", downloadJSAtOnload); else window.onload = downloadJSAtOnload; </script>

1
2
3
4
5
6
7
8
9
10
11
12
<script type="text/javascript">
function downloadJSAtOnload() {
var element = document.createElement("script");
element.src = "defer.js";
document.body.appendChild(element);
}
if (window.addEventListener)
window.addEventListener("load", downloadJSAtOnload, false);
else if (window.attachEvent)
window.attachEvent("onload", downloadJSAtOnload);
else window.onload = downloadJSAtOnload;
</script>

这段代码的意思是等待页面加载完成后,然后再加载外部的“defer.js”文件。下面是测试结果。

图片 6

8.  启用压缩/ GZIP

使用gzip对HTML和CSS文件进行压缩,通常可以节省大约50%到70%的大小,这样加载页面只需要更少的带宽和更少的时间。

你可以通过这个 Gzip压缩工具 来检测页面是否已经经过Gzip压缩。

9.  启用Keep-Alive

HTTP协议采用“请求-应答”模式,当使用普通模式(非KeepAlive模式)时,每个请求/应答客户和服务器都要新建一个连接,完成之后立即断开连接(HTTP协议为无连接的协议);当使用 Keep-Alive模式(又称持久连接、连接重用)时,Keep-Alive功能使客户端到服务器端的连接持续有效,当出现对服务器的后继请求时,Keep-Alive功能避免了建立或者重新建立连接。

在HTTP 1.0中Keep-Alive默认是关闭的,需要在HTTP头中加入“Connection: Keep-Alive”,才能启用Keep-Alive;在 HTTP1.1中Keep-Alive默认启用,加入“Connection: close”可关闭。目前大部分浏览器都是用HTTP 1.1协议,也就是说默认都会发起Keep-Alive的连接请求了,所以是否能完成一个完整的Keep- Alive连接就看Web服务器的设置情况。

10.  将小的CSS和JavaScript代码内嵌到HTML中

如果你的CSS代码比较小,可以将这部分代码放到HTML文件中,而不是一个外部CSS文件,这样可以减少页面加载所需的文件数,从而加快页面的加载。同样,也可以将小的 JavaScript脚本代码内嵌到HTML文件中。

XHTML

<style type="text/css"> <!--CSS代码--> </style> <script type="text/javascript"> <!--JavaScript代码--> </script>

1
2
3
4
5
6
7
<style type="text/css">
<!--CSS代码-->
</style>
 
<script type="text/javascript">
<!--JavaScript代码-->
</script>

11.  利用浏览器缓存

在显示页面时,浏览器需要加载logo、CSS文件和其他一些资源。浏览器缓存所做的工作就是“记住”已经加载的资源,让页面的加载速度更快。

12.  压缩CSS代码

不管你在页面中如何使用CSS,CSS文件都是越小越好,这会帮助你提升网页的加载速度。你可以通过 Minify CSS工具 来压缩你的CSS代码。

压缩前:

CSS

body { background-color:#d0e4fe; } h1 { color:orange; text-align:center; }

1
2
3
4
5
6
7
8
9
body
{
background-color:#d0e4fe;
}
h1
{
color:orange;
text-align:center;
}

压缩后:

CSS

body {background-color:#d0e4fe;} h1 {color:orange;text-align:center;}

1
2
body {background-color:#d0e4fe;}
h1 {color:orange;text-align:center;}

13.  尽量减少DNS查询次数

当浏览器与Web服务器建立连接时,它需要进行DNS解析,将域名解析为IP地址。然而,一旦客户端需要执行DNS lookup时,等待时间将会取决于域名服务器的有效响应的速度。

虽然所有的ISP的DNS服务器都能缓存域名和IP地址映射表,但如果缓存的DNS记录过期了而需要更新,则可能需要通过遍历多个DNS节点,有时候需要通过全球范围内来找到可信任的域名服务器。一旦域名服务器工作繁忙,请求解析时就需要排队,则进一步延迟等待时间。

因此,减少DNS的查询次数非常重要,页面加载时就尽量避免额外耗时。为了减少DNS查询次数,最好的解决方法就是在页面中减少不同的域名请求的机会。

你可以通过 request checker工具 来检测页面中存在多少请求,然后进行优化。

14.  尽量减少重定向

有时为了特定需求,需要在网页中使用重定向。重定向的意思是,用户的原始请求(例如请求A)被重定向到其他的请求(例如请求B)。

但是这会造成网站性能和速度下降,因为浏览器访问网址是一连串的过程,如果访问到一半而跳到新地址,就会重复发起一连串的过程,这将浪费很多的时间。所以我们要尽量避免重定向,Google建议:

  • 不要链接到一个包含重定向的页面
  • 不要请求包含重定向的资源

15.  优化样式表和脚本的顺序

Style标签和样式表调用代码应该放置在JavaScript代码的前面,这样可以使页面的加载速度加快。

XHTML

<head> <meta name=description content="description"/> <title>title</title> <style> page specific css code goes here </style> <script type="text/javascript"> javascript code goes here </script> </head>

1
2
3
4
5
6
7
8
9
10
<head>
<meta name=description content="description"/>
<title>title</title>
<style>
page specific css code goes here
</style>
<script type="text/javascript">
javascript code goes here
</script>
</head>

16.  避免JavaScripts阻塞渲染

浏览器在遇到一个引入外部JS文件的<script>标签时,会停下所有工作来下载并解析执行它,在这个过程中,页面渲染和用户交互完全被阻塞了。这时页面加载就会停止。

谷歌 建议 删除干扰页面中第一屏内容加载的JavaScript,第一屏是指用户在屏幕中最初看到的页面,无论是桌面浏览器、手机,还是平板电脑。

图片 7

17.  缩小原始图像

如果无需在页面中显示较大的图像,那么就建议将图像的实际大小缩小为显示的大小,这样可以减少下载图像所需的时间。

18.  指定图像尺寸

当浏览器加载页面的HTML代码时,有时候需要在图片下载完成前就对页面布局进行定位。如果HTML里的图片没有指定尺寸(宽和高),或者代码描述的尺寸与实际图片的尺寸不符时,浏览器则要在图片下载完成后再“回溯”该图片并重新显示,这将消耗额外的时间)。

所以,最好为页面中的每一张图片都指定尺寸,不管是在HTML里的<img>标签中,还是在CSS中。

更多信息: 

2014

  1. Ilya Grigorik: Website Performance Optimization | 网站性能优化 (Udacity 课程) [1:13:57]
  2. Mark DiMarco: User Interface Algorithms | 用户接口算法 [27:41]
  3. Neil Green: Writing Custom DSLs [29:07]
  4. Philip Roberts: Help, I’m stuck in an event-loop [20:13]
  5. Eric Bidelman: Polymer and Web Components change everything you know about Web development [36:12]
  6. Alex Russell, Jake Archibald: Bridging the gap between the web and apps [48:40]
  7. Scott Hanselman: Virtual Machines, JavaScript and Assembler [25:56]
  8. Jafar Husain: Async JavaScript with Reactive Extensions [26:38]
  9. John-David Dalton: Unorthodox Performance [43:39]
  10. Gary Bernhardt: The Birth & Death of Javascript [29:22]
  11. Addy Osmani: Memory Management Masterclass [55:06]
  12. Reginald Braithwaite: Invent the future, don’t recreate the past [39:16]
  13. Kyle Simpson: Syncing Async [42:25]
  14. Ariya Hidayat: JavaScript and the Browser: Under the Hood [29:13]
  15. Jafar Husain: Version 7: The Evolution of JavaScript [1:11:53]
  16. David Nolen: Immutability: Putting The Dream Machine To Work [22:05]

正文

二、雅虎的Web优化最佳实践

1.  内容优化

  • 尽量减少HTTP请求:常见方法包括合并多个CSS文件和JavaScript文件,利用CSS Sprites整合图像,Image map(图像中不同的区域设置不同的链接),内联图象(使用  data: URL scheme 在实际的页面嵌入图像数据)等。
  • 减少DNS查找
  • 避免重定向
  • 使Ajax可缓存
  • 延迟加载组件:考虑哪些内容是页面呈现时所必需首先加载的、哪些内容和结构可以稍后再加载,根据这个优先级进行设定。
  • 预加载组件:预加载是在浏览器空闲时请求将来可能会用到的页面内容(如图像、样式表和脚本)。当用户要访问下一个页面时,页面中的内容大部分已经加载到缓存中了,因此可以大大改善访问速度。
  • 减少DOM元素数量:页面中存在大量DOM 元素,会导致JavaScript遍历DOM的效率变慢。
  • 根据域名划分页面内容:把页面内容划分成若干部分可以使你最大限度地实现平行下载。但要确保你使用的域名数量在2个到4个之间(否则与第2条冲突)。
  • 最小化iframe的数量:iframes 提供了一个简单的方式把一个网站的内容嵌入到另一个网站中。但其创建速度比其他包括JavaScript和CSS的DOM元素的创建慢了1-2个数量级。
  • 避免404:HTTP请求时间消耗是很大的,因此使用HTTP请求来获得一个没有用处的响应(例如404没有找到页面)是完全没有必要的,它只会降低用户体验而不会有一点好处。

2. 服务器优化

  • 使用内容分发网络(CDN):把你的网站内容分散到多个、处于不同地域位置的服务器上可以加快下载速度。
  • 添加Expires或Cache-Control信息头:对于静态内容,可设置文件头过期时间Expires的值为“Never expire(永不过期)”;对于动态内容,可使用恰当的Cache-Control文件头来帮助浏览器进行有条件的请求。
  • Gzip压缩
  • 设置ETag:ETags(Entity tags,实体标签)是web服务器和浏览器用于判断浏览器缓存中的内容和服务器中的原始内容是否匹配的一种机制。
  • 提前刷新缓冲区:当用户请求一个页面时,服务器会花费200到500毫秒用于后台组织HTML文件。在这期间,浏览器会一直空闲等待数据返回。在PHP中,可以使用flush()方法,它允许你把已经编译的好的部分HTML响应文件先发送给浏览器,这时浏览器就会可以下载文件中的内容(脚本等)而后台同时处理剩余的HTML页面。
  • 对Ajax请求使用GET方法:当使用XMLHttpRequest时,浏览器中的POST方法会首先发送文件头,然后才发送数据。因此使用GET最为恰当。
  • 避免空的图像src

3. Cookie优化

  • 减小cookie大小:去除不必要的coockie,并使coockie体积尽量小以减少对用户响应的影响
  • 针对Web组件使用域名无关的Cookie:对静态组件的Cookie读取是一种浪费,使用另一个无Cookie的域名来存放静态组件是一个好方法,或者也可以在Cookie中只存放带www的域名。

4. CSS优化

  • 将CSS代码放在HTML页面的顶部
  • 避免使用CSS表达式:CSS表达式在执行时候的运算量非常大,会对页面性能产生大的影响
  • 使用<link>来代替@import
  • 避免使用Filters:IE独有属性AlphaImageLoader用于修正IE 7以下版本中PNG图片的半透明效果,但它的问题在于浏览器加载图片时它会终止内容的呈现并且冻结浏览器。

5. JavaScript优化

  • 将JavaScript脚本放在页面的底部
  • 将JavaScript和CSS作为外部文件来引用:在实际应用中使用外部文件可以提高页面速度,因为JavaScript和CSS文件都能在浏览器中产生缓存。
  • 缩小JavaScript和CSS
  • 删除重复的脚本
  • 最小化DOM的访问:使用JavaScript访问DOM元素比较慢
  • 开发智能的事件处理程序

6. 图像优化

  • 优化图片大小
  • 通过CSS Sprites优化图片
  • 不要在HTML中使用缩放图片
  • favicon.ico要小而且可缓存

7. 针对移动优化

  • 保持组件大小在25KB以下:主要是因为iPhone不能缓存大于25K的文件(注意这里指的是解压缩后的大小)。
  • 将组件打包成为一个复合文档:把页面内容打包成复合文本就如同带有多附件的Email,它能够使你在一个HTTP请求中获取多个组件。

更多信息:(中文翻译)

2013

  1. Nat Duca, Tom Wiltzius: Jank Free: Chrome Rendering Performance [40:53]
  2. Ilya Grigorik: Automating Performance Best Practices with PageSpeed [46:58]
  3. Eric Bidelman: Web Components [32:39]
  4. Alex Komoroske, Matthew McNulty: Web Components in Action [41:28]
  5. Paul Lewis, Peter Beverloo: Device Agnostic Development [40:44]
  6. John McCutchan, Loreena Lee: A Trip Down Memory Lane with Gmail and DevTools [42:09]
  7. Joe Marini: Upgrading to a Chrome Packaged App [43:49]
  8. Pete Hunt: React: Rethinking best practices [29:31]
  9. Martin Kleppe: 1024+ Seconds of JS Wizardry [31:01]
  10. Yehuda Katz: A tale of two MVC’s [31:06]
  11. Vyacheslav Egorov: Performance and Benchmarking [25:41]
  12. Brendan Eich: JavaScript at 18: Legal to Gamble [25:44]
  13. Mathias Bynens: JavaScript ♥ Unicode [26:12]
  14. Mark Trostler: Testable JavaScript – Architecting Your Application for Testability [45:35]

排序算法说明

(1)排序的定义:对一序列对象根据某个关键字进行排序;

输入:n个数:a1,a2,a3,…,an
输出:n个数的排列:a1’,a2’,a3’,…,an’,使得a1’

再讲的形象点就是排排坐,调座位,高的站在后面,矮的站在前面咯。

(3)对于评述算法优劣术语的说明

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;

内排序:所有排序操作都在内存中完成;
外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

时间复杂度: 一个算法执行所耗费的时间。
空间复杂度: 运行完一个程序所需内存的大小。

关于时间空间复杂度的更多了解请戳这里,或是看书程杰大大编写的《大话数据结构》还是很赞的,通俗易懂。

(4)排序算法图片总结(图片来源于网络):

排序对比:

图片 8

图片名词解释:
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存,不占用额外内存
Out-place: 占用额外内存

排序分类:

图片 9

三、一些工具

1.  Google PageSpeed

Google提供了 PageSpeed工具,这是一个浏览器插件,可以很好地应用上文中Google所提到的Web优化实践——帮助你轻松对网站的性能瓶颈进行分析,并为你提供优化建议。

  • 在线分析你的网站
  • 安装浏览器插件( Chrome、 Firefox)
  • 通过 Insights API在应用中嵌入PageSpeed功能

2.  雅虎 YSlow

YSlow是雅虎推出的一款浏览器插件,可以帮助你对网站的页面进行分析,并为你提供一些优化建议,以提高网站的性能。

  • Firefox插件
  • Chrome插件
  • YSlow for Mobile/Bookmarklet
  • 源码

3. 其他分析优化工具

  • 蜘蛛模拟器:这个工具可以分析你的页面,并提供一些优化建议。
  • 图像SEO工具:这个工具可以检查图片的alt标签,并提供一些优化建议。
  • 请求检查器:找出页面中需要加载哪些资源和服务。
  • 链接检查器:检查页面中内部、外部和无效链接。
  • HTTP头检查:显示网页或资源的HTTP响应头。
  • 社交检查器:检查页面中的社交组件,比如Google+、Facebook、Twitter、Linkedin和Pinterest。
  • If modified检查器:检查页面是否接受 If-Modified-Since HTTP头。
  • Gzip检查器:检查页面是否经过了Gzip压缩。
  • CSS delivery工具:检查页面中所使用的CSS文件。
  • 面包屑工具:可根据你输入的信息提供面包屑导航的代码。
  • CSS压缩工具:用于压缩CSS代码。

通过以上的优化建议和优化工具,可以轻松找到影响你的Web页面性能的瓶颈,轻松实现Web页面性能的提升。如果你也有Web优化方面的经验,欢迎分享。

赞 3 收藏 评论

图片 10

2012

  1. Ryan Sandor Richards: Garbage Collection & Heap Management [32:57]
  2. Addy Osmani: Scaling Your JavaScript Applications
    • Part 1 [22:38]
    • Part 2 [15:41]
    • Part 3 [33:32]
  3. John-David Dalton: Lo-Dash [25:08]
  4. Gary Bernhardt: WAT [4:17]
  5. Angus Croll: Break all the rules [31:29]
  6. Nicholas Zakas: Maintainable JavaScript [47:04]
  7. Douglas Crockford: Principles of Security [59:52]

1.冒泡排序(Bubble Sort)

好的,开始总结第一个排序算法,冒泡排序。我想对于它每个学过C语言的都会了解的吧,这可能是很多人接触的第一个排序算法。

2011

  1. Douglas Crockford: Level 7: ECMAScript 5: The New Parts [57:18]
    图片 11
  2. Douglas Crockford: Section 8: Programming Style and Your Brain [1:06:45]
  3. Ryan Dahl: Introduction to Node.js [1:06:33]
  4. Alex Russell: Learning to Love JavaScript [1:03:25]

(1)算法描述

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2010

  1. Douglas Crockford: Volume One: The Early Years [1:42:08]
  2. Douglas Crockford: Chapter 2: And Then There Was JavaScript [1:30:22]
  3. Douglas Crockford: Act III: Function the Ultimate [1:13:28]
  4. Douglas Crockford: Episode IV: The Metamorphosis of Ajax [1:33:54]
  5. Douglas Crockford: Part 5: The End of All Things [1:24:42]
  6. Douglas Crockford: Scene 6: Loopage [51:52]

(2)算法描述和实现

具体算法描述如下:

  • <1>.比较相邻的元素。如果第一个比第二个大,就交换它们两个;
  • <2>.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
  • <3>.针对所有的元素重复以上的步骤,除了最后一个;
  • <4>.重复步骤1~3,直到排序完成。

JavaScript代码实现:

JavaScript

function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len; i++) { for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { //相邻元素两两对比 var temp = arr[j+1]; //元素交换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                var temp = arr[j+1];        //元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

 

改进冒泡排序: 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

JavaScript

function bubbleSort2(arr) { console.time('改进后冒泡排序耗时'); var i = arr.length-1; //初始时,最后位置保持不变 while ( i> 0) { var pos= 0; //每趟开始时,无记录交换 for (var j= 0; j< i; j++) if (arr[j]> arr[j+1]) { pos= j; //记录交换的位置 var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp; } i= pos; //为下一趟排序作准备 } console.timeEnd('改进后冒泡排序耗时'); return arr; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSort2(arr) {
    console.time('改进后冒泡排序耗时');
    var i = arr.length-1;  //初始时,最后位置保持不变
    while ( i> 0) {
        var pos= 0; //每趟开始时,无记录交换
        for (var j= 0; j< i; j++)
            if (arr[j]> arr[j+1]) {
                pos= j; //记录交换的位置
                var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
            }
        i= pos; //为下一趟排序作准备
     }
     console.timeEnd('改进后冒泡排序耗时');
     return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

 

传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

改进后的算法实现为:

JavaScript

function bubbleSort3(arr3) { var low = 0; var high= arr.length-1; //设置变量的初始值 var tmp,j; console.time('2.改进后冒泡排序耗时'); while (low < high) { for (j= low; j< high; ++j) //正向冒泡,找到最大者 if (arr[j]> arr[j+1]) { tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp; } --high; //修改high值, 前移一位 for (j=high; j>low; --j) //反向冒泡,找到最小者 if (arr[j]<arr[j-1]) { tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp; } ++low; //修改low值,后移一位 } console.timeEnd('2.改进后冒泡排序耗时'); return arr3; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(bubbleSort3(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function bubbleSort3(arr3) {
    var low = 0;
    var high= arr.length-1; //设置变量的初始值
    var tmp,j;
    console.time('2.改进后冒泡排序耗时');
    while (low < high) {
        for (j= low; j< high; ++j) //正向冒泡,找到最大者
            if (arr[j]> arr[j+1]) {
                tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
            }
        --high;                 //修改high值, 前移一位
        for (j=high; j>low; --j) //反向冒泡,找到最小者
            if (arr[j]<arr[j-1]) {
                tmp = arr[j]; arr[j]=arr[j-1];arr[j-1]=tmp;
            }
        ++low;                  //修改low值,后移一位
    }
    console.timeEnd('2.改进后冒泡排序耗时');
    return arr3;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort3(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

三种方法耗时对比:

图片 12

由图可以看出改进后的冒泡排序明显的时间复杂度更低,耗时更短了。读者自行尝试可以戳这,博主在github建了个库,读者可以Clone下来本地尝试。此博文配合源码体验更棒哦~~~

冒泡排序动图演示:

图片 13

(3)算法分析

  • 最佳情况:T(n) = O(n)

当输入的数据已经是正序时(都已经是正序了,为毛何必还排序呢….)

  • 最差情况:T(n) = O(n2)

当输入的数据是反序时(卧槽,我直接反序不就完了….)

  • 平均情况:T(n) = O(n2)

2009

  1. Nicholas Zakas: Scalable JavaScript Application Architecture [52:22]
  2. Douglas Crockford: JavaScript: The Good Parts [1:03:47]

    1 赞 4 收藏 评论

图片 14

2.选择排序(Selection Sort)

表现最稳定的排序算法之一(这个稳定不是指算法层面上的稳定哈,相信聪明的你能明白我说的意思2333),因为无论什么数据进去都是O(n²)的时间复杂度…..所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

(1)算法简介

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

(2)算法描述和实现

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

  • <1>.初始状态:无序区为R[1..n],有序区为空;
  • <2>.第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  • <3>.n-1趟结束,数组有序化了。

Javascript代码实现:

JavaScript

function selectionSort(arr) { var len = arr.length; var minIndex, temp; console.time('选择排序耗时'); for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { //寻找最小的数 minIndex = j; //将最小数的索引保存 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } console.timeEnd('选择排序耗时'); return arr; } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    console.time('选择排序耗时');
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     //寻找最小的数
                minIndex = j;                 //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    console.timeEnd('选择排序耗时');
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

选择排序动图演示:

图片 15

(3)算法分析

  • 最佳情况:T(n) = O(n2)
  • 最差情况:T(n) = O(n2)
  • 平均情况:T(n) = O(n2)

3.插入排序(Insertion Sort)

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。当然,如果你说你打扑克牌摸牌的时候从来不按牌的大小整理牌,那估计这辈子你对插入排序的算法都不会产生任何兴趣了…..

(1)算法简介

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

(2)算法描述和实现

一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

  • <1>.从第一个元素开始,该元素可以认为已经被排序;
  • <2>.取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • <3>.如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • <4>.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • <5>.将新元素插入到该位置后;
  • <6>.重复步骤2~5。

Javascript代码实现:

JavaScript

function insertionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { console.time('插入排序耗时:'); for (var i = 1; i < array.length; i++) { var key = array[i]; var j = i - 1; while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j--; } array[j + 1] = key; } console.timeEnd('插入排序耗时:'); return array; } else { return 'array is not an Array!'; } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function insertionSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
        console.time('插入排序耗时:');
        for (var i = 1; i < array.length; i++) {
            var key = array[i];
            var j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
        console.timeEnd('插入排序耗时:');
        return array;
    } else {
        return 'array is not an Array!';
    }
}

改进插入排序: 查找插入位置时使用二分查找的方式

JavaScript

function binaryInsertionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { console.time('二分插入排序耗时:'); for (var i = 1; i < array.length; i++) { var key = array[i], left = 0, right = i - 1; while (left <= right) { var middle = parseInt((left + right) / 2); if (key < array[middle]) { right = middle - 1; } else { left = middle + 1; } } for (var j = i - 1; j >= left; j--) { array[j + 1] = array[j]; } array[left] = key; } console.timeEnd('二分插入排序耗时:'); return array; } else { return 'array is not an Array!'; } } var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]; console.log(binaryInsertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function binaryInsertionSort(array) {
    if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
        console.time('二分插入排序耗时:');
        for (var i = 1; i < array.length; i++) {
            var key = array[i], left = 0, right = i - 1;
            while (left <= right) {
                var middle = parseInt((left + right) / 2);
                if (key < array[middle]) {
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
            for (var j = i - 1; j >= left; j--) {
                array[j + 1] = array[j];
            }
            array[left] = key;
        }
        console.timeEnd('二分插入排序耗时:');
        return array;
    } else {
        return 'array is not an Array!';
    }
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(binaryInsertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

改进前后对比:

图片 16

插入排序动图演示:

图片 17

(3)算法分析

  • 最佳情况:输入数组按升序排列。T(n) = O(n)
  • 最坏情况:输入数组按降序排列。T(n) = O(n2)
  • 平均情况:T(n) = O(n2)

4.希尔排序(Shell Sort)

1959年Shell发明;
第一个突破O(n^2)的排序算法;是简单插入排序的改进版;它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

本文由澳门新葡亰手机版发布于web前端,转载请注明出处:Web前端优化最佳实践及工具集锦,十大经典排序

上一篇:没有了 下一篇:没有了
猜你喜欢
热门排行
精彩图文