列表：

1. 快速排序
2. 归并排序
3. 冒泡排序
4. 简单选择排序
5. 直接插入排序
6. 希尔排序
7. 堆排序
8. 字符串匹配的朴素算法
9. kmp模式匹配算法
10. 逆波兰式运算
11. 逆波兰式生成
12. 斐波那契数列
13. 树的遍历（先序，中序，后序）
14. 图的遍历（BFS/DFS）

//快速排序
function quickSort(arr,min,max){
    if(min < max){
        var len1 = min;
        var len2 = max;

        //选取基数优化（首尾中间值，取中间大小的值）
        var mid = min + Math.floor((max-min)/2)
        if(arr[mid] > arr[max]){
            arr[max] = arr[mid]+arr[max];
            arr[mid] = arr[max]-arr[mid];
            arr[max] = arr[max]-arr[mid];
        }
        if(arr[min] > arr[max]){
            arr[max] = arr[min]+arr[max];
            arr[min] = arr[max]-arr[min];
            arr[max] = arr[max]-arr[min];
        }
        if(arr[mid] > arr[min]){
            arr[min] = arr[mid]+arr[min];
            arr[mid] = arr[min]-arr[mid];
            arr[min] = arr[min]-arr[mid];
        }

        //基数左右两侧排序
        var temp = arr[min];
        while(min<max){

            while(min < max && arr[max] >= temp){
                max--;
            }
            arr[min] = arr[max];

            while(min<max && arr[min] <= temp){
                min++;
            }
            arr[max] = arr[min];


        }
        arr[min] = temp;

        //递归
        quickSort(arr,len1,min-1);
        quickSort(arr,min+1,len2);
    }

}

var a = [12,2,69,1,27,111,19,15,100,1];
quickSort(a,0,a.length-1);
for(var i in a){
console.log(a[i]);
}

//归并排序

function mergeSort(arr,min,max){
    if(min < max){//临界条件
        var mid = min+Math.floor((max-min)/2);
        mergeSort(arr,min,mid);
        mergeSort(arr,mid+1,max);
        merge(arr,min,mid,max);

    }

}
function merge(arr,min,mid,max){
    var temparr = [];
    var tempindex = min;
    var min2 = min;
    var right = mid+1;
    while(min<=mid && right <= max){
        if(arr[min]<=arr[right]){
            temparr[tempindex++] = arr[min++];
        }else{
            temparr[tempindex++] = arr[right++];
        }
    }

    while(min <= mid){
        temparr[tempindex++] = arr[min++];
    }
    while(right <= max){
        temparr[tempindex++] = arr[right++];
    }

    while(min2<= max){
        arr[min2] = temparr[min2++];
    }

}

var a = [12,2,69,1,27,111,19,15,100,1];
mergeSort(a,0,a.length-1);
for(var i in a){
console.log(a[i]);
}

//冒泡排序
function Sort1(arr){
    var len = arr.length;
    if(len > 1){
        var flag = true; //优化
        for(var i = 0 ; i < len && flag;i++){
            flag = false;
            for(var j = 0 ; j < len-i-1;j++){

                if(arr[j] > arr[j+1]){
                    arr[j] = arr[j]^arr[j+1];
                    arr[j+1] = arr[j]^arr[j+1];
                    arr[j] = arr[j]^arr[j+1];
                    flag = true;

                }
            }
        }

    }

}
var a = [12,2,69,1,27,111,19,15,100,1];
Sort1(a);
for(var i in a){
console.log(a[i]);
}

//简单选择排序

function Sort2(arr){
    var len = arr.length;
    if(len > 1){
        for(var i = 0 ; i < len-1; i++){
            var k = i;
            for(var j = i+1; j < len ; j++){
                if(arr[j] < arr[k]){
                    k = j;
                }

            }

            if(i != k){
                arr[i]  = arr[k]^arr[i];
                arr[k]  = arr[k]^arr[i];
                arr[i]  = arr[k]^arr[i];
            }


        }
    }
}
var a = [12,2,69,1,27,111,19,15,100,1];
Sort2(a);
for(var i in a){
console.log(a[i]);
}

//直接插入排序
function Sort3(arr){
    var len = arr.length;
    if(len > 1){
        var j ;
        for(var i = 1;i<len;i++){
            var temp = arr[i];

            for(j = i-1;j >= 0; j--){
                if(arr[j] > temp){
                    arr[j+1] = arr[j];
                }else{
                    bleak;
                }
            }
            if((j+1) != i){

                arr[j+1] = temp;
            }

        }


    }

}

var a = [12,2,69,1,27,111,19,15,100,1];
Sort3(a);
for(var i in a){
console.log(a[i]);
}

//希尔排序
function shellSort(arr){
    var len = arr.length;
    if(len > 1){
        var gap = 1;
        while(gap < len/5){
            gap = gap*5 +1;
        }

        for(gap;gap>0;gap = Math.floor(gap/5)){
            for(var i = gap;i<len;i++){
                var temp = arr[i];
                var j;
                for(j=i-gap;j>=0;j-=gap){
                    if(arr[j]>temp){
                        arr[j+gap] = arr[j];
                    }else{
                        break;
                    }

                }
                if(j+1 != i){
                    arr[j+gap] = temp;
                }

            }

        }

    }

}
var a = [12,2,69,1,27,111,19,15,100,1];
shellSort(a);
for(var i in a){
console.log(a[i]);
}

//堆排序

function HeapSort(arr){
    var len = arr.length;
    if(len > 1){
        //构建最大堆,完全二叉树的性质，这里是遍历所有的含有子结点的结点，从最低层，最右边开//始，直到根结点。
        for( var i = Math.floor(len/2)-1;i>=0;i--){
            heapify(arr,i,len);
        }

        //排序
        for(var j = len-1 ; j > 0 ; j--){
            //已有的最大堆，把最大点（根节点）和最后的一个结点互换
            var temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;

            //此时，最后的节点换到根节点位置，需要调整最大堆
            heapify(arr,0,--len);
        }
    }
}

function heapify(arr,i,len){
    var left = 2*i+1,right = 2*i+2,largest = i,temp;

    //下标为i的节点，比较他本身，左孩子，右孩子，如果孩子比父节点的大，则交换，并对交换到下方的这个节点继续做判断（递归本方法）
    if(left < len && arr[left] > arr[i]){
        largest = left;
    }

    if(right < len && arr[right] > arr[largest]){
        largest = right;
    }

    if(largest != i){
        temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr,largest,len);
    }
}



//字符串匹配的朴素算法
//长字符串s，从下标pos处开始，查找后续是否存在字符串t(仅第一匹配成功的),返回匹配成功的下标，否则返回-1
function indexof(s,t,pos){
    var slen = s.length;
    var tlen = t.length;
    for(var i = pos;i<=slen-tlen;i++){
        var j ;
        for(j=0;j<tlen;j++){
            if(s.charAt(i+j) != t.charAt(j)){
                break;
            }
        }
        if(j==tlen){
            return i;
        }

    }
    return -1;
}
indexof('ksdfnnksf','nk',0);

//第二种写法，便于后续理解kmp匹配算法
function indexof2(s,t,pos){
    var slen = s.length;
    var tlen = t.length;
    var i = pos;
    var j = 0;
    while(i < slen && j < tlen){

        if(s.charAt(i) == t.charAt(j)){
            i++;
            j++;
        }else{
            i = i-j+1;
            j = 0;

        }

    }
    if(j>=tlen){
        return i-tlen;

    }else{
        return -1;
    }
}

indexof2('ksdnfnksf','nk',0);


//kmp模式匹配算法
//相比较于朴素算法，减少不必要的重复比较，使得效率更高
//核心：每轮比较后，使得i不回溯，j值取决于t串内部的重复程度。
function getNext(t){
    var next = [];


}


//逆波兰式运算
//str 是右序表达式的数组
function result(str){
    var len = str.length;

    var stack = [];//数值放入栈，遇到符号，出栈两个数字，计算
    for(var i = 0;i<len;i++){
        if(str[i] != '+' && str[i] != '-' && str[i] != '*' && str[i] != '/'){
            stack.push(str[i]);
        }else{
            var p2 = stack.pop();//注意此处顺序，先pop是被操作数（被加减乘除）
            var p1 = stack.pop();

            switch(str[i]){
                case '+':
                    p1 +=p2;
                    break;
                case '-':
                    p1 -=p2;
                    break;
                case '*':
                    p1 *=p2;
                    break;
                case '+':
                    p1 /=p2;
                    break;

            }
            stack.push(p1);
        }

    }
    return stack.pop();


}
var s = result(["9", "3", "1", "-", "3", "*", "+", "10", "2", "/", "+"]);//20
var s1 = result(["1", "2", "+", "5", "5", "4", "-", "*", "6", "*", "-", "6", "1", "-", "-"]);//-32
console.log(s+"::::"+s1);

//逆波兰式生成
//仅仅考虑+-*/()

function create(arr){
    var result = [];
    var stack = [];

    for(var i = 0 ; i < arr.length;i++){
        var now = arr[i];
        if(isnum(now)){
            result.push(now);//1.数字，直接放入结果数组
        }else{

            //2.符号相关处理
            //2.1.左括号直接压入操作符号栈
            if(now == '('){
                stack.push(now);
            }

            //2.2.右括号，将操作符号栈左括号‘(’之间操作符放入结果数组，抛弃左右括号'('')'
            if(now == ')'){
                var temp = stack.pop();
                while(temp != '('){
                    result.push(temp);//把操作栈中左括号中间的符号输出
                    temp = stack.pop();
                }

            }

            //2.3.加号，减号,乘号，除号
            //2.3.1.栈为空,或者栈顶为左括号‘(’,直接压入
            //2.3.2.比较now和栈顶,当now优先级高于（不包括等于）栈顶，直接压入
            //2.3.3.优先级小于等于栈顶，弹出栈顶压入结果数组，直至栈顶优先级低于（不包括等于）now,或者遇到左括号‘(’,或者操作栈空。此后，将now压入操作符号栈（不是结果数组）
            //此处只考虑，加减乘除。
            if(now == '-' || now == '+' || now == '*' || now == '/'){
                if(stack.length == 0 || stack[stack.length-1] == '('){
                    stack.push(now);
                }else{
                    var temp2 = stack[stack.length-1];

                    if(now == '*' || now == '/'){
                        if(temp2 == '*' || temp2 == '/'){

                        result.push(stack.pop());

                        while(true){
                            if(stack.length == 0){
                                break;
                            }
                            temp2 = stack[stack.length-1];

                            if(temp2 == '(' || temp2 == '+' || temp2 == '-'){
                                break;
                            }
                            result.push(stack.pop());
                        }
                        //压入
                        stack.push(now);

                        }else{//加减，优先级低
                            stack.push(now);
                        }

                    }

                    if(now == '+' || now == '-'){
                        result.push(stack.pop());
                        while(true){
                            if(stack.length == 0){
                                break;
                            }
                            temp2 = stack[stack.length-1];

                            if(temp2 == '('){
                                break;
                            }
                            result.push(stack.pop());
                        }
                        //压入
                        stack.push(now);
                    }

                }
            }




        }

    }
    //stack中全部输出
    while(stack.length>0){
        result.push(stack.pop());
    }
    return result;
}

//是不是数字
function isnum(a){
    if(a == '(' || a == ')' || a == '+' || a == '-' || a == '*' || a == '/'){

        return false;
    }
    return true;
}
//测试
//var h = create('9+(3-1)*3+10/2'.split(''));//数字10被分为1,0
var h = create(['9','+','(','3','-','1',')','*','3','+','10','/','2']);
//h:9 3 1 - 3 * + 10 2 / +
//["9", "3", "1", "-", "3", "*", "+", "10", "2", "/", "+"]

//var h = create('1+2-5*(5-4)*6-(6-1)'.split(''));
//h:1 2 + 5 5 4 - * 6 * - 6 1 - -
//["1", "2", "+", "5", "5", "4", "-", "*", "6", "*", "-", "6", "1", "-", "-"]

//斐波那契数列
//递归
function rabbit(n){
    if(n<0){
        return "error";
    }else if(n<=2){
        return 1;

    }
    return rabbit(n-2)+rabbit(n-1);

}
//非递归
function rabbit2(n){
    if(n<0){
        return "error";
    }else if(n<=2){
        return 1;

    }
    var temp1 = 1;
    var temp2 = 1;
    for(var i = 4;i<=n;i++){
        var temp2 = temp1+temp2;//新的，两数之和
        var temp1 = temp2-temp1;//原始temp2的值
    }
    return temp1+temp2;

}

//树的遍历

//递归
function print1(n){
    console.log("先序遍历，此处对节点进行操作→→→"+n.value);
    print1(n.left);
    //console.log("中序遍历，此处对节点进行操作→→→"+n.value);
    print1(n.right);
    //console.log("后序遍历，此处对节点进行操作→→→"+n.value);

}
//调用,root为根节点
print1(root);

//非递归
function print2(n){
    var arr = [];

    while(n != null || arr.length > 0){
        if(n != null){
            console.log("先序遍历，此处对节点进行操作→→→"+n.value);
            arr.push(n);
            n = n.left;
        }else{
            n = arr.pop();
            //console.log("中序遍历，此处对节点进行操作→→→"+n.value);
            n.right;
        }
    }

}
//先遍历根节点，然后遍历右孩子，最后遍历左孩子。
function print3(n){
    var arr = [];
    var result = [];

    while(n != null || arr.length > 0){
        if(n != null){
            result.push(n);
            arr.push(n);
            n = n.right;
        }else{
            n = arr.pop();

            n.left;
        }
    }

    while(result.length > 0 ){
        console.log("后序遍历非递归操作："+result.pop());
    }
}

//根据先序数组，生成二叉树，abdh##i##e##cf#j##g##

function createTree(){

    var value = '用户依次输入字符';
    if(value != '#'){
        var node = node.value;
        node.left = createTree();
        node.right = createTree();
    }
}



//图的遍历
//邻接矩阵实现,无向图
var vertexs = ['a','b','c','d'];
var flag = [false,false,false,false];
var edges = [
[0,1,1,0],
[1,0,0,1],
[1,0,0,1],
[0,1,1,0]
];

//深度优先递归算法
function DFSTraverse(){
    for(var i = 0;i<vertexs.length;i++){
        if(flag[i] == false){
            DFS(i);
        }

    }

}

function DFS(i){
    flag[i] = true;

    for(int j = 0 ;j< vertexs.length ;j++){
        if(flag[j] == false && edges[i][j] == 1){
            DFS(j);
        }

    }
}

//广度优先算法（队列）

function BFS(){
    var arr = [];//数组模拟队列
    for(var i = 0 ; i < vertexs.length;i++){
        if(!flag[i]){
            flag[i] = true;

            arr.push(i);
            while(arr.length > 0){
                int j = arr.shift();
                for(var k = 0;k<vertexs.length ;k++){
                    if(edges[j][k] == 1 && !flag[k]){
                        flag[k] = true;
                        arr.push(k);
                    }
                }

            }
        }

    }
}