快速排序–js实现算法

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好,可是这是为什么呢,我也不知道。好在我的强迫症又犯了,查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案:

快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

1. 算法步骤

  1. 从数列中挑出一个元素,称为 “基准”(pivot);
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

2. 动图演示

动图演示

3. JavaScript 代码实现

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != 'number' ? 0 : left,
        right = typeof right != 'number' ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分区操作
    var pivot = left,                      // 设定基准值(pivot)
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function partition2(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function quickSort2(arr, low, high) {
  if (low < high) {
    let pivot = partition2(arr, low, high);
    quickSort2(arr, low, pivot - 1);
    quickSort2(arr, pivot + 1, high);
  }
  return arr;
}

归并排序–js实现算法

归并排序

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

  • 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
  • 自下而上的迭代;

在《数据结构与算法 JavaScript 描述》中,作者给出了自下而上的迭代方法。但是对于递归法,作者却认为:

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。

说实话,我不太理解这句话。意思是 JavaScript 编译器内存太小,递归太深容易造成内存溢出吗?还望有大神能够指教。

和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

2. 算法步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
  4. 重复步骤 3 直到某一指针达到序列尾;
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

3. 动图演示

动图演示

4. JavaScript 代码实现

function mergeSort(arr) {  // 采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

希尔排序–js代码实现

希尔排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

  • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
  • 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

1. 算法步骤

  1. 选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
  2. 按增量序列个数 k,对序列进行 k 趟排序;
  3. 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

2. JavaScript 代码实现

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //动态定义间隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

插入排序–js实现

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

1. 算法步骤

  1. 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

2. 动图演示

动图演示

3. JavaScript 代码实现

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

选择排序–js实现算法

选择排序

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤

  1. 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  3. 重复第二步,直到所有元素均排序完毕。

2. 动图演示

动图演示

3. JavaScript 代码实现

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    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;
    }
    return arr;
}

冒泡算法 — js之实现

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

作为最简单的排序算法之一,冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

1. 算法步骤

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    2. 动图演示

    动图演示

    3. 什么时候最快

    当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。

    4. 什么时候最慢

    当输入的数据是反序时(写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗)。

    5. JavaScript 代码实现

    function bubbleSort(arr) {
        var len = arr.length;
        for (var i = 0; i < len - 1; 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;
    }

ES6/ES7常用语法总结

最常用的ES6特性

let, const, class, extends, super, arrow functions, template string, destructuring, default, rest arguments
这些是ES6最常用的几个语法,基本上学会它们,我们就可以走遍天下都不怕啦!我会用最通俗易懂的语言和例子来讲解它们,保证一看就懂,一学就会。

let, const

这两个的用途与var类似,都是用来声明变量的,但在实际运用中他俩都有各自的特殊用途。
首先来看下面这个例子:

var name = 'zach'

while (true) {
    var name = 'obama'
    console.log(name)  //obama
    break
}

console.log(name)  //obama

使用var 两次输出都是obama,这是因为ES5只有全局作用域和函数作用域,没有块级作用域,这带来很多不合理的场景。第一种场景就是你现在看到的内层变量覆盖外层变量。而let则实际上为JavaScript新增了块级作用域。用它所声明的变量,只在let命令所在的代码块内有效。

let name = 'zach'

while (true) {
    let name = 'obama'
    console.log(name)  //obama
    break
}

console.log(name)  //zach

另外一个var带来的不合理场景就是用来计数的循环变量泄露为全局变量,看下面的例子:

var a = [];
for (var i = 0; i < 10; i++) {
  a[i] = function () {
    console.log(i);
  };
}
a[6](); // 10

上面代码中,变量i是var声明的,在全局范围内都有效。所以每一次循环,新的i值都会覆盖旧值,导致最后输出的是最后一轮的i的值。而使用let则不会出现这个问题。

var a = [];
for (let i = 0; i < 10; i++) {
  a[i] = function () {
    console.log(i);
  };
}
a[6](); // 6

再来看一个更常见的例子,了解下如果不用ES6,而用闭包如何解决这个问题。

var clickBoxs = document.querySelectorAll('.clickBox')
for (var i = 0; i < clickBoxs.length; i++){
    clickBoxs[i].onclick = function(){
        console.log(i)
    }
}

我们本来希望的是点击不同的clickBox,显示不同的i,但事实是无论我们点击哪个clickBox,输出的都是5。下面我们来看下,如何用闭包搞定它。

function iteratorFactory(i){
    var onclick = function(e){
        console.log(i)
    }
    return onclick;
}
var clickBoxs = document.querySelectorAll('.clickBox')
for (var i = 0; i < clickBoxs.length; i++){
    clickBoxs[i].onclick = iteratorFactory(i)
}

const也用来声明变量,但是声明的是常量。一旦声明,常量的值就不能改变。

const PI = Math.PI

PI = 23 //Module build failed: SyntaxError: /es6/app.js: "PI" is read-only

当我们尝试去改变用const声明的常量时,浏览器就会报错。
const有一个很好的应用场景,就是当我们引用第三方库的时声明的变量,用const来声明可以避免未来不小心重命名而导致出现bug:

const monent = require('moment')

class, extends, super

这三个特性涉及了ES5中最令人头疼的的几个部分:原型、构造函数,继承…你还在为它们复杂难懂的语法而烦恼吗?你还在为指针到底指向哪里而纠结万分吗?

有了ES6我们不再烦恼!

ES6提供了更接近传统语言的写法,引入了Class(类)这个概念。新的class写法让对象原型的写法更加清晰、更像面向对象编程的语法,也更加通俗易懂。

class Animal {
    constructor(){
        this.type = 'animal'
    }
    says(say){
        console.log(this.type + ' says ' + say)
    }
}

let animal = new Animal()
animal.says('hello') //animal says hello

class Cat extends Animal {
    constructor(){
        super()
        this.type = 'cat'
    }
}

let cat = new Cat()
cat.says('hello') //cat says hello

上面代码首先用class定义了一个“类”,可以看到里面有一个constructor方法,这就是构造方法,而this关键字则代表实例对象。简单地说,constructor内定义的方法和属性是实例对象自己的,而constructor外定义的方法和属性则是所有实例对象可以共享的。

Class之间可以通过extends关键字实现继承,这比ES5的通过修改原型链实现继承,要清晰和方便很多。上面定义了一个Cat类,该类通过extends关键字,继承了Animal类的所有属性和方法。

super关键字,它指代父类的实例(即父类的this对象)。子类必须在constructor方法中调用super方法,否则新建实例时会报错。这是因为子类没有自己的this对象,而是继承父类的this对象,然后对其进行加工。如果不调用super方法,子类就得不到this对象。

ES6的继承机制,实质是先创造父类的实例对象this(所以必须先调用super方法),然后再用子类的构造函数修改this。

P.S 如果你写react的话,就会发现以上三个东西在最新版React中出现得很多。创建的每个component都是一个继承React.Component的类。详见react文档

arrow function

这个恐怕是ES6最最常用的一个新特性了,用它来写function比原来的写法要简洁清晰很多:

function(i){ return i + 1; } //ES5
(i) => i + 1 //ES6

简直是简单的不像话对吧…
如果方程比较复杂,则需要用{}把代码包起来:

function(x, y) { 
    x++;
    y--;
    return x + y;
}
(x, y) => {x++; y--; return x+y}

除了看上去更简洁以外,arrow function还有一项超级无敌的功能!
长期以来,JavaScript语言的this对象一直是一个令人头痛的问题,在对象方法中使用this,必须非常小心。例如:

class Animal {
    constructor(){
        this.type = 'animal'
    }
    says(say){
        setTimeout(function(){
            console.log(this.type + ' says ' + say)
        }, 1000)
    }
}

 var animal = new Animal()
 animal.says('hi')  //undefined says hi

运行上面的代码会报错,这是因为setTimeout中的this指向的是全局对象。所以为了让它能够正确的运行,传统的解决方法有两种:

  1. 第一种是将this传给self,再用self来指代this
       says(say){
           var self = this;
           setTimeout(function(){
               console.log(self.type + ' says ' + say)
           }, 1000)

    2.第二种方法是用bind(this),即

       says(say){
           setTimeout(function(){
               console.log(this.type + ' says ' + say)
           }.bind(this), 1000)

    但现在我们有了箭头函数,就不需要这么麻烦了:

class Animal {
    constructor(){
        this.type = 'animal'
    }
    says(say){
        setTimeout( () => {
            console.log(this.type + ' says ' + say)
        }, 1000)
    }
}
 var animal = new Animal()
 animal.says('hi')  //animal says hi

当我们使用箭头函数时,函数体内的this对象,就是定义时所在的对象,而不是使用时所在的对象。
并不是因为箭头函数内部有绑定this的机制,实际原因是箭头函数根本没有自己的this,它的this是继承外面的,因此内部的this就是外层代码块的this。

template string

这个东西也是非常有用,当我们要插入大段的html内容到文档中时,传统的写法非常麻烦,所以之前我们通常会引用一些模板工具库,比如mustache等等。

大家可以先看下面一段代码:

$("#result").append(
  "There are <b>" + basket.count + "</b> " +
  "items in your basket, " +
  "<em>" + basket.onSale +
  "</em> are on sale!"
);

我们要用一堆的’+’号来连接文本与变量,而使用ES6的新特性模板字符串“后,我们可以直接这么来写:

$("#result").append(`
  There are <b>${basket.count}</b> items
   in your basket, <em>${basket.onSale}</em>
  are on sale!
`);

用反引号(\来标识起始,用${}`来引用变量,而且所有的空格和缩进都会被保留在输出之中,是不是非常爽?!

React Router从第1.0.3版开始也使用ES6语法了,比如这个例子:

<Link to={`/taco/${taco.name}`}>{taco.name}</Link>

React Router

destructuring

ES6允许按照一定模式,从数组和对象中提取值,对变量进行赋值,这被称为解构(Destructuring)。

看下面的例子:

let cat = 'ken'
let dog = 'lili'
let zoo = {cat: cat, dog: dog}
console.log(zoo)  //Object {cat: "ken", dog: "lili"}

用ES6完全可以像下面这么写:

let cat = 'ken'
let dog = 'lili'
let zoo = {cat, dog}
console.log(zoo)  //Object {cat: "ken", dog: "lili"}

反过来可以这么写:

let dog = {type: 'animal', many: 2}
let { type, many} = dog
console.log(type, many)   //animal 2

default, rest

default很简单,意思就是默认值。大家可以看下面的例子,调用animal()方法时忘了传参数,传统的做法就是加上这一句type = type || 'cat' 来指定默认值。

function animal(type){
    type = type || 'cat'  
    console.log(type)
}
animal()

如果用ES6我们而已直接这么写:

function animal(type = 'cat'){
    console.log(type)
}
animal()

最后一个rest语法也很简单,直接看例子:

function animals(...types){
    console.log(types)
}
animals('cat', 'dog', 'fish') //["cat", "dog", "fish"]

而如果不用ES6的话,我们则得使用ES5的arguments

转:JavaScript instanceof 运算符深入剖析

原文地址:https://www.ibm.com/developerworks/cn/web/1306_jiangjj_jsinstanceof/

instanceof 运算符简介

在 JavaScript 中,判断一个变量的类型尝尝会用 typeof 运算符,在使用 typeof 运算符时采用引用类型存储值会出现一个问题,无论引用的是什么类型的对象,它都返回 “object”。ECMAScript 引入了另一个 Java 运算符 instanceof 来解决这个问题。instanceof 运算符与 typeof 运算符相似,用于识别正在处理的对象的类型。与 typeof 方法不同的是,instanceof 方法要求开发者明确地确认对象为某特定类型。例如:

清单 1. instanceof 示例
var oStringObject = new String("hello world");
console.log(oStringObject instanceof String);   // 输出 "true"

这段代码问的是“变量 oStringObject 是否为 String 对象的实例?”oStringObject 的确是 String 对象的实例,因此结果是”true”。尽管不像 typeof 方法那样灵活,但是在 typeof 方法返回 “object” 的情况下,instanceof 方法还是很有用的。

instanceof 运算符的常规用法

通常来讲,使用 instanceof 就是判断一个实例是否属于某种类型。例如:

清单 2. instanceof 常规用法
1
2
3
4
// 判断 foo 是否是 Foo 类的实例
function Foo(){}
var foo = new Foo();
console.log(foo instanceof Foo)//true

另外,更重的一点是 instanceof 可以在继承关系中用来判断一个实例是否属于它的父类型。例如:

清单 3. instanceof 在继承中关系中的用法
1
2
3
4
5
6
7
8
// 判断 foo 是否是 Foo 类的实例 , 并且是否是其父类型的实例
function Aoo(){}
function Foo(){}
Foo.prototype = new Aoo();//JavaScript 原型继承
var foo = new Foo();
console.log(foo instanceof Foo)//true
console.log(foo instanceof Aoo)//true

上面的代码中是判断了一层继承关系中的父类,在多层继承关系中,instanceof 运算符同样适用。

你真的了解 instanceof 操作符吗?

看了上面的代码示例,是不是觉得 instanceof 操作符很简单,下面来看点复杂的用法。

清单 4. instanceof 复杂用法
1
2
3
4
5
6
7
8
9
console.log(Object instanceof Object);//true
console.log(Function instanceof Function);//true
console.log(Number instanceof Number);//false
console.log(String instanceof String);//false
console.log(Function instanceof Object);//true
console.log(Foo instanceof Function);//true
console.log(Foo instanceof Foo);//false

看了上面的代码是不是又晕头转向了?为什么 Object 和 Function instanceof 自己等于 true,而其他类 instanceof 自己却又不等于 true 呢?如何解释?要想从根本上了解 instanceof 的奥秘,需要从两个方面着手:1,语言规范中是如何定义这个运算符的。2,JavaScript 原型继承机制。

详细剖析 ECMAScript-262 edition 3 中 instanceof 运算符的定义

语言规范对中 instanceof 运算符的定义如下:

清单 5. 规范中 instanceof 运算符定义
11.8.6 The instanceof operator
 The production RelationalExpression:
     RelationalExpression instanceof ShiftExpression is evaluated as follows:
 1. Evaluate RelationalExpression.
 2. Call GetValue(Result(1)).// 调用 GetValue 方法得到 Result(1) 的值,设为 Result(2)
 3. Evaluate ShiftExpression.
 4. Call GetValue(Result(3)).// 同理,这里设为 Result(4)
 5. If Result(4) is not an object, throw a TypeError exception.// 如果 Result(4) 不是 object,
                                                                //抛出异常
 /* 如果 Result(4) 没有 [[HasInstance]] 方法,抛出异常。规范中的所有 [[...]] 方法或者属性都是内部的,
在 JavaScript 中不能直接使用。并且规范中说明,只有 Function 对象实现了 [[HasInstance]] 方法。
所以这里可以简单的理解为:如果 Result(4) 不是 Function 对象,抛出异常 */
 6. If Result(4) does not have a [[HasInstance]] method,
   throw a TypeError exception.
 // 相当于这样调用:Result(4).[[HasInstance]](Result(2))
 7. Call the [[HasInstance]] method of Result(4) with parameter Result(2).
 8. Return Result(7).
 // 相关的 HasInstance 方法定义
 15.3.5.3 [[HasInstance]] (V)
 Assume F is a Function object.// 这里 F 就是上面的 Result(4),V 是 Result(2)
 When the [[HasInstance]] method of F is called with value V,
     the following steps are taken:
 1. If V is not an object, return false.// 如果 V 不是 object,直接返回 false
 2. Call the [[Get]] method of F with property name "prototype".// 用 [[Get]] 方法取
                                                                // F 的 prototype 属性
 3. Let O be Result(2).//O = F.[[Get]]("prototype")
 4. If O is not an object, throw a TypeError exception.
 5. Let V be the value of the [[Prototype]] property of V.//V = V.[[Prototype]]
 6. If V is null, return false.
 // 这里是关键,如果 O 和 V 引用的是同一个对象,则返回 true;否则,到 Step 8 返回 Step 5 继续循环
 7. If O and V refer to the same object or if they refer to objects
   joined to each other (section 13.1.2), return true.
 8. Go to step 5.

上面的规范定义很晦涩,而且看起来比较复杂,涉及到很多概念,但把这段规范翻译成 JavaScript 代码却很简单,如下:

清单 6. JavaScript instanceof 运算符代码
1
2
3
4
5
6
7
8
9
10
11
function instance_of(L, R) {//L 表示左表达式,R 表示右表达式
 var O = R.prototype;// 取 R 的显示原型
 L = L.__proto__;// 取 L 的隐式原型
 while (true) {
   if (L === null)
     return false;
   if (O === L)// 这里重点:当 O 严格等于 L 时,返回 true
     return true;
   L = L.__proto__;
 }
}

JavaScript 原型继承机制

由于本文主要集中在剖析 JavaScript instanceof 运算符,所以对于 JavaScript 的原型继承机制不再做详细的讲解,下面参考来自 http://www.mollypages.org/misc/js.mp 的一张图片,此图片详细的描述了 JavaScript 各种对象的显示和隐式原型链结构。

由其本文涉及显示原型和隐式原型,所以下面对这两个概念作一下简单说明。在 JavaScript 原型继承结构里面,规范中用 [[Prototype]] 表示对象隐式的原型,在 JavaScript 中用 __proto__ 表示,并且在 Firefox 和 Chrome 浏览器中是可以访问得到这个属性的,但是 IE 下不行。所有 JavaScript 对象都有 __proto__ 属性,但只有 Object.prototype.__proto__ 为 null,前提是没有在 Firefox 或者 Chrome 下修改过这个属性。这个属性指向它的原型对象。 至于显示的原型,在 JavaScript 里用 prototype 属性表示,这个是 JavaScript 原型继承的基础知识,在这里就不在叙述了。

图 1. JavaScript 原型链

JavaScript 原型链

讲解 instanceof 复杂用法

有了上面 instanceof 运算符的 JavaScript 代码和原型继承图,再来理解 instanceof 运算符将易如反掌。下面将详细讲解 Object instanceof Object,Function instanceof Function 和 Foo instanceof Foo 三个示例,其它示例读者可自行推演。

清单 7. Object instanceof Object
1
2
3
4
5
6
7
8
9
10
11
12
// 为了方便表述,首先区分左侧表达式和右侧表达式
ObjectL = Object, ObjectR = Object;
// 下面根据规范逐步推演
O = ObjectR.prototype = Object.prototype
L = ObjectL.__proto__ = Function.prototype
// 第一次判断
O != L
// 循环查找 L 是否还有 __proto__
L = Function.prototype.__proto__ = Object.prototype
// 第二次判断
O == L
// 返回 true
清单 8. Function instanceof Function
1
2
3
4
5
6
7
8
// 为了方便表述,首先区分左侧表达式和右侧表达式
FunctionL = Function, FunctionR = Function;
// 下面根据规范逐步推演
O = FunctionR.prototype = Function.prototype
L = FunctionL.__proto__ = Function.prototype
// 第一次判断
O == L
// 返回 true
清单 9. Foo instanceof Foo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 为了方便表述,首先区分左侧表达式和右侧表达式
FooL = Foo, FooR = Foo;
// 下面根据规范逐步推演
O = FooR.prototype = Foo.prototype
L = FooL.__proto__ = Function.prototype
// 第一次判断
O != L
// 循环再次查找 L 是否还有 __proto__
L = Function.prototype.__proto__ = Object.prototype
// 第二次判断
O != L
// 再次循环查找 L 是否还有 __proto__
L = Object.prototype.__proto__ = null
// 第三次判断
L == null
// 返回 false

简析 instanceof 在 Dojo 继承机制中的应用

在 JavaScript 中,是没有多重继承这个概念的,就像 Java 一样。但在 Dojo 中使用 declare 声明类时,是允许继承自多个类的。下面以 Dojo 1.6.1 为例。

清单 10. Dojo 中多重继承
1
2
3
4
5
6
7
8
9
10
dojo.declare("Aoo",null,{});
dojo.declare("Boo",null,{});
dojo.declare("Foo",[Aoo,Boo],{});
var foo = new Foo();
console.log(foo instanceof Aoo);//true
console.log(foo instanceof Boo);//false
console.log(foo.isInstanceOf(Aoo));//true
console.log(foo.isInstanceOf(Boo));//true

上面的示例中,Foo 同时继承自 Aoo 和 Boo,但当使用 instanceof 运算符来检查 foo 是否是 Boo 的实例时,返回的是 false。实际上,在 Dojo 的内部,Foo 仍然只继承自 Aoo,而通过 mixin 机制把 Boo 类中的方法和属性拷贝到 Foo 中,所以当用 instanceof 运算符来检查是否是 Boo 的实例时,会返回 false。所以 Dojo 为每个类的实例添加了一个新的方法叫 isInstanceOf,用这个方法来检查多重继承。

结束语

本文详细介绍了 JavaScript 语言中 instanceof 运算符,并且结合语言规范深入剖析了此操作符的算法。对读者使用 JavaScript 编写复杂的面向对象程序会有很大的帮助。本文所有代码在 Firefox 15 下通过测试。

相关主题

移动端触摸数字转盘无限滚动实现思路

先看下效果,这个转盘的数字是从0-105,可以设置起始数字,那么之前的数字就变灰,不可选取,点击 加减号,会自动转动4个数字间隔,同时也可以手动触摸拖动,拖到终端105,自动回弹不可再拖动下去,同时选中的数字自动变黄···

好啦看下gif实现效果,或者点击查看,请滑动到第三屏

 

难点分析:

1、因为一个圆是360度,数字按照一定间隔排列比较合理的是18度排一个数字,那么一个圆形只能排列20个数字,其他数字如何生成?

2、如何判断当前选中并且加黄?

3、手指触摸拖动和圆盘转动的换算关系?

4、转动如何更加平滑有一定弹性

5、如何控制相应的数字显示隐藏来达到转盘数字一直增加或者减少的效果?

继续阅读移动端触摸数字转盘无限滚动实现思路