[algorithm] 常见的算法 #algorithm

binary-tree.js

// https://zhuanlan.zhihu.com/p/27307626
// 二叉树遍历，有深度优先和广度优先。有递归算法和非递归算法
var nodes = {
    node: 6,
    left: {
      node: 5, 
      left: { 
        node: 4 
      }, 
      right: { 
        node: 3 
      }
    },
    right: { 
      node: 2, 
      right: { 
        node: 1 
      } 
    }
  }

// 深度优先，使用堆栈，先入后出。

// 1 深度优先，先左后右
function btree(nodes){
    let result = [];
    nodes.node && result.push(nodes.node);
    if(nodes.left) {result = result.concat(btree(nodes.left))}
    if(nodes.right) {result = result.concat(btree(nodes.right))}
    return result;
}

// 2 深度优先，不使用递归
// 广度优先，就是有条件，能一直执行下去，while语句
// 不断的取节点使用，不断的
function btree(nodes){
    let result = [];
    let stack = [nodes];
    while(stack.length) {
        let node = stack.pop();
        result.push(node.node);
        if(node.right) {stack.push(node.right)}
        if(node.left) {stack.push(node.left)}
    }
    return result;
}

// 使用队列，先入先出

// 3 广度优先，不使用递归
function btree(nodes){
    let result = [];
    let queue = [nodes];
    let pointer = 0;
    while(pointer < queue.length){
        let node = queue[pointer];
        result.push(node.node)
        if(node.left) { queue.push(node.left) }
        if(node.right) { queue.push(node.right) }
        pointer++;
    }
    return result;
}

var collect = btree(nodes);
console.log(collect);

quick-sort.js

// 其实是分治的思想，快速的分成大小两部分，然后再不断的拆分，通过concat来合并拆分的结果

// 使用递归的方法

function quickSort(arr){
    // 这个arr可能为0，空数组
    if(arr.length <= 1) return arr;
    var povit = arr[arr.length - 1];
    var larger = [];
    var smaller = [];
    for(var i=0;i<arr.length-1;i++) {
        if(arr[i] > povit) {
            larger.push(arr[i]);
        } else {
            smaller.push(arr[i]);
        }
    }
    return quickSort(smaller).concat([povit]).concat(quickSort(larger));
}


let ret = quickSort([7,6,5,4,3,2,1]);
console.log(ret);