学好算法有饭吃

2018-02-01

数组去重

ES5

Array.prototype.distinct = function() {
    return this.filter(function(v, i) { 
        return this.indexOf(v) === i;
    }, this);
}

ES6

1
2
3

Array.prototype.distinct = function() {
    return Array.from(new Set(this));
}

哈希判断

Array.prototype.distinct = function() {
    var n = {}, r = []; // n为hash表，r为临时数组
    for (var i = 0; i < this.length; i++) {
        if (!n[this[i]]) { // 如果hash表中没有当前项
            n[this[i]] = true; // 存入hash表
            r.push(this[i]); // 把数组的当前项push到临时数组里面
        }
    }
    return r;
}

排序

sort函数

V8引擎中，sort函数给出了两种排序InsertionSort和QuickSort，数量小于10的数组使用InsertionSort，比10大的数组则使用QuickSort。

冒泡排序

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;
}

还有一个改进版。

function bubbleSort2(arr) {
    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; // 为下一趟排序作准备
    }
    return arr;
}

选择排序

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;
}

插入排序

function insertionSort(array) {
    for (var i = 1; i < array.length; i++) {
        var key = array[i];
        var j = i - 1;
        while (array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
    return array;
}

快速排序

function quickSort(array, left, right) {
    if (left < right) {
        // x为本循环的末位值 i用作计数
        var x = array[right], 
            i = left - 1, 
            temp;
        for (var j = left; j <= right; j++) {
            if (array[j] <= x) {
                i++;
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        quickSort(array, left, i - 1);
        quickSort(array, i + 1, right);
    }、
    return array;
}

性能总结

二叉树

一言不合直接上代码~

function BinaryTree (key) {
    let Node = function (key) { // 节点对象
        this.key = key;
        this.left = null;
        this.right= null;
    }
    let root = null; // 根
    // 插入节点
    let insertNode = function (node, newNode) {
        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }
    };
    this.insert = function (key) {
        let newNode = new Node(key);
        if (root === null) { // 第一次
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    };
    // 中序遍历
    let inOrderTraverse = function (node, cb) {
        if (node !== null) {
            inOrderTraverse(node.left, cb); 
            cb(node.key);
            inOrderTraverse(node.right, cb); 
        }
    }
    this.inOrderTraverse = function (cb) {
       inOrderTraverse(root, cb); 
    }
    // 前序遍历（便于复制二叉树，效率高于直接插入的方式）
    let preOrderTraverse = function (node, cb) {
        if (node !== null) {
            cb(node.key);
            preOrderTraverse(node.left, cb); 
            preOrderTraverse(node.right, cb); 
        }
    }
    this.preOrderTraverse = function (cb) {
       preOrderTraverse(root, cb); 
    }
    // 后序遍历
    let postOrderTraverse = function (node, cb) {
        if (node !== null) {
            postOrderTraverse(node.left, cb); 
            postOrderTraverse(node.right, cb); 
            cb(node.key);
        }
    }
    this.postOrderTraverse = function (cb) {
       postOrderTraverse(root, cb); 
    }
    // 查找最小值
    let minNode = function (node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left;
            }
            return node.key;
        }
        return null;
    }
    this.min = function () {
        return minNode(root);
    }
    // 查找最大值
    let maxNode = function (node) {
        if (node) {
            while (node && node.right !== null) {
                node = node.right;
            }
            return node.key;
        }
        return null;
    }
    this.max = function () {
        return maxNode(root);
    }
    // 查找指定值
    let findNode = function (node, key) {
        if (node === null) {
            return false;
        }
        if (key < node.key) {
            return findNode(node.left, key);
        } else if (key > node.key) {
            return findNode(node.right, key);
        } else {
            return true;
        }
    }
    this.find = function (key) {
        return findNode(root, key);
    }
    // 删除节点
    let removeNode = function (node, key) {
        if (node === null) {
            return null;
        }
        if (key < node.key) {
            node.left = removeNode(node.left, key);
            return node;
        } else if (key > node.key) {
            node.right = removeNode(node.right, key);
            return node;
        } else {
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            }
            if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            }
            let aux = findMinNode(node.right);
            node.key = aux.key;
            node.right = removeNode(node.right, aux.key);
            return node;
        }
    }
    let findMinNode = function (node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left;
            }
            return node;
        }
        return null;
    }
    this.remove = function (key) {
        return removeNode(root, key);
    }
}
let nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
let binaryTree = new BinaryTree();
nodes.forEach(function (key) {
    binaryTree.insert(key);
});
let cb = function (key) {
    console.log(key);
};
console.log('中序遍历');
binaryTree.inOrderTraverse(cb);
console.log('前序遍历');
binaryTree.preOrderTraverse(cb);
console.log('后序遍历');
binaryTree.postOrderTraverse(cb);
console.log('最小值', binaryTree.min());
console.log('最大值', binaryTree.max());
console.log(binaryTree.find(1));
console.log(binaryTree.find(100));