基础概念

• javascript中，函数的参数传递方式都是按值传递，没有按引用传递的参数。但是javascript中有保存引用的对象，比如数组，它们是按引用传递的。

• 变量的作用域是指一个变量在程序中哪些地方可以访问。javascript中的变量作用域被定义为函数作用域，即变量的值在定义该变量的函数内是可见的，并且定义该函数内的潜逃函数中也可访问该变量。

数组

Javascript中的数组是一种特殊的对象，用来表示偏移量的索引是该对象的属性，索引可能是整数。然而，这些数字索引在内部被转换为字符串类型，这是因为Javascript对象中的属性名必须是字符串。严格来说，JavaScript中的数组是特殊的对象。

javascript中，当把一个数组赋给另一个数组，只是为被赋值的数组增加了一个新的引用。当通过原引用修改了数组的值，另一个引用也会感知到这个变化，如下：

var nums = [];
 for (var i = 0; i < 100; ++i) 
    { 
      nums[i] = i+1; 
    } 
var samenums = nums; 
nums[0] = 400; 
print(samenums[0]); // 显示400

这种行为被称为浅复制或浅拷贝，关于浅拷贝和深拷贝可参考笔者另一篇博客:传送

数组的各种方法可查看MDN，不一一赘述：MDN

列表

列表的抽象数据类型定义：

// 列表
function List() {
    this.listSize = 0;              // 当前列表元素个数
    this.pos = 0;
    this.dataStore = [];            // 初始化一个空数组来保存列表元素
    this.append = function (element) {
        this.dataStore[this.listSize++] = element;
    };
    this.find = function (element) {
        for (var i = 0; i < this.dataStore.length; i++) {
            if (this.dataStore[i] == element) {
                return i
            }
        }
        return -1;
    };
    this.remove = function (element) {
        var foundAt = this.find(element);
        if (foundAt > -1) {
            this.dataStore.splice(foundAt, 1);
            this.listSize--;
            return true;
        }
        return false;
    };
    this.length = function () {
        return this.listSize;
    };
    this.toString(){
        return this.dataStore.join();
    };
    this.insert = function (element, after) {
        var insertPos = this.find(after);
        if (insertPos > -1) {
            this.dataStore.splice(insertPos + 1, 0, element);
            this.listSize++;
            return true;
        };
        return false;
    };
    this.clear = function () {
        delete this.dataStore;
        this.dataStore.length = 0;
        this.listSize = this.pos = 0;
    };
    this.contains = function (element) {
        for (var i = 0; i < this.dataStore.length; i++) {
            if (this.dataStore[i] == element) {
                return true
            }
        };
        return false;
    };
    this.front = function () {
        this.pos = 0;
    };
    this.end = function () {
        this.pos = this.listSize - 1;
    };
    this.prev = function () {
        if (this.pos > 0) {
            this.pos--;
        }
    };
    this.next = function () {
        if (this.pos < this.listSize - 1) {
            this.pos++;
        }
    };
    this.moveTo=function(position){
        this.pos = position;
    };
    this.getElement = function () {
        return this.dataStore[this.pos];
    }
}

栈

栈是特殊的列表，栈内的元素只通过列表的一端访问，这一端称为栈顶。栈具有后入先出的特点，任何不在栈顶的元素都无法访问。

// 栈
function Stack() {
    this.dataStore = [];
    this.top = 0;
    this.push = function (element) {
        this.dataStore[this.top++] = element;
    };
    this.peek = function () {
        return this.dataStore[this.top - 1];
    };
    this.pop = function () {
        return this.dataStore[--this.top];
    };
    this.clear = function () {
        this.top = 0;
    };
    this.length = function () {
        return this.top;
    }
};

使用栈判断一个字符串是否为回文

使用栈，可以轻松判断一个字符串是否是回文。我们将拿到的字符串的每个字符按从左至右的顺序压入栈。当字符串中的字符都入栈后，栈内就保存了 一个反转后的字符串，最后的字符在栈顶，第一个字符在栈底。字符串完整压入栈内后，通过持续弹出栈中的每个 字母就可以得到一个新字符串，该字符串刚好与原 来的字符串顺序相反。我们只需要比较这两个字符 串即可，如果它们相等，就是一个回文。

// 使用栈判断字符串是否为回文
function isPalindrome(word) {
    var s = new Stack();
    for (var i = 0; i < word.length; i++) {
        s.push(word[i]);
    };
    var r_word = "";
    while (s.length() > 0) {
        r_word += s.pop();
    };
    if (word == r_word) {
        return true;
    } else {
        return false;
    }
}

队列

队列是一种列表，只能从队尾插入元素，在队尾删除元素，用于存储按顺序排列的数据，先进先出。

// 队列
function Queue() {
    this.dataStore = [];
    this.enqueue = function (element) {
        this.dataStore.push(element);
    };
    this.dequeue = function () {
        return this.dataStore.shift();
    };
    this.front = function () {
        return this.dataStore[0];
    };
    this.back = function () {
        return this.dataStore[this.dataStore.length - 1];
    };
    this.empty = function () {
        if (this.dataStore.length == 0) {
            return true;
        } else {
            return false;
        }
    }
}

链表

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。链表的尾元素指向一个null的节点。许多链表的实现都在链表最前面有一个特殊节点，叫做头节点。

// 链表

function Node(element) {
    this.element = element;
    this.next = null;
};

function LList() {
    this.head = new Node("head");
    this.find = function (item) {
        var currNode = this.head;
        while (currNode.element != item) {
            currNode = currNode.next;
        };
        return currNode;
    };
    this.insert = function (newElement, item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        newNode.next = current.next;
        current.next = newNode;
    };
    this.display = function () {
        var currNode = this.head;
        while (!(currNode.next == null)) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    };
    this.findPrevious = function (item) {
        var currNode = this.head;
        while (!(currNode.next == null) && (currNode.next.element != item)) {
            currNode = currNode.next;
        };
        return currNode;
    };
    this.remove = function (item) {
        var prevNode = this.findPrevious(item);
        if (!(prevNode.next == null)) {
            prevNode.next = prevNode.next.next;
        }
    }
}

双向链表

通过给Node对象增加一个属性，该属性存储指向前驱节点的链接。此时向链表插入一个节点需要更多的工作，我们需要指出该节点正确的前驱和后继。但是在链表中删除节点时，不需要再查找待删除节点的前驱节点了。

function Node(element) {
    this.element = element;
    this.next = null;
    this.previous = null;
};

function LList() {
    this.head = new Node("head");
    this.find = function (item) {
        var currNode = this.head;
        while (currNode.element != item) {
            currNode = currNode.next;
        };
        return currNode;
    };
    this.insert = function (newElement, item) {
        var newNode = new Node(newElement);
        var current = this.find(item);
        newNode.next = current.next;
        newNode.previous = current;
        current.next = newNode;
    };
    this.display = function () {
        var currNode = this.head;
        while (!(currNode.next == null)) {
            console.log(currNode.next.element);
            currNode = currNode.next;
        }
    };
    this.displayReverse = function () {
        var currNode = this.findLast();
        while (!(currNode.previous == null)) {
            console.log(currNode.element);
            currNode = currNode.previous;
        }
    };
    this.remove = function (item) {
        var currNode = this.find(item);
        if (!(currNode.next == null)) {
            currNode.previous.next = currNode.next;
            currNode.next.previous = currNode.previous;
            currNode.next = null;
            currNode.previous = null;
        }
    };
    this.findLast = function () {
        var currNode = this.head;
        while (!(currNode.next == null)) {
            currNode = currNode.next;
        };
        return currNode;
    }
}

循环链表

在插入节点时，使得插入的节点的next属性指向链表的头节点，也就是链表的尾节点指向头节点，形成一个循环链表。

创建循环链表，只需修改单向链表LList类的构造函数：

    this.head = new Node("head");
    this.head.next=this.head;

而display函数也需要修改，避免进入死循环：

this.display = function () {
    var currNode = this.head;
    while (!(currNode.next == null) && !(currNode.next.element == "head")) {
        console.log(currNode.next.element);
        currNode = currNode.next;
    }
};

散列

散列是基于数组进行设计的。所有元素根据和该元素对应的键，保存在数组的特定位置。使用散列表存储数据时，通过一个散列函数将键映射为一个数字，这个数字的范围是0到散列表的长度。

理想情况下，散列函数会将每个键值映射为一个唯一的数组索引。然而，键的数量是无限的，数组的 长度是有限的（理论上，在JavaScript中是这样）， 一个更现实的目标是让散列函数尽量将键均匀地映射到数组中。

即使使用一个高效的散列函数，仍然存在将两个键 映射成同一个值的可能，这种现象称为碰撞 （collision），当碰撞发生时，我们需要有方案去解决。

由于大部分应用中，键是字符串类型的，散列函数可以是：将字符串中每个字符的ASCII码值相加的和除以数组长度，余数作为散列值。为了避免碰撞，首先要保证散列表中存储数据的数组的长度是质数，这和计算散列值时的取余运算有关。

function HashTable() {
    this.table = new Array(137);
    this.simpleHash = function (data) {
        var total = 0;
        for (var i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };
        return total % this.table.length;
    };
    this.showDis = function () {
        for (var i = 0; i < this.table.length; i++) {
            if (this.table[i] != undefined) {
                console.log(i + ": " + this.table[i]);
            }
        }
    };
    this.put = function (data) {
        var pos = this.simpleHash(data);
        this.table[pos] = data;
    }
}

前面更多是介绍散列函数，现在使用散列表来储存数据。需要修改put()方法，使得该方法同时接收键和数据作为参数，对键值散列后，将数据储存到散列表中。

同时定义get()方法，用以读取存储在散列表中的数据。完整散列表如下：

function HashTable() {
    this.table = new Array(137);
    this.simpleHash = function (data) {
        var total = 0;
        for (var i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };
        return total % this.table.length;
    };
    this.showDis = function () {
        for (var i = 0; i < this.table.length; i++) {
            if (this.table[i] != undefined) {
                console.log(i + ": " + this.table[i]);
            }
        }
    };
    this.put = function (key, data) {
        var pos = this.simpleHash(key);
        this.table[pos] = data;
    };
    this.get = function (key) {
        return this.table[this.simpleHash(key)];
    }
}

碰撞处理

当散列函数对于多个输入产生同样的输出时，就产生了碰撞。我们这里通过开链法和线性探测法解决碰撞。

开链法

实现开链法的方法是：在创建存储散列过的键值的数组时，通过调用一个函数创建一个新的空数组，然后将该数组赋给散列表里的每个元素。这样就创建了一个二维数组。

考虑到散列表现在使用多维数组存储数据，需要重新定义函数。

put() 方法将键值散列，散列后的值对应数组中的一个位置，先尝试将数据放到该位置上的数组中的第一个单元格，如果该单元格里已经有数据 了，put() 方法会搜索下一个位置，直到找到能放置数据的单元格，并把键值数据存储进去。

get() 方法先对键值散列，根据散列后的值找到散列表中相应的位置，然后搜索该位置上的链，直到找到键值。如果找到，就将紧跟在键值后面的数据返回；如果没找到，就返回undefined。

// 开链法
function HashTable() {
    this.table = new Array(137);
    this.buildChains = function () {            // 创建二维数组
        for (var i = 0; i < this.table.length; i++) {
            this.table[i] = new Array();
        }
    };
    this.simpleHash = function (data) {
        var total = 0;
        for (var i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };
        return total % this.table.length;
    };
    this.showDis = function () {
        for (var i = 0; i < this.table.length; i++) {
            if (this.table[i][0] != undefined) {
                console.log(i + ": " + this.table[i]);
            }
        }
    };
    this.put = function (key, data) {
        var pos = this.simpleHash(key);
        var index = 0;
        if (this.table[pos][index] == undefined) {
            this.table[pos][index] = key;
            this.table[pos][index + 1] = data;
        } else {
            while (this.table[pos][index] !== undefined) {
                index++;
            };
            this.table[pos][index] = key;
            this.table[pos][index + 1] = data;
        }
    };
    this.get = function (key) {
        var index = 0;
        var pos = this.simpleHash(key);
        if (this.table[pos][index] = key) {
            return this.table[pos][index + 1];
        } else {
            index += 2;
            while (this.table[pos][index] != key) {
                index += 2;
            };
            return this.table[pos][index + 1];
        };
        return undefined;

    }
}

线性探测法

当发生碰撞时，线性探测法检查散列表中的下一 个位置是否为空。如果为空，就将数据存入该位 置；如果不为空，则继续检查下一个位置，直到找 到一个空的位置为止。该技术是基于这样一个事 实：每个散列表都会有很多空的单元格，可以使用 它们来存储数据。

为了说明线性探测法的工作原理，可以重写put()和get() 方法。为了实现一个真实的数据存取系统，需要为HashTable类增加一个新的数组，用来存储数据。数组table和values并行工作，当将一个键值保存到数组table 中时，将数据存入数组 values中相应的位置上。

function HashTable() {
    this.table = new Array(137);
    this.values = [];
    this.simpleHash = function (data) {
        var total = 0;
        for (var i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        };
        return total % this.table.length;
    };
    this.showDis = function () {
        for (var i = 0; i < this.table.length; i++) {
            if (this.table[i] != undefined) {
                console.log(i + ": " + this.values[i]);
            }
        }
    };
    this.put = function (key, data) {
        var pos = this.simpleHash(key);
        if (this.table[pos] == undefined) {
            this.table[pos] == key;
            this.values[pos] = data
        } else {
            while (this.table[pos] != undefined) {
                pos++;
            };
            this.table[pos] = key;
            this.values[pos] = data;
        }
    };
    this.get = function (key) {
        var hash = -1;
        hash = this.simpleHash(key);
        if (hash > -1) {
            for (var i = hash; this.table[hash] != undefined; i++) {
                if (this.table[hash] == key) {
                    return this.values[hash];
                }
            }
        };
        return undefined;
    }
}

集合

集合是由一组无序但彼此之间又有一定相关性的成员构成的，每个成员在集合中只能出现一次。

// 集合
function Set() {
    this.dataStore = [];
    this.add = function (data) {                    // 添加数据
        if (this.dataStore.indexOf(data) < 0) {
            this.dataStore.push(data);
            return true;
        } else {
            return false;
        }
    };
    this.remove = function (data) {                 // 移除某个数据
        var pos = this.dataStore.indexOf(data);
        if (pos > -1) {
            this.dataStore.splice(pos, 1);
            return true;
        } else {
            return false;
        }
    };
    this.show = function () {
        return this.dataStore;
    };
    this.contains = function (data) {               // 判断有无此数据
        if (this.dataStore.indexOf(data) > -1) {
            return true;
        } else {
            return false;
        }
    };
    this.union = function (set) {           // 并集，将两个集合合并
        var tempSet = new Set();
        for (var i = 0; i < this.dataStore.length; ++i) {
            tempSet.add(this.dataStore[i]);
        };
        for (var i = 0; i < set.dataStore.length; ++i) {
            if (!tempSet.contains(set.dataStore[i])) {
                tempSet.dataStore.push(set.dataStore[i]);
            }
        };
        return tempSet;
    }
    this.intersect = function (set) {       // 求两个集合的交集
        var tempSet = new Set();
        for (var i = 0; i < this.dataStore.length; ++i) {
            if (set.contains(this.dataStore[i])) {
                tempSet.add(this.dataStore[i]);
            }
        } ；
        return tempSet;
    };
    this.size = function () {           // 当前集合长度
        return this.dataStore.length;
    };
    this.subset = function (set) {          // 判断当前集合是否为某个集合的子集
        if (this.size() > set.size()) {
            return false
        } else {
            for (var i = 0; i < this.dataStore.length; i++) {
                if (!set.contains(this.dataStore[i])) {
                    return false
                }
            }
        };
        return true;
    }
}

二叉树和二叉查找树

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据。 树被用来存储具有层级关系的数据，树还被用来存储有序列表。

树可以分为几个层次 ，根节点是第0层，它的子节点是第1层，子节点的子节点是第2层，以此类推。树中任何一层的节点可以都看做是子树的根，该子树包含根节点的子节点，子节点的子节点等。我们定义树的层数就是树的深度。

二叉树是一种特殊的树，它的子节点个数不超过两个。二叉树具有一些特殊的计算性质，使得在它们之上的一些操作异常高效。

二叉查找树是一种特殊的二 叉树，相对较小的值保存在左节点中，较大的值保 存在右节点中。这一特性使得查找的效率很高，对 于数值型和非数值型的数据，比如单词和字符串， 都是如此。

function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = function () {
        return this.data
    }
};

function BST() {
    this.root = null;
    this.insert = function (data) {                 // 插入数据
        var n = new Node(data, null, null);     // 新建节点
        if (this.root == null) {
            this.root = n;                  // 根节点为空，则设为新节点
        } else {
            var current = this.root;
            var parent;
            while (true) {      
                parent = current;                   // 当前父节点为当前节点
                if (data < current.data) {      // 数据小于当前节点数据
                    current = current.left;         // 取左节点
                    if (current == null) {          // 左节点为空
                        parent.left = n;        // 当前父节点的左节点设为新节点
                        break;
                    }
                } else {
                    current = current.right;      // 取右节点
                    if (current == null) {      // 右节点为空
                        parent.right = n;       // 当前父节点的右节点设为新节点
                        break;
                    }
                }
            }
        }
    };
    this.inOrder = function (node = this.root) {            // 中序遍历
        if (!(node == null)) {
            this.inOrder(node.left);
            console.log(node.show());
            this.inOrder(node.right);
        }
    };
    this.preOrder = function (node = this.root) {            // 先序遍历
        if (!(node == null)) {
            console.log(node.show());
            this.preOrder(node.left);
            this.preOrder(node.right);
        }
    };
    this.postOrder = function (node = this.root) {          // 后序遍历
        if (!(node == null)) {
            this.postOrder(node.left);
            this.postOrder(node.right);
            console.log(node.show());
        }
    };
    this.getMin = function () {                             // 查找最小值
        var current = this.root;
        while (!(current.left == null)) {
            current = current.left;
        };
        return current.data
    };
    this.getMax = function () {                             // 查找最大值
        var current = this.root;
        while (!(current.right == null)) {
            current = current.right;
        };
        return current.data;
    };
    this.find = function (data) {                           // 查找节点
        var current = this.root;
        while (!(current == null)) {
            if (current.data == data) {
                return current;
            } else if (data < current.data) {
                current = current.left;
            } else {
                current = current.right;
            }
        };
        return null
    };

    this.getSmallest = function (node) {            // 返回当前节点树的最小节点
        while (!(node.left == null)) {
            node = node.left
        };
        return node
    };

    this.removeNode = function (data, node = this.root) {      // 去除特定节点
        if (node == null) {
            return null;
        };

        if (data == node.data) {
            // 没有子节点的节点
            if (node.left == null && node.right == null) {
                return null;
            };
            // 没有左节点的节点
            if (node.left == null) {
                return node.right;
            };
            // 没有右节点的节点
            if (node.right == null) {
                return node.left;
            };
            // 有两个子节点的节点
            var tempNode = this.getSmallest(node.right);        // 当前节点下的最小节点
            node.data = tempNode.data;                      // 当前节点数据设为最小节点的数据
            node.right = this.removeNode(tempNode.data, node.right);    // 清除最小节点
            return node;
        } else if (data < node.data) {
            node.left = this.removeNode(data, node.left);        // 在左子树中删除特定节点
            return node;
        } else {
            node.right = this.removeNode(data, node.right);     // 在右子树中删除特定节点
            return node
        }
    }

}

图

图由边的集合及顶点的集合组成。边由顶点对(v1,v2)定义，v1和v2分别是图中的两个顶点。顶点也有权重，也称为成本。如果一个图的顶点对是有序的，则可以称之为有向图 。在对有向图中的顶点对排序后，便可以在两个顶点之间绘制一个箭头。有向图表明了顶点的流向。

如果图是无序的，则称之为无序图 ，或无向图。

图中的一系列顶点构成路径 ，路径中所有的顶点都由边连接。路径的长度用路径中第一个顶点到最后一个顶点之间边的数量表示。由指向自身的顶点组成的路径称为环，环的长度为0。

圈是至少有一条边的路径，且路径的第一个顶点和最后一个顶点相同。无论是有向图还是无向图，只要是没有重复边或重复顶点的圈，就是一个简单圈 。除了第一个和最后一个顶点以外，路径的其他顶 点有重复的圈称为平凡圈 。

如果两个顶点之间有路径，那么这两个顶点就是强连通的，反之亦然。如果有向图的所有的顶点都是 强连通的，那么这个有向图也是强连通的。

function Graph(v) {
    this.vertices = v;          // 顶点数
    this.edges = 0;             // 边的数量

    this.adj = [];              // 记录顶点与边的分布
    for (var i = 0; i < this.vertices; i++) {        // 每个顶点一个数组记录相邻的点
        this.adj[i] = [];
        //this.adj[i].push("");
    };

    this.marked = [];               // 记录顶点有无被遍历到
    for (var i = 0; i < this.vertices; i++) {        // 全部顶点先设未被遍历到
        this.marked[i] = false
    };

    this.edgeTo = [];               // 保存从一个顶点到下一个顶点的所有边

    this.addEdge = function (v, w) {    // 新增边，v -> w
        this.adj[v].push(w);
        this.adj[w].push(v);
        this.edges++;
    };
    this.showGraph = function () {                      // 遍历图
        for (var i = 0; i < this.vertices; i++) {
            for (var j = 0; j < this.vertices; j++) {
                if (this.adj[i][j] !== undefined) {
                    console.log(i + " -> " + this.adj[i][j] + '  ');
                }
            }
        }
    };

    this.dfs = function (v) {                           // 深度优先遍历
        this.marked[v] = true;                      // 当前顶点设为已遍历
        if (this.adj[v] != undefined) {                 // 当前顶点有边
            for (var i = 0; i < this.adj[v].length; i++) {       // 遍历连接的顶点
                console.log(v + ' -> ' + this.adj[v][i])
                if (!this.marked[this.adj[v][i]]) {     // 连接的顶点未遍历过
                    this.dfs(this.adj[v][i])            // 遍历顶点
                }
            }
        }
    };

    this.bfs = function (v) { // 广度优先遍历
        var queue = [];             // 记录遍历顶点的队列
        this.marked[v] = true;          // 记录当前顶点已遍历
        queue.push(v);              // 当前顶点添加到队尾
        while (queue.length > 0) {
            var w = queue.shift()         // 取队首顶点
            if (this.adj[w] != undefined) {     // 顶点的边数组不为空
                for (var i = 0; i < this.adj[w].length; i++) {      // 遍历连接的节点
                    console.log(w + ' -> ' + this.adj[w][i]);
                    if (!this.marked[this.adj[w][i]]) {         // 遍历到的节点还没遍历过
                        this.marked[this.adj[v][i]] = true;     // 标记遍历
                        queue.push(w);                  // 加入队列
                    }
                }
            }
        }
    };

    this.hasPathTo = function (v) {             // 判断有无到此顶点的边
        return this.edgeTo[v]
    }

    this.pathTo = function (v) {
        var source = 0;
        if (!this.hasPathTo(v)) {           // 无边连接此顶点
            return undefined;
        };
        var path = [];                      // 记录路径
        for (var i = v; i != source; i = this.edgeTo[i]){   // 根据路径查找，直到0即开始的顶点
            path.push(i);                   // 途经的顶点入栈
        };
        path.push(source);                  // 顶点也入栈
        return path;        
    }
};

排序算法

排序和检索在计算机中使用得非常多，以下介绍常用排序算法。

为了后面的操作，先定义一个常用函数：

function swap(data, index1, index2) {       // 调换两项数据
    temp = data[index1];
    data[index1] = data[index2];
    data[index2] = temp;
}

冒泡排序

冒泡排序是最慢的排序算法之一，但也是一种最容易实现的排序算法。

之所以叫冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，较大的值 会浮动到数组的右侧，而较小的值则会浮动到数组 的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换。

function bubbleSort(data) {
    var numElements = data.length;                      // 数组长度
    for (var outer = numElements; outer > 1; outer--) {      // 一轮把一个最大的数沉底
        for (var inner = 0; inner < outer; inner++) {    // 把当前最大的数沉到outer-1的位置
            if (data[inner] > data[inner + 1]) {
                swap(data, inner, inner + 1);          // 换数
            }
        }
    }
}

选择排序

选择排序从数组的开头开始，将第一个元素和其他元素进行比 较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。

function selectionSort(data) {
    var min;                    // 记录每一轮选择的最小值
    for (var outer = 0; outer < data.length - 1; outer++){              // 外循环
        min = outer;                                            // 初始最小值设为outer
        for (var inner = outer + 1; inner < data.length; inner++){      // 内循环，从outer+1至数组尾部
            if (data[inner] < data[min]) {              // inner值小于当前最小值
                min = inner;                    // 记录最小值
            }
        };
        swap(data, outer, min);                 // 换数
    }
}

插入排序

插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动， 为内循环中的这个元素腾出位置。

function insertionSort(data) {
    var temp;                           // 外循环取出的数
    var inner;                              // 内循环指针
    for (var outer = 1; outer < data.length; outer++){      // 外循环，每次拿出一个数
        temp = data[outer];                         // 暂时取出的数
        inner = outer;                              // 指针
        while (inner > 0 && (data[inner - 1] >= temp)) {    // 指针前一个数比temp大
            data[inner] = data[inner - 1];                  // 移动前一个数到当前指针位置，前一个数的位置空出
            inner--;                                        // 指针--
        };
        data[inner] = temp;                             // 赋值到指针位置
    }
}

希尔排序

希尔排序在插入排序的基础上做了很大的改善。希尔排序的核心理念与插入排序不同，它会首先比较距离较远的元素，而非相邻的元素。和简单地比较相邻元素相比，使用这种方案可以使离正确位置很远的元素更快地回到合适的位置。当开始用这个算法遍历数据集时，所有元素之间的距离会不断减小，直到处理到数据集的末尾，这时算法比较的就是相邻元素了。

function shellSort(data) {
    var gaps = [5, 3, 1];                   // 间隔数组
    for (var g = 0; g < gaps.length; g++) {
        for (var i = gaps[g]; i < data.length; i++) {
            var temp = data[i];
            for (var j = i - gaps[g]; j >= 0 && data[j] >= temp; j -= gaps[g]) {
                data[j + gaps[g]] = data[j];
            };
            data[j + gaps[g]] = temp;
        }
    }
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

function merge(leftArr, rightArr){  
    var result = [];  
    while (leftArr.length > 0 && rightArr.length > 0){  
      if (leftArr[0] < rightArr[0])  
        result.push(leftArr.shift()); //把最小的最先取出，放到结果集中   
      else   
        result.push(rightArr.shift());  
    }   
    return result.concat(leftArr).concat(rightArr);  //剩下的就是合并，这样就排好序了  
}  

function mergeSort(array){  
    if (array.length == 1) return array;  
    var middle = Math.floor(array.length / 2);       //求出中点  
    var left = array.slice(0, middle);               //分割数组  
    var right = array.slice(middle);  
    return merge(mergeSort(left), mergeSort(right)); //递归合并与排序  
} 

快速排序

快速排序通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。

这个算法首先要在列表中选择一个元素作为基准值（pivot）。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部。

function qSort(data) {
    if (data.length == 0) {
        return []
    };
    var lesser = [];                            // 比基准小的数
    var greater = [];                           // 比基准大的数
    var pivot = data[0];                        // 取第一个数作为比较基准
    for (var i = 1; i < data.length; i++) {      // 遍历进行比较分组
        if (data[i] < pivot) {
            lesser.push(data[i]);
        } else {
            greater.push(data[i]);
        }
    };
    return qSort(lesser).concat(pivot, qSort(greater));     // 递归分组，拼接结果返回
}

检索算法

顺序查找

顺序查找面向数据无顺序，即循环查找
而查找最大或最小值时，可以设立一个min或max作为标志，遍历一轮即可找出需要的值。

二分查找

如果你要查找的数据是有序的，二分查找算法比顺序查找算法更高效。

function binSearch(arr, data) {
    var upperBound = arr.length - 1;        // 尾部指针
    var lowerBound = 0;                     // 头部指针
    var mid;                                // 中间指针
    while (lowerBound <= upperBound) {              // 当头部指针小于等于尾部指针
        mid = Math.floor((upperBound + lowerBound) / 2);    // 取中间指针
        if (arr[mid] == data) {
            return mid                          // 找到数据
        } else if (arr[mid] > data) {       
            upperBound = mid - 1;           // 中间指针数据大，重取尾部指针
        } else {
            lowerBound = mid + 1;           // 中间指针数据小，重取头部指针
        }
    };

    return -1                           // 找不到
}

高级算法

动态规划

动态规划有时被认为是一种与递归相反的技术。 递归是从顶部开始将问题分解，通过解决掉所有分解出小问题的方式，来解决整个问题。动态规划解决方案从底部开始解决问题，将所有小问题解决掉，然后合并成一个整体解决方案，从而解决掉整 个大问题。

从基础的斐波那契函数来看递归和动态规划的区别，递归实现如下：

// 递归实现斐波切纳函数
function recurFib(n) {
    if (n < 2) {
        return n
    } else {
        return recurFib(n - 1) + recurFib(n - 2);
    }
}

可以通过下图看到函数的执行过程：

很明显有太多值在递归调用中被重新计算。如果编译器可以将已经计算的值记录下来，函数的执行效 率就不会如此差。我们可以使用动态规划的技巧来设计一个效率更高的算法。

// 动态规划实现斐波切纳函数
function dynFib(n) {
    var val = [];
    for (var i = 0; i <= n; i++){
        val[i] = 0;
    };

    if (n == 1 || n == 2) {
        return 1;
    } else {
        val[1] = 1;
        val[2] = 2;
        for (var i = 3; i <= n; i++){
            val[i] = val[i - 1] + val[i - 2];
        };
        return val[n - 1];
    }
}

我们在这个数组val中保存了中间结果。如果要计算的斐波那契数是1或者2，那么if语句会返回1。 否则，数值1和2将被保存在val 数组中1和2的位 置。循环将会从3到输入的参数之间进行遍历，将数组的每个元素赋值为前两个元素之和，循环结 束，数组的最后一个元素值即为最终计算得到的斐波那契数值，这个数值也将作为函数的返回值。

寻找最长公共字串

动态规划是更适合解决这个问题的方案。这个算法使用一个二维数组存储两个字符串相同位置的字符比较结果。初始化时，该数组的每一个元素被设置为0。每次在这两个数组的相同位置发现了匹配， 就将数组对应行和列的元素加1，否则保持为0。

按照这种方式，一个变量会持续记录下找到了多少个匹配项。当算法执行完毕时，这个变量会结合一个索引变量来获得最长公共子串。

// 动态规划查找最长公共字串
function lcs(word1, word2) {
    var max = 0;
    var index = 0;
    var lcsarr = new Array(word1.length + 1);
    for (var i = 0; i <= word1.length + 1; i++) {
        lcsarr[i] = new Array(word2.length + 1);
        for (var j = 0; j <= word2.length + 1; j++) {
            lcsarr[i][j] = 0;
        }
    };

    for (var i = 0; i <= word1.length; i++) {
        for (var j = 0; j <= word2.length; j++) {
            if (i == 0 || j == 0) {
                lcsarr[i][j] = 0;
            } else {
                if (word1[i - 1] == word2[j - 1]) {
                    lcsarr[i][j] = lcsarr[i - 1][j - 1] + 1;
                } else {
                    lcsarr[i][j] = 0;
                }
            };
            if (max < lcsarr[i][j]) {
                max = lcsarr[i][j];
                index = i;
            }
        }
    };

    var str = "";
    if (max == 0) {
        return "";
    } else {
        for (var i = index - max; i <= max; i++) {
            str += word2[i];
        };
        return str;
    }
}

该函数的第一部分初始化了两个变量以及一个二维数组。第二部分构建了用于保存字符匹配记录的表。数组的第一个元素总是被设置为0 。如果两个字符串相应位置的字符进行了匹配，当前数组元素的值将被设置为前一次循环中数组元素保存的值加1。

最后， 如果变量max 的值比现在存储在数组中的当前元素 要小，max的值将被赋值给这个元素，变量index的值将被设置为i 的当前值。这两个变量将在函数的最后一部分用于确定从哪里开始获取最长公共子 串。

最后一部分代码用于确认从哪里开始构建这个最长公共子串。以变量index 减去变量max 的差值作为 起始点，以变量max 的值作为终点：

背包问题

试想你是 一个保险箱大盗，打开了一个装满奇珍异宝的保险
箱，但是你必须将这些宝贝放入你的一个小背包中。保险箱中的物品规格和价值不同。你希望自己的背包装进的宝贝总价值最大。

先通过递归的方法解决问题：

// 递归解决背包问题
function max(a, b) {
    return a > b ? a : b;
};

function knapSack(capacity, size, value, n) {
    if (n == 0 || capacity == 0) {
        return 0;
    };

    if (size[n - 1] > capacity) {
        return knapSack(capacity, size, value, n - 1);
    } else {
        return max(value[n - 1] + knapSack(capacity - size[n - 1], size, value, n - 1), knapSack(capacity, size, value, n - 1));
    }
}

var value = [4, 5, 10, 11, 13];             // 物品价值
var size = [3, 4, 7, 8, 9];                 // 物品所占容量
var capacity = 16;                          // 可带容量
var n = 5;                                  // 物品数量
console.log(knapsack(capacity, size, value, n));

能用递归解决的问题都可以使用动态规划解决，以下是动态规划解决背包问题的方法：

// 动态规划解决背包问题
function max(a, b) {
    return a > b ? a : b;
};

function dKnapsack(capacity, size, value, n) {
    var k = [];
    for (var i = 0; i <= capacity + 1; i++) {
        k[i] = [];
    };

    for (var i = 0; i <= n; i++) {
        for (var w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0) {
                k[i][w] = 0;
            } else if (size[i - 1] <= w) {
                k[i][w] = max(value[i - 1] + k[i - 1][w - size[i - 1]], k[i - 1][w]);
            } else {
                k[i][w] = k[i - 1][w];
            }
        }
    };

    return k[n][capacity];
}

var value = [4, 5, 10, 11, 13];             // 物品价值
var size = [3, 4, 7, 8, 9];                 // 物品所占容量
var capacity = 16;                          // 可带容量
var n = 5;                                  // 物品数量
console.log(dKnapsack(capacity, size, value, n));

这个问题的最优解可以在二维数组的最后一个单元中找到，即可以在表的右下角找到。

贪心算法

贪心算法总是会选择当下的最优解，而不去考虑这一次的选择 会不会对未来的选择造成影响。使用贪心算法通常表明，实现者希望做出的这一系列局部“最优”选择能够带来最终的整体“最优”选择。

通过贪心算法解决背包问题：
如果放入背包的物品从本质上说是连续的，那么就 可以使用贪心算法来解决背包问题。如果用到的物品是连续的，那么可以简单地通过物品的单价除以单位体积来确定物品的价值。在这种情况下的最优解是，先装价值最高的物品直到该物品装完或者将背包装满，接着装价值次高的物品，直到这种物品也装完或将背包装满，以此类推。我们不能通过贪心算法来解决离散物品问题的原因，是因为我们无法将“半台电视”放入背包。离散背包问题也称为“0-1”问题，因为你必须放入整个物品或者不放入。

这种类型的背包问题被称为部分背包问题。以下算法用于解决部分背包问题。

• 背包的容量为W，物品的价格为v，重量为w
• 根据v/w的比率对物品排序
• 按比率的降序方式来考虑物品
• 尽可能多地放入每个物品

假设我们通过上述方式列出背包物品的数据：

根据上面的表格，假设背包的容量为30，那么这个背包问题的最优解是放入所有物品A、所有物品B和一半的物品C。这个物品组合将得到的价值为 220。

这个问题最优解的代码如下：

// 贪心算法解决部分背包问题
function kSack(values, weights, capacity, n) {
    var load = 0;                               // 拿的总容量
    var i = 0;                                  // 拿的物品种类
    var w = 0;                                  // 拿到的总价值
    while (load < capacity && i < n) {
        if (weights[i] <= (capacity - load)) {       // 可以全拿
            w += values[i];
            load += weights[i];
        } else {                                    // 拿一部分
            var r = (capacity - load) / weights[i];     // 根据所剩容量拿
            w += r * value[i];
            load += weights[i];
        }
        i++;
    };
    return w;
}

var values = [50, 140, 60, 60];
var weights = [5, 20, 10, 12];
var capacity = 30;
var n = 4;
console.log(kSack(values, weights, capacity, n))