开垦者才记得这个,Web品质优化连串

Web性能优化系列 – 通过提前获取DNS来提升网页加载速度

2015/04/23 · HTML5 · DNS, 性能优化

本文由 伯乐在线 - 刘健超-J.c 翻译,sunbiaobiao 校稿。未经许可,禁止转载!
英文出处:www.deanhume.com。欢迎加入翻译组。

我时常寻找方法改善网站性能,为的就是能提供更佳的用户体验。也许你经常会发现你的网站运行高效且性能优异。你也可能曾让你的应用程序在Google PageSpeed或Yahoo! YSlow进行测试,并得到高分。然而,有一样东西一直影响页面加载时间。它在一个页面上,花费很多时间去查找不同组件的DNS。例如,下面这幅图片展示了我的博客首页所需资源的加载瀑布图。

图片 1

请注意条形图的灰蓝色部分,它出现在瀑布图中的大部分组件前。这灰蓝色代表下载资源前查找DNS所需时间。这竟然占了组件下载时间的很大部分!即使组件进行了优化,并已经最小化/合并/压缩处理,你仍然需要等待查找DNS时间。我利用webpagetest.org做了一个关于该网站DNS查找时间的表格。

图片 2

从上图可看到,DNS查找时间都很高, 如果能减少该时间并提速,便会让资源加载变得更加高效。幸运的是,有个很棒的技巧能让网站的加载时间变得更快。它被称为DNS预取,并且很容易实现。你所需做的是,在网页顶部添加以下属性作为链接(link)。

<link rel="dns-prefetch" href="//host_name_to_prefetch.com">

DNS预取是在用户尝试点击链接前试图解析域名。一旦域名被解析,且用户导航到该域名,则不会因DNS查找而导致加载时间变长。在这个博客主页里,有很多跳转到不同帖子的链接。如果能在用户导航到下一个页面前,预取一些外部链接的DNS,这将会大大减少下一个页面的DNS查找时间。根据Chromium documentation所说,如果用户能将域名解析成IP地址并且缓存之,则DNS查找时间能低至0-1毫秒(千分之一秒)。这是相当令人印象深刻的!

我在网站添加DNS预取功能后,确实能显著改善页面加载时间。目前,这项技术被大多数主流浏览器所支持(除了IE),所以,当前没有任何理由不在你的web应用上使用这项技术!DNS预取是一个安全的HTML5特性,它会被那些不支持该技术的老旧浏览器简单忽略掉。如果你的网页内容是来自多个域名,那么这绝对是一个聪明的,能加快页面加载速度的方法。

打赏支持我翻译更多好文章,谢谢!

打赏译者

十大经典排序算法

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

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

只有 90 年代的 Web 开发者才记得这些

2016/04/26 · 基础技术 · 2 评论 · WEB

本文由 伯乐在线 - dcscodelife 翻译,艾凌风 校稿。未经许可,禁止转载!
英文出处:holman。欢迎加入翻译组。

你曾经强行把 <blink> 标签放入 <marquee> 标签吗?如今皮克斯动画工作室获得了所有荣誉,但是在 90 年代这个做法则是电脑动画的伟大创举。通过组合两种标签,你成为了一个先驱者。一个创意无限的人。一个令所有人都崇拜的人。

在 90 年代,你曾经是一个网页开发者。

在当时,你知道自己是一个出色的人物。伴随你而来的是极其大量的技术创新,从那时候开始,我们还没来得及做出喜好,技术就已经开始复制开来了。

让我们先放下 jQuery,抛开非关系型数据库不谈:我们有更重要的事情要讨论。

打赏支持我翻译更多好文章,谢谢!

任选一种支付方式

图片 3 图片 4

赞 1 收藏 评论

前言

读者自行尝试可以想看源码戳这,博主在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”就是下图这货(感觉重要数学元素提出者貌似都戴了顶白帽子),开个玩笑,阿拉伯人对于数学史的贡献还是值得人敬佩的。
    图片 5

1×1.gif

1×1.gif 应该获得伟大的格莱美大奖。或者普利策新闻奖。或者类似三年级体育课上颁发的最佳进步奖。除了链式链表,它是计算机科学史上最重要的成就。它不是我们应得的未来,而是我们需要的未来(直到盒子模型彻底取代了它)。

如果你还没不熟悉我们的 1×1.gif 小把戏,请看下面:

图片 6

你能看到它吗,让我们放大一些:

图片 7

The 1×1.gif

这个 1×1.gif – 或者 spacer.gif,或者 transparent.gif – 仅仅是一个长宽都是一个像素的透明 GIF 图像。

JavaScript

<IMG SRC="/1x1.gif" WIDTH=150 HEIGHT=250>

1
<IMG SRC="/1x1.gif" WIDTH=150 HEIGHT=250>

通过上面的代码,你可以把元素放置在页面的任何位置上。

JavaScript

<TABLE> <TR> <TD><IMG SRC="1x1.gif" WIDTH=300> <TD><FONT SIZE=42>Hello welcome to my <MARQUEE>Internet Web Home</MARQUEE></FONT> </TR> <TR> <TD BGCOLOR=RED><IMG SRC="/cgi/webcounter.cgi"> </TR> </TABLE>

1
2
3
4
5
6
7
8
9
<TABLE>
  <TR>
    <TD><IMG SRC="1x1.gif" WIDTH=300>
    <TD><FONT SIZE=42>Hello welcome to my <MARQUEE>Internet Web Home</MARQUEE></FONT>
  </TR>
  <TR>
    <TD BGCOLOR=RED><IMG SRC="/cgi/webcounter.cgi">
  </TR>
</TABLE>

1×1.gif 让你毫不费力地在页面的任何位放置元素。直到今天为止,它仍然是唯一的垂直居中元素的方法。

JavaScript

          

1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

图片对于你而言是不是太高级了?《HTML For Dummies》是不是直到第四章才介绍 <IMG> 标签?现在好了,你是幸运的:&nbsp; 标签来了!

你可以对自己说,“我知道所有 HTML 实体编码。这个弱不禁风的帅哥来这里干嘛的?”

听着,我亲爱的聪明的迷人的读者朋友,这是一个如今的年轻人没有给予足够尊重的创新:不断重复 &nbsp;。很像 1×1.gif 的小把戏,你能任意地扩展 &nbsp; 并用在任何你需要的地方:

JavaScript

PLEASE SIGN <BR>       MY GUESTBOOK BELOW: <HR><HR>

1
2
3
PLEASE SIGN  <BR>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;MY GUESTBOOK BELOW:
<HR><HR>

在 90 年代,如果我每写下一个 &nbsp; 就得到五美分,我就会有足够的钱支付来自美国在线的每月超支账单了。

关于作者:刘健超-J.c

图片 8

前端,在路上... 个人主页 · 我的文章 · 19 ·     

图片 9

正文

点下划线,边界效应

在 HTML 快走到他的黄金时代的尾巴时,CSS 登场了,它带来了一个内容和样式分离的世界,从此我们也开始不停地处理灾难。

首当其冲地当然是用 CSS 来删除链接的下划线效果。一夜之间,整个因特网都陷入了这个方法所带来的泥泞之中,文本看起来像链接,链接看起来像文本。你不知道点哪里,但是黑暗并没有持续多久,因为我们发明了光标效果(你还没有活到你的鼠标有十二个火球尾巴的时候)。

高级技术的应用是如此引人注目,以至于几乎我们所有人都从一开始就使用 CSS。我甚至在 2000 年的一份 index.shtml(对,就是 SSI)文档中发现了证据:

JavaScript

<style type="text/css"> <!-- a:hover {text-decoration: none; color: #000000} --> </style>

1
2
3
4
5
<style type="text/css">
<!--
a:hover {text-decoration: none; color: #000000}
-->
</style>

就是它了!当然,这是 CSS 的内嵌样式。这个样式使你的鼠标滑过链接时,删除链接的下划线并且链接的文字变黑。从此,交互式网站诞生了。

排序算法说明

(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)排序算法图片总结(图片来源于网络):

排序对比:

图片 10

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

排序分类:

图片 11

DHTML 动态超文本标记语言

就在我们拥有了删除链接下划线的技术后,我们决定把它和一个强大功能结合起来,这个功能就是在页面加载的时候弹出一个消息框 alert("Welcome to my website!")。组合 CSS 和 JavaScript 的二者力量,我们得到了一个技术怪兽:DHTML。

DHTML,表示“分布式 HTML”,这是网页开发工具的最高成就。它将经受住时间的考验,它可以使我们实现很多效果,比如雪花从页面顶部飘落下来,或者创建可折叠的菜单,动态的图片地图,又或者除了使用语义标签 <div>,我们还可以自定义 <marquee> 标签。

DHTML 帮助 Web 开发从业余爱好发展到一个成熟的专业领域。类似 Dynamic Drive 这样的网站使你可以仅仅通过复制粘贴一个 50 行的代码块,就可以解决任何问题,而不需要自己再思考创新的解决方法。实际上, DHTML 就是那个年代的 Twitter Bootstrap 框架。

1.冒泡排序(Bubble Sort)

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

像素字体

那个年代的电脑屏幕不是很大。我的意思是,虽然自从阴极射线管显示器 CRT 诞生后,显示器的尺寸的确很大,但是它们的分辨率不高。因此,为了充分利用像素,我们必须用 6 个像素点来表示任意字符。

图片 12

从字里行间我们可以看出,当面对着这些简单的不能再简单的字体,并且当意识到这些字体都是由像素构成的时候,Web 开发者们会渴望成为一个漫画家。所以你会在启动画面上看到那些奇怪的等距像素插图,这些开发者的时间和金钱如果投到那些新上市的互联网公司会产生更多的价值,而不是浪费在安装 Photoshop 软件上。

(1)算法描述

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

按钮

我相信人们之所以讨厌IE浏览器,都是因为IE浏览器抛弃了当初那种最纯粹的样子

IE 4.0 是浏览器的完美化身。它拥有动态桌面。拥有通道 Channels。对,就是伟大的通道,这是最酷的技术,之前从来没有在市场上被使用过,一点都没有。总的来说,IE 4 太优秀了,无论你是否喜欢它,你都应该把它装到你的电脑上。

当你属于精英团体时,你深刻理解完美的价值,你有一种与生俱来的冲动,你想告诉每一个你遇到的人你的决定。你,也唯独只有你有必要庄严地做一个伟大的决定。比如决定你的客户使用什么浏览器浏览你的网站。

图片 13

这些按钮随处可见。就像军官衣服上的绶带:向人们宣告着他们为了如今的荣耀,曾经是如何努力战斗的故事。换句话说,无论你用哪一个编辑器(当然是 FrontPage 98),无论你的 Web 服务器是什么(傻瓜,当然是 GeoCities),无论是 Web 环的哪个部分(这个按钮无论如何都将提高你的网站排名)

我怀念这段美好的时光。如今我们在 Javascript上进行抽象,在抽象之上又进行抽象。我们甚至都不知道如何准确地进行计算。每当想起我们如何走到今天这一步,都令人十分吃惊。

让我们自豪地举起酒杯,帮我们一个忙:复制一堆 &nbsp; 到你的下一个代码提交中,让你的团队成员大吃一惊吧。

1 赞 收藏 2 评论

(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]

三种方法耗时对比:

图片 14

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

冒泡排序动图演示:

图片 15

(3)算法分析

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

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

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

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

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

关于作者:dcscodelife

图片 16

简介还没来得及写 :) 个人主页 · 我的文章 · 10 ·  

图片 17

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]

选择排序动图演示:

图片 18

(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]

改进前后对比:

图片 19

插入排序动图演示:

图片 20

(3)算法分析

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

4.希尔排序(Shell Sort)

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

本文由澳门新葡亰平台官网发布于web前端,转载请注明出处:开垦者才记得这个,Web品质优化连串

TAG标签:
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。