2014年9月 ’ 的文章存档

常用排序算法之JavaScript实现

笔试面试经常涉及各种算法,本文简要介绍常用的一些算法,并用JavaScript实现。

一、插入排序

1)算法简介

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

2)算法描述和实现

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

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

 

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

 

3)算法分析

最佳情况:输入数组按升序排列。T(n) = O(n)
最坏情况:输入数组按降序排列。T(n) = O(n2)
平均情况:T(n) = O(n2)
二、二分插入排序
阅读全文

内存管理技巧:如何避免JavaScript的内存泄露

高效的JavaScript Web应用必须流畅,快速。与用户交互的任何应用程序,都需要考虑如何确保内存有效使用,因为如果消耗过多,页面就会崩溃,迫使用户重新加载。而你只能躲在角落哭泣。

自动垃圾收集是不能代替有效的内存管理的,特别是在大型,长时间运行的Web应用程序中。在这次讲座中,我们将演示如何通过Chrome的DevTools对内存进行有效的管理。

并了解如何解决性能问题,如内存泄漏,频繁的垃圾收集暂停,和整体内存膨胀,那些真正让你耗费精力的东西。

Addy Osmani在他的PPT中展示了很多会在Chrome V8中产生内存泄漏的示例:

1) Delete一个Object的属性会让此对象变慢(多耗费15倍的内存)

var o = { x: 'y' };
delete o.x; //此时o会成一个慢对象
o.x; //

var o = { x: 'y' };
o = null;  //应该这样

阅读全文

95后有多牛?18岁进 Facebook 当全职工程师

Facebook 在物色和吸纳人才方面一贯口碑不错,比如,创业公司就能向它学习如何招到优秀的产品设计师——它家的实习项目也很厉害,总能网罗到天才程序猿,这不,一位刚高中毕业、8 月 24 日满 18 岁的小哥 Michael Sayman 就加入了 Facebook,担任全职工程师——他也是 Facebook 最年轻员工之一。

ddd

 

小哥笑起来很甜美吧,是不是还有点眼熟?没错,Sayman 此番加入马扎哥其实是再续前缘——他之前写了一个火火火火火的 iPhone App,用的还是 Facebook 的开发者工具,随后他引起了 Facebook 的关注。后者特地请他飞到总部和马扎哥碰了碰——一碰,就碰出了个总部实习机会。

Sayman 显然实习得很嗨,他在自己的 Facebook 主页上写道:“在 Facebook 的暑期实习简直爽。不过,当当当当,Facebook 还请我去当全职工程师。嗯,我在这的生涯刚刚起航。” 这条帖子的内容也受到了 Facebook 的认可。

对于这种有点才华有点狂有时简单有时 naive 的 95 后,我只想说一句:带带我。

 

文章来自:36kr