做靠谱交互动画的,十大经典排序算法

在Email中防御性地使用HTML5和CSS3的指南

2015/04/20 · CSS,
HTML5 · 1
评论 ·
Email

本文由 伯乐在线 –
fzr
翻译,黄利民
校稿。未经许可,禁止转载!
英文出处:litmus.com。欢迎加入翻译组。

“在Email中不能使用HTML5或CSS3”。

由于它们“有限”的支持,这已成为邮件设计行业的一个普遍共识。然而,我们现在可以说它是一个完全荒唐的说法。

尽管支持还不是十分通用的,但许多主流电邮客户端已经可以支持HTML5和CSS3了。实际上,电邮总体市场的50%都支持HTML5和CSS。前五大电邮客户端中也有3家开始支持它们了。对于特定顾客,可支持的内容可能会更多。

但是,那些还不能支持这些高级功能的客户端会怎么样呢?你的邮件在这样的订阅者的邮箱中该如何展示?当这些涉及到邮箱,就归结为一个:为订阅者提供非凡的体验。然而,这也不意味着你的邮件必须在每一家客户端中都显示的一样——只需要让你的所有订阅者都能易得易取。

我喜欢的两位邮件设计师——Jonathan Kim 和 Brian
Graves——就十分强调使用不同的方法实现:防御性邮件设计和渐进式增强。

防御性邮箱设计

大概两年前, Jonathan
Kim在我们的 Mobile
Master 作品展上提出了“Pushing the Limits of
Email”的概念。在谈话中,Jonathan发明了一个新词来说明当前的电邮设计状态,即防御性邮件设计。

他解释说,由于一些邮箱客户端对CSS的支持有限,使得邮件设计者们陷入了陈旧的设计状态。他倡导邮件设计者们优先为那些支持网络渲染引擎的客户端设计,进而推动邮件设计行业发展。

渐进式增强

以此类推,在2014年的邮箱设计大会上,DEG的UI设计师,
Brian
Graves,,提出了“赢得在每个屏幕上设计的战斗”。他的谈话的重点在于渐进式增强,关于在支持的环境上提供高级功能。他也强调了优雅降级的重要性。优雅降级意味着,即使订阅者的邮箱客户端不能支持某项特定功能,你也要能为他们提供愉悦的用户体验。

对获得Brian的完整展示感兴趣?幻灯片和录像现在都有提供了。

自动楼梯就是实际生活中一个渐进式增强和优雅降级的完美例子。已故喜剧演员Mitch
Hedberg开玩笑说,“自动扶梯永远不会出故障:因为它可以只是一个楼梯。你应该永远也不会看到‘自动扶梯暂时故障’的标牌,只是‘自动扶梯暂时为楼梯’,不利于方便。”不论环境如何,自动扶梯都能保持自己的功能。

为HTML5和CSS3实现渐进式增强

使用渐进式增强是解决邮件设计的最有效方式。我们都知道的是,在邮箱中使用传统的HTML5和CSS3会在不同客户端之间引起许多渲染问题。向后的兼容性非常不一致——一些HTML和CSS有稳固的向后兼容性而其他的却并没有。对此,不同的客户端采用了不同选择。使用标准的HTML5和CSS3需要更多的测试,而且会影响开发速度。所以,到底什么才是在邮箱中实现渐进式增强的最好方法?

在电邮中使用HTML5和CSS3不必太困难。它不要求在古怪的邮箱客户端上浪费大量时间排除故障(说的就是Outlook邮箱)。它所需要做的就是用一个合适的框架来快速执行HTML5和CSS3而不用烦恼和担心产生渲染问题。而且,非常幸运的是,我们有那样的框架。

下面就是邮件设计者们和开发者们提供的一行重要的代码:

XHTML

@media screen and (-webkit-min-device-pixel-ratio:0) { /* Insert styles
here */ }

1
2
3
@media screen and (-webkit-min-device-pixel-ratio:0) {
  /* Insert styles here */
}

这个媒体查询只针对支持WebKit的邮箱客户端——对HTML5和CSS3有难以置信的支持度。这个媒体查询允许你使用现代技术例如HTML5视频、CSS3动画、web字体以及更多。

这个方法也将现代邮件客户端和旧式客户端的邮箱开发分为两部分。你可以在使用Safari或Chrome浏览器为支持WebKit的客户端测试开发现代技术的同时,使用Firefox为旧式浏览器提供诸如外观之类的基本体验。

这样解决电邮开发问题可以将更多的质量控制过程转移到浏览器方面而不是电邮客户端。这给予邮件设计者以更多的权力,控制力,和自信去开发一个能在所有邮箱客户端之间优雅渲染的电邮。

下载这些Litmus测试结果,显示了就媒体查询对WebKit的支持。值得注意的是,Gmail——既是一个web邮箱客户端,也是一个移动App——并不支持媒体查询,所以这些测试对那些屏幕截图无效。

你也可以针对Gecko(Firefox)渲染这个媒体查询:

XHTML

@-moz-document url-prefix() { /* Insert styles here */ }

1
2
3
@-moz-document url-prefix() {
  /* Insert styles here */
}

很少有客户端使用Gecko(Firefox)作为渲染引擎,这也是为什么最好就支持WebKit的邮箱提供你的增强版。但是,使用媒体查询为WebKit渲染引擎添加同样的功能就简单的多了,对Thunderbird之类的客户端而言。

除了这个方法,还有其他在电邮中实现HTML5和CSS3的方法吗?有。但我们相信这个方法是开发的最迅速的方法——也是最安全的。它缩小了为特殊邮箱客户端开发外观之类需要的工作量,而且集中于基于浏览器的测试。

总结:渐进式增强的建议

了解你的受众

订阅者在哪里打开你的邮件?他们会使用对HTML和CSS支持的很好的如iPhone和AppleMail之类的客户端吗?你可以使用Litmus’
Email
Analytics测试工具检测出订阅者中最流行的邮箱App。

基于所获得的信息,你可以决定是否渐进式增强会对你的工作有帮助。例如,如果你的受众中绝大部分使用WebKit,能够很好的支持高级功能,那么可能尝试创新性的技术,比如HTML5
视频,会是一个不错的想法!

建立一个基本体验

用对HTML和CSS支持有限的邮箱App——如Outlook和Gmail,在你为其他客户端优化邮件之前,为订阅者建立一个基本体验。渐进式增强不应该让其他用户产生次优体验。

尽可能优化

一旦你已经建立一个基本体验,就开始为其他用户优化体验。你可以使用CSS3,视频,交互,可缩放向量图形(SVG),以及web字体。记住,即使是对HTML和CSS支持的比较好的Email客户端也有它们各自的特殊之处,仍然需要测试哪些才是可行的。

实战:邮件中的渐进增强例子

我们先看看一些在邮件中使用渐进式增强的开创性例子。为了展示对这些邮件的优化,你必须使用一个如Chrome或Safari一样以WebKit为动力的浏览器。

2014邮件设计大会以HTML5视频为背景的邮件

为了播报2014邮件设计大会,我们决定认真地以HTML5视频为背景实现渐进式增强。尽管这种专项技术只能在Apple邮箱和Outlook
2011(Mac版)上工作,但这两种客户端达到接收特定邮件的用户40%左右。

View the full email here

对于不支持视频的电邮客户端,HTML5视频仅仅只是退化为一张静态背景图片。我们的结果却是令人惊奇的——而且回报也是惊人的!

B&Q 交互式旋转圆盘邮件

这一年中最酷的邮件之一是B&Q的交互式旋转圆盘邮件。对于WebKit客户端,该邮件包含了一个旋转热点,供用户点击查看不同的部分。

View the full email here

整个邮件中最令人印象深刻的部分,可能是它为非WebKit邮箱使用的备用方案——一个美丽的旋转木马网格布局,没有隐藏也没有复制任何内容!

图片 1

你可以在 Firefox 或 Internet Explorer 浏览器中打开该邮件查看备用设计。

Litmus Builder(邮件开发工具)交互之旅邮件

为了引入我们的新邮件代码编辑器,Litmus
Builder,在这封邮件中展示了大量的可点击交互。同样,该技术也只能在Apple邮箱和Outlook
2011(Mac版)中工作,而这两个却占了我们的顾客的绝大部分。(注:邮件需要屏幕至少800像素宽才能浏览。)

该展览仅仅只是退化为一个静态背景图片,而且会调用接口跳转到登录页面。这邮件取得了巨大的成功,其产品在最开始的几天里增加了成千上万的用户。

View the full email here

想尝试一下 Litmus Builder?注册后
,你就可以开始使用HTML5和CSS3测试你的邮件!

一个创新邮件设计框架

CSS

@media screen and (-webkit-min-device-pixel-ratio:0) { /* Insert styles
here */ }

1
2
3
@media screen and (-webkit-min-device-pixel-ratio:0) {
  /* Insert styles here */
}

这个媒介查询为邮件设计师提供了一个简单的创新框架。我们可以为拥有现代邮箱客户端的那一大部分订阅者提供更好的体验。

最好的防卫就是进攻。现在该是进攻的时候了。在邮件设计中使用这个媒介查询开始创新,推动邮件前进。

为了订阅者去尝试。为了我们的行业,为了
对邮件的热爱。

已经迫不及待想看看我们会共同建立出什么了。

如果你用的是这种方法——或者开发你自己的更高级的版本——在你的邮件中,或者如果你对这种方法有任何的疑问,请在下面的评论中贴出,或者用更好的方式,去Litmus社区!

发现你的受众 + 测试你的设计

对于能够开始使用高级技能像HTML5和CSS3来推动邮件发展,是不是感到很激动?确保识别出订阅者们最喜爱的邮箱APP,然后测试你新设计的邮件。

通过邮件分析,你可以了解订阅者经常在哪里打开邮件,这样你就可以集中精力在渐进式增强(以及优雅降级!)上了。

测试设计也是开发过程中非常关键的一步。在30个以上邮箱客户端和APP之间的兼容性测试,可以确保订阅者们不论用什么邮箱打开邮件都能正常获得你的邮件。

 

赞 收藏 1
评论

十大经典排序算法

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

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

做靠谱交互动画的 5 种方法

2015/04/19 · HTML5 ·
交互动画

本文由 伯乐在线 –
Abel
翻译,黄利民
校稿。未经许可,禁止转载!
英文出处:24ways.org。欢迎加入翻译组。

从我在这个网站上开始写《Flashless
Animation》这篇文章到现在已经两年了。从那时起,交互动画已经从像圆润的APP一样的用户界面到交互式杂志在网站上流行。对网页交互动画师、交互开发人员、用户体验师、用户界面设计人员和许多其它与交互动画有关的人员来说,这是一个多么令人兴奋的时间。

但是匆忙的设计交互动画,似乎表示我们很少讨论是否必须要使用交互动画,而是更多地讨论我们用交互动画能干什么?我们花费很多时间为怎么以
60fps 使所有东西可以动画而着急,而不是设计一些方法让初级用户避免障碍。

我喜爱网页动画,并以它为生。我知道动画能被滥用,而且我们都拿flash-trubation来娱乐。但是在网页设计期间积累的教训,我们忘记它是如此的快啊。视差滚动效应也许是对这原因产生的大概介绍。在Flash和网页动画API这一令人深思的时期,我们确实学到了很多。

所以这里的五点建议,我们可以用于把处于交互动画滥用边缘的使用者拉回到高水平上。有这几点建议在心中,我们可以让2015的网页动画年真正地属于它自己。

有目的性的使用动画

很遗憾,大量的Web开发社区认为动画是装饰性的。UI设计师和交互开发人员当然理解的更到位。但是当我给一个工作室培训交互动画的时候,我知道我的学生是在和一些决策者做艰苦的斗争,这些决策者认为有动画会非常美妙并要求尽可能的在项目的结尾附上动画,而我的学生则认为不然。

这种观念差异很难动摇,但是当我们精心做动画的时候这种观念差异也许就会消失。附加动画带来的危害比益处要多,这点很少被用户考虑。例如,用户也许会抱怨动画太快或者太慢,或者他们不知道动画在展示什么。

当我今年参加 Chrome 开发峰会的时候,我有和 Roma Shah 交流的机会,她是
Polymer Material Design 背后的 UX
主管。我问她有什么建议给在设计当中使用动画和转场的设计师。她简单的回答:有目的地使用动画。如果你不能慢下来想想如何做交互动画并代表用户做一个充分知情和精心制作的决定,那么你最好不要做这个尝试。动画需要花费精力来制作,而一个差劲的动画比没有更糟糕。

不止《生活的错觉》这把书中提到的动画 12 条准则

我们总是试着在激发我们兴趣却毫不相干的事情之间找到相关性。最近越来越多的人把《生活的错觉》放在挨着《理解漫画》这本书的同一个书架上。这些书给我们带来很多来自其它领域的有用的观点。然而,我们不应该在网站上犯类似与漫画书与动画片的错误。虽然它们可以帮助我们用新的角度理解我们的工作,但是这些概念会或多或少产生上述混淆两者概念的作用。

我一直在慎重地思考《生活的错觉》,迪士尼动画工作室的经验丰富的工程师们在书中提出了动画十二条准则。这些规则对做动人的、逼真的动画非常有用,如像弹起的球、蹦跳的松鼠、绚丽的物理极光一样的页面转场动画。但是什么时候或者怎样把一个动画作为一个大型交互体验的一部分,这些准则没有对这些问题做方向性的指导。比如一个下拉操作需要多久才能伸展完毕,或者一组可操作对象是应该按照顺序,还是按照整体做成动画。

这十二条准则仅仅是一个开始地方,除此之外我们还有其它很多东西要学习。我已经写过至少六条应用到web和app的设计交互动画功能。当我们思考做交互动画时,我们不仅仅考虑做什么动画、动画的物理学,还要考虑为什么要做动画,怎样做动画。如果动画是多余的或者令人费解的,再严密的物理设计也是徒劳的。

有用、有必要,然后是漂亮

有一句行内话:除非一个动画既是必须又是有用的,要不然不要做它;如果它既是必须的,又是有用的,那就毫不犹豫去把它做漂亮。当说到动画和网页,目前很少有文章写什么样的动画是有用或者必要的。我们大部分都是倾向于做漂亮、令人愉快、令人有趣的动画。虽然动画的外观漂亮很重要,但是外观是仅次于用户的整体体验的。

第一次我在掌机看到黄色口袋妖怪的开机动画时,我被迷住了。到了第六次的时候,当Freak的游戏图标出现在屏幕上时,我被开始按钮搞的厌烦了。当我们在做设计的时候,令我们高兴和有意义的东西对用户来说却是未必的。像黄色口袋妖怪令人欣喜的开机动画一样,纯粹令人愉快的动画即使是被用户欣然的接受,但是太多次的重复却最终无意义的动画,用户就会慢慢对该动画产生厌恶之情。

如果一个动画不能在某种方式上帮助用户,如让用户知道他们在网站的什么位置或者一个页面上的两个元素是如何彼此相关的,那么它是在耗费电池并在不停地产生仅仅令用户高兴的效果。资源很少得到合理的利用。

动画不是仅仅为了令用户高兴,首先,我们必须能让动画给用户清晰的表达两个意思。以从 Finethought.com 网站上这个菜单图标为例。当我们点击这个菜单图标时,它向我们表达了两个意思。

1.这个菜单按钮用动画给用户以反馈,表面这个图标已经被点击了。

2.这个菜单按钮表明通过点击关闭图标,页面的内容将会发生改变。

假定我们有两个好的理由来做交互动画,那么就会有理由来取悦用户。

以四倍速度让动画更快

有一个传统动画的概览法适合于网页动画:不管你的动画应该持续多久,把动画的持续时间减半,然后再减半。当我们设计动画几个小时之后,我们对时间的感觉会变长。对我们来说速度很快的动画,对大部分用户来讲已经到了无法忍受的慢。事实上,最近来自于用户对网站动画接口的绝大数批评似乎是:“它太慢了。”一个好的动画是不唐突的并且速度是非常快的。

如果让你的动画持续时间处于一个最佳值,那么请把动画持续时间减少到原来的四分之一。

安装一个关闭开关

不管一个动画是多么的富有见解和必要性,总有一些人对动画不感冒。对这些人来说,我们必须增加一种方式来让他们关闭网页上的动画。

幸运的是,网页设计师已经在考虑赋予用户一些自己做决定来改变网页体验的权力。以下面的动画为例,这个《小鱼商店》的动画电影网站允许用户关闭视差效果。虽然它不能移除全部动画,但是这个网站确实减少了动画的视觉给用户带来的头晕的感觉。

在我们网页设计的工具库中,动画是一个强有力的工具。但是我们必须小心:如果我们滥用动画,动画也许会带来不好的效果;如果我们低估动画,它就不能完全发挥它的作用。但是如果我们恰到好处的使用动画,当既有必要又有用的使用动画,赋予用户关闭的动画的权力,那么动画会变成一个帮助我们建造一些用起来简单、带给我们快乐的东西。

让我们把2015的网页动画年带给用户吧!

赞 收藏
评论

关于作者:fzr

图片 2

微博:@fzr-fzr)
个人主页 ·
我的文章 ·
26

图片 3

前言

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

关于作者:Abel

图片 5

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

图片 3

正文

排序算法说明

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

排序对比:

图片 7

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

排序分类:

图片 8

1.冒泡排序(Bubble Sort)

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

(1)算法描述

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

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

三种方法耗时对比:

图片 9

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

冒泡排序动图演示:

图片 10

(3)算法分析

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

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

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

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

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

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]

选择排序动图演示:

图片 11

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

改进前后对比:

图片 12

插入排序动图演示:

图片 13

(3)算法分析

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

4.希尔排序(Shell Sort)

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

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注