前言

JDK1.5，Sun大神（Doug Lea）为我们带来了java.util.concurrent工具包，以简化并发编程。
在concurrent包之前，我们要借助join(),wait()/notify()，synchronized等来实现并发编程，难度较大，也容易出现问题，而concurrent包的到来，我们可以使用线程池（ThreadPoolExecutor）、灵活的可重入锁（ReentrantLock）、原子类（AtomicInteger…）、阻塞队列（ArrayBlockingQueue…）、线程安全Map(ConcurrentMap…)、以及本节会介绍的并发工具（CountDownLatch、CyclicBarrier…），使得并发编程变得容易了，也增加了很多灵活性。

博客推荐

前言

网上很多文章讲线程状态的，但是多数为了好理解，进行了一定的改变，使得准确性不够。
本文根据Thread类中的枚举类State为切入点，对这一知识点进行总结，通过理解这个知识点，为以后的系统故障排查，JVM调优打下坚实的基础。
在阅读以下内容时，需要了解两个jdk自带的小工具，jps,jstack（后续补充一篇jdk工具的备忘）。

要点

1. 不是jdk自带，需要导入jar包。所需要的jar,cglib-3.0.jar;asm-4.0.jar;asm-util-4.0.jar
2. 由于jdk动态代理要求，被代理类和代理类要实现同一个接口，当无接口时，就需要使用到cglib动态代理。
3. 原理是：通过字节码技术为代理类创建子类，并在子类中采用方法拦截的技术拦截所有父类方法的调用，顺势织入横切逻辑。
4. cglib的性能高于jdk动态代理，但是cglib创建代理对象时间较长，所以对于单例的对象，因为无需频繁创建对象，用CGLib合适。
5. 由于CGLib由于是采用动态创建子类的方法，对于final方法，无法进行代理。

最近写前端页面比较多，屏幕适配比较麻烦，写一堆的@media,min-width等，经同事指导，使用了css3的rem，感觉不能再爽了！！！

Java通过Proxy类实现的动态代理，使用上是比较简单的，但是内部实现比较复杂，这里是一个思路整理。

//1.真实对象
RealSubject realSubject = new RealSubject();
//handler对象
InvocationHandler handler = new DynamicSubject(realSubject);
//代理对象
Subject subject = (Subject) Proxy.newProxyInstance(classType.getClassLoader(),
                  realSubject.getClass().getInterfaces(),handler);
//代理对象执行方法                  
subject.work();

（主要是针对网友博客的理解，后续自己深入研究源码）

• Proxy.newProxyInstance()方法，通过参数一（loader）,参数二（真实类的接口数组），动态生成一个代理类$Proxy0,继承了Proxy,实现Subject(真实类的接口数组)。

public final class $Proxy0 extends Proxy implements Subject

• 返回的代理对象subject是Subject接口类型的对象，该对象会有Subject接口中定义的work()方法，所以可以执行subject.work();

• 类$Proxy的work方法实现如下,调用了我们在Proxy.newProxyInstance()方法的第三个参数（handler）的invoke方法，至此，即是调用了我们在实现InvocationHandler接口时，自己写的逻辑（h.invoke()）。

super.h.invoke(this, m3, null);

• 需要解释的是，$Proxy继承了Proxy，在调用Proxy.newProxyInstance()生成代理对象时，第三个参数会通过构造方法注入到代理对象中，从而会有上一步的h.invoke()执行。

代码：

public $Proxy0(InvocationHandler invocationhandler)
{
  super(invocationhandler);
}
========================================================
class Proxy
{
   protected InvocationHandler h;
   protected Proxy(InvocationHandler h) 
   {
         this.h = h;
   }
}

• 动态生成$Proxy0，这块应该是源码研究的难点，后续自己可以挑战下。

代码展示

package com.kevinlsui.proxy;

public interface Subject {
    void work();
}

package com.kevinlsui.proxy;

public class RealSubject implements Subject{
    @Override
    public void work() {
        System.out.println("需要代理的方法...");

    }
}

package com.kevinlsui.proxy;

import java.lang.reflect.InvocationHandler;
import java.lang.reflect.Method;
import java.lang.reflect.Proxy;

public class ProxyHandler implements InvocationHandler{

    Object object ;
    public Object blind(Object obj){
        object = obj;
        return Proxy.newProxyInstance(this.getClass().getClassLoader(), obj.getClass().getInterfaces(), this);
    }


    @Override
    public Object invoke(Object proxy, Method method, Object[] args)
            throws Throwable {
        System.out.println("真正执行前，做一些处理，比如日志记录");
        Object obj = method.invoke(object, args);//实际执行的方法
        System.out.println("真正执行后，做一些处理");
        return obj;
    }

}

package com.kevinlsui.proxy;

public class ProxyTest {

    public static void main(String[] args) {
        RealSubject real = new RealSubject();//实际业务代码
        ProxyHandler handler = new ProxyHandler();//帮助类，把切片方法写在这个类中
        //代理类的对象，动态生成的代理类实现Subject接口，继承Proxy类，在生成对象时，把handler对象作为属性注入到代理对象
        Subject proxy = (Subject) handler.blind(real);
        //在代理对象执行对应方法时，实际是使用handler中的invoke方法，达到代理的效果。
        proxy.work();
    }

}

入门博客

推荐博客1

题目

01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为C1，C2，…，Cn，与之相对应的价值为W1,W2，…，Wn.求解将那些物品装入背包可使总价值最大。

代码

package com.kevinlsui.dp;

/*
 * 动态规划：01背包问题
 * 入门博客：http://m.blog.csdn.net/article/details?id=7722810
 */
public class DpTest {

    public static void main(String[] args) {
        int m = 10;//背包总容量10
        int n = 3; //待选物品为3个
        int[] w = {3,4,5}; //三个物品的容量数组
        int[] p = {4,5,6};//三个物品的价值数组

        int[][]  c = bulidArry(m,n,w,p);//c[n][m]表示n个物品，m容量的背包最大价值
        System.out.println("最佳方案："+c[2][10]);//i下标从零开始的
        System.out.println("数组展示：");
        for(int i = 0;i<n;i++){
            for(int j = 0; j<m ; j++){
                System.out.print(c[i][j]+" ");
            }
            System.out.println();
        }

    }

    /*
     * c[n][m]表示n个物品，m容量的背包最大价值
     * 
     */
    private static int[][] bulidArry(int m, int n, int[] w, int[] p) {


        int[][] c = new int[n][m+1];//着重解释，此处必须是m+1，因为后续计算需要用到背包容量等于0时的数据,故有m+1列
        for(int k = 0;k < n;k++){
            c[k][0] = 0;
        }


        /*
         * 以下循环解释：
         * 1.只有物品1，背包的容量从0到10，分别的最大价值（后面的计算会用到）
         * 2.有物品1，物品2，背包的容量从0到10，分别的最大价值
         * 3.物品1,2,3，背包的容量从0到10，分别的最大价值
         * 其中，核心理解：
         * 对于c[i][j]的最大价值，
         * 我可以不放这物品，把资源（背包空间）留给(i-1)个物品，看下最大价值c[i-1][j]；
         * 也可以放这个物品（如果能放下），获得价值p[i],但是占用资源w[i]，留给（i-1）个物品，资源剩下(j-w[i]),此时的最大价值为 p[i]+c[i-1][j-w[i]]
         * 比较这两种方式哪一个更优
         */
        for(int i = 0;i < n ;i++){
            for(int j= 1;j < m+1;j++){//j从1开始
                if(i==0){//第一行
                    if(w[i] > j){
                        c[i][j] = 0;
                    }else{
                        c[i][j] = p[i];
                    }
                }else{//从第二行开始
                    if(w[i] > j){//放不下物品i,此时直接就是：把资源（背包空间）留给(i-1)个物品，看下最大价值c[i-1][j]
                        c[i][j] = c[i-1][j];
                    }else{//两种情况比较
                        c[i][j] = c[i-1][j] > c[i-1][j-w[i]]+p[i] ? c[i-1][j]:c[i-1][j-w[i]]+p[i];
                    }

                }

            }

        }

        return c;
    }

}

结果

最佳方案：11
数组展示：
0 0 0 4 4 4 4 4 4 4 4 
0 0 0 4 5 5 5 9 9 9 9 
0 0 0 4 5 6 6 9 10 11 11 

这次解决问题，给我的启发：克服源码恐惧，代码都是人写出来的，敢于阅读源码，敢于修改源码。

Java内存模型的基础

并发编程模型中的两个关键问题

1.线程间如何通信？
通信是指线程之间以何种机制来交换信息。
方法一：共享内存；线程间共享程序的公共状态，通过读写内存中的公共状态进行隐式通信。Java语言就是采用的共享内存模型。
方法二：消息传递。线程之间没有公共状态，线程之间必须通过发送消息来显示进行通信。

2.线程间如何同步？
同步是指程序中用于控制不同线程间操作发生相对顺序的机制。
共享内存并发模型中，同步是显式进行的，程序猿必须显式指定某个方法或者某段代码需要在线程之间互斥执行。
消息传递并发模型中，由于消息的发送必须在消息的接收之前，因此同步是隐式的。

Java的并发是采用的共享内存模型，通信总是隐式进行的，整个通信过程对程序猿是完全透明的。

Java内存模型的抽象结构

由上可知，Java采用的是共享内存模型，所以通信是由Java内存模型（JMM）控制，通过读写内存中的公共状态进行隐式通信，JMM决定一个线程对共享变量的写入何时对另外一个线程可见。

注意：共享变量通常是指存放在堆内存中的实例域、静态域、数组元素。而局部变量、方法定义参数、异常处理参数是不会在线程之间共享的，也就不存在相应的线程安全问题。

JMM定义了线程和主内存之间的抽象关系：
线程之间的共享变量存储在主内存中，每个线程都有各自的一个私有的本地内存，本地内存中存储了该线程用到的读写共享变量的副本。

通信过程：线程A修改本地内存中的共享变量副本，同步到主内存中，线程B读取主内存中的共享变量到自己的本地内存，从而实现读写内存中的公共状态进行隐式通信。

从源代码到指令序列的重排序

在执行程序时，为了提高性能，编译器和处理器常常会对指令做重排序。

1. 编译器优化的重排序；编译器在不改变单线程程序语义的前提下，重新安排语句顺序
2. 指令级并行的重排序；
3. 内存系统的重排序。

上述的1属于编译器重排序，23属于处理器重排序。
在多线程环境，重排序可能会导致内存可见性问题，也就是出现一些错误。
对于编译器重排序，JMM的编译器重排序规则会禁止特定类型的编译器重排序。
对于处理器重排序，JMM的处理器重排序规则会要求Java编译器在生成指令序列时，插入特定类型的内存屏障指令，通过该内存屏障来禁止特定类型的处理器重排序。

注意：java是一次编译，到处运行的语言，所以对于JMM这一语言级别的内存模型，它确保在不同的编译器和不同的处理器平台上，通过禁止特定类型的编译器重排和处理器重排序，为程序猿提供一致的内存可见性保证。

并发编程模型的分类

现代的处理器，使用写缓冲区临时保存向内存写入的数据。写缓冲区可以保证指令流水线持续运行，避免由于处理器停顿下来等待向内存写入数据而产生的延迟。同时，通过以批处理的方式刷新写缓冲区，以及合并写缓冲区中对同一内存地址的多次写，减少对内存总线的占用。
虽然写缓冲区有这么多好处，但是每个处理器上的写缓冲区，仅仅对他所在的处理器可见，这一特性对内存操作的执行顺序产生重要的影响：处理器对内存的读、写操作的执行顺序，不一定与内存实际发生的读写操作顺序一致。
示例中的，由于存在以上特性，导致x=y=0。

也是由于现代的处理器都会使用写缓冲区，因此现代的处理器都会允许对写-读操作进行重排序。（都不允许对存在数据依赖的操作做重排序。）

为了保证内存的可见性，也就是不出现上述的重排序带来的不良影响，Java编译器在生成指令序列的适当位置会插入内存屏障指令来禁止特定类型的处理器重排序。
JMM把内存屏障指令分为4类，LoadLoad Barriers;StoreStore Barriers;LoadStore Barriers;StoreLoad Barriers。其中最后一个，StoreLoad Barriers 是一个全能的屏障，它同时支持其他三个屏障的效果，也是现在大多数处理器都支持的。
但是执行该屏障开销昂贵，因为当前处理器通常要把写缓冲区的数据全部刷新到内存中。

happens-before简介

Java多线程技能

• 进程是操作系统结构的基础，是一次程序的执行，是一个程序及其数据在处理机上顺序执行时所发生的活动，是程序在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位。
• 生活中，我们可以简单的把一个运行中的exe程序理解成“进程”
• 线程是在进程中独立运行的子任务，一个进程正在运行时至少会有一个线程。
• 关于进程与线程的解释，可以看这篇文章
• 疑问：一个jvm进程中有多个线程，多核的cpu，某一个时刻，某一cpu可以运行某一进程，是不是说这多个线程只能在某一个核的该jvm进程的时间片内运行？网友解释
• Thread.currentThread().getName();当前线程名
• 实现线程，1.继承Thread 2.实现Runnable,java单继承的原因，优先考虑实现接口
• public class Thread implements Runnable ; 类Thread源码中继承了Runnable接口
• 使用多线程时，代码顺序并不是实际执行顺序，启动多个线程（start方法），cpu空闲时会随机选取一个准备好的线程运行。
• 启动线程，必须调用start(),如果直接thread.run(),则不会开一个新的线程，直接是在main线程中运行
• Thread类的构造方法，Thread(Runnable target),不光可以传入Runnable接口的对象，也可以传入一个Thread类的对象，这样做是相当于将一个Thread对象中的run方法交由其他的线程进行调度。
• 普通方法加synchronized关键字，提供是一个对象锁
• static方法加synchronized关键字，提供的是class锁
• isAlive()判断当前线程是否存活
• sleep(s)的作用是让当前正在执行的线程休眠s秒，不交出所获得的锁。
• getId()是去的线程的唯一标识
• 停止线程。方法一：Thread.stop()方法已经被废弃，最好不用，原因是暴力停止的不安全，可能导致一些资源没有释放，带来死锁。并且，调用stop(),会产生ThreadDeath异常。方法二：Thread.interrupt()方法，推荐方法。方法三：设置退出标志，使得正常退出，也就是当run方法运行完后线程终止
• thread.interrupt()将某个线程终止，含义是：将这个线程的中断标志设置为true,具体去终止线程，需要在该线程中去判断这个中断标志，然后结束代码
• 判断线程是否中断，static interrupted(),静态方法，无论调用者是谁，都返回的是当前线程的中断状态，具体表现是，在main方法中，thread.interrupted(),具体线程thread是已经调用中断的，返回false,即返回是main线程的中断状态；另外一个特点是，调用一次本方法，中断标志会复位为false
• isInterrupted(),不是static,调用者的中断状态，也没有擦除效果，一般使用这个方法。
• 在线程内部，通过查看中断标志为true后，可以抛出一个异常，达到后续代码不运行的目的
• 同上，可以使用return达到同样目的
• 在线程sleep状态下中断，会进入catch语句，并清除中断标志，变为false
• 线程中断后，再遇到sleep方法，会进入异常代码
• suspend()暂停，resume()恢复。均废弃
• yield(),放弃cpu资源，时间未知。
• setPriority()设置线程优先级，优先级具有随机性
• thread.setDaemon(true),将thread设置为守护线程，从而main结束时thread也结束

对象及变量的并发访问

• 方法内部的变量，是线程安全的。因为每个线程调用这个方法时都会创建一份私有变量。
• 多个线程访问同一个对象的实例变量（属性），则存在“非线程安全”问题。
• 多个线程访问多个对象（同一个class的对象）的static(静态)变量，则存在“非线程安全”问题。
• 多个线程，访问同一个对象的同步（synchronized）普通方法，同一时间，只有一个线程可以执行该方法，是同步的，是线程安全的
• 多个线程，访问多个对象（同class）的同一个同步（synchronized）方法,是异步的，由于每个对象一个同步锁。即同步普通方法锁的对象。
• 多线程环境，某一线程获取同步方法的锁（对象锁），其它线程可以访问该对象的非同步方法。
• 多线程环境，某一线程获取某一同步方法的锁（对象锁），其它线程不能访问该对象的其它同步方法。即同一个对象，多个同步方法是用的同一个对象锁。
• 关键字synchronized拥有锁重入的功能：当一个线程获取到该对象的锁，执行代码过程中，再次获取锁是可以的，即一个同步方法中再去调用该对象其它同步方法，是可以的。自己可以获取自己内部的锁
• 如果关键字synchronized不具备锁重入功能，则可能造成 死锁。
• 当存在父子类继承关系时，子类是完全可以通过“可重入锁”调用父类的同步方法，这是由于java的继承特性。
• 当一个线程执行的代码出现异常，其所持有的锁会自动释放。
• synchronized同步代码块（同步语句块），相比同步方法，会灵活点
• synchronized(this){//coding};也是对象锁
• synchronized(任意对象非this){//coding}；锁的是（）中的对象，多线程竞争同一个对象，则同步。
• synchronized(任意对象非this){//coding}；解决了前两种，同一对象只用一个锁的问题，增加了灵活性
• 静态同步方法（static synchronized）、synchronized(Class.class),锁的是class,与普通同步方法的对象锁不是同一个，即同一对象的静态同步方法和普通同步方法是异步的。
• 多线程，多个对象，如果是锁的class,则是同步
• JVM有一个String常量池，使用synchronized(String str){}可能带来一些例外，需要注意。
• 使用jdk自带工具检查死锁情况，cmd,jps(查看进程id列表),jstack pid (查看该进程的情况)
• 内部类，静态内部类的synchronized用法与常规的基本相同
• synchronized(任意对象){}，当这个对象改变了，会出现异步的可能（比如字符串对象，赋新值），但是只是改这个对象的属性，还是同步的
• 关键字volatile，作用一：使变量在多个线程间可见；作用二：禁止指令重排。
• 作用一解释：关键字volatile会强制从公共堆栈中取得变量的值，而不是从线程私有数据栈中取得变量的值。
• volatile的缺点是：不支持原子性
• 可以使用volatile加上原子类，保证多线程安全问题
• 原子类 AtomicInteger…
• 关键字synchronized可以使得多线程访问同一资源具有同步性，而且它还具有将线程工作内存中的私有变量与公共内存中的变量同步的功能，也就是保证了可见性。

等待/通知机制

• 多线程之间可以通过共享变量，来实现通信，但是不够灵活。
• 等待/通知机制，wait(),notify()…
• wait(),是object的方法，该方法用来将当前线程置入“预执行队列”，并且在调用wait的代码行处停止执行，直到接到通知或者被中断。
• 调用wait前必须获取到该对象的对象级别锁，调用时会释放该锁，若无锁调用，会抛出异常，IllegalMonitorStateException。
• notify()也是object的方法，如果有多个线程等待，则由线程规划器随机挑选其中一个呈现wait的线程，对其发出notify通知，使其可以进去等待锁的状态。
• notify调用前，线程也必须获取该对象的对象级别的锁，否则抛出IllegalMonitorStateException。
• 调用notify后，不能及时释放锁，必须等该线程执行完。
• notifyAll(),唤醒所有等待这一共享资源的线程。
• wait状态的线程，被中断interrupt(),会抛出异常
• wait(long),等待long指定的时间，如果期间没有被唤醒，则超出这个时间自动唤醒
• 消费者和生产者问题
• 通过管道进行线程间的通信：PipedInputStream PipedInputStream PipedReader PipedWriter
• join()方法
• ThreadLocal的使用

Lock的使用

定时器的使用

单例模式与多线程

拾遗增补

列表：

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

            }
        }

    }
}