/**
 * 归并排序
 * @param array
 * @param left
 * @param right
 */
private static void mergeSort(int []array,int left,int right){
    if(left < right) {
        //分解
        int mid = (left + right) / 2;
        mergeSort(array,left,mid);
        mergeSort(array,mid + 1,right);
        //合并
        merge(array,left,mid,right);
    }
}

static void merge(int []array,int left,int mid,int right) {
    System.out.println("merge->left:"+left+" mid:"+mid+" rgiht:"+right);
    int i = left;
    int j = mid +1;
    int tmp[] = new int[right-left+1];//构建tmp数组
    int t = 0;//tmp数组索引
    //填充tmp数组
    for (;i<=mid && j<=right;) {
        if(array[i] < array[j]) {
            tmp[t++] = array[i++];
        } else {
            tmp[t++] = array[j++];
        }
    }
    while (i<=mid) {
        tmp[t++] = array[i++];
    }
    while (j<=right) {
        tmp[t++] = array[j++];
    }

    //再把tmp复制到array
    t = 0;
    while (left<=right) {
        array[left++] = tmp[t++];
    }
    System.out.println("  tmp:"+ Arrays.toString(tmp));
    System.out.println("merge:"+ Arrays.toString(array));
}

 /**
 *
 * a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

 　b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

 　c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

 * 整个排序过程，就是构造堆的过程
 *
 * 这儿写得利于理解一点，把最后一步改掉，循环从数组中把第一位取出来放到新数组，剩余的再去构造堆
 * @param array
 */
static void heapSort(int []array) {
    //原始数组
    int [] oriental = Arrays.copyOf(array,array.length);
    //最终排序好的数组
    int [] result = new int[array.length];

    int length = array.length;
    for ( int i = 0;i< length;i++) {
        //1.构造堆
        buildHeap(array);
        //构建完array[0]就是最大的元素,取出来放到排序好的数组
        result[i] = array[0];
        //[0]取走之后，一个新数组，再去构造堆
        array = Arrays.copyOfRange(array, 1,length-i);
    }
    System.out.println("finish:"+ Arrays.toString(result));
}

/**
 * 构造椎
 * @param array
 */
static void buildHeap(int []array) {
    //(n/2-1)~0的节点才有子节点
    for (int i= array.length/2 -1 ;i>=0;i--) {
//            System.out.println("i:"+i);
//            System.out.println("start:"+ Arrays.toString(array));
        int k = i;
        for (int left = k * 2 + 1; left < array.length; left = k * 2 + 1) {
           // System.out.println("build:"+ Arrays.toString(array));
            int max = left;
            int right = left + 1;
            //有右节点
            if (right < array.length) {
                if (array[right] > array[left]) {
                    max = right;
                }
            }
            //max是left子节点,那就交换左子节点与k
            if (array[max] > array[k]) {
                swap(array, max, k);
                // 下面就是非常关键的一步了
                // 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？
                // 所以，循环对子节点所在的树继续进行判断
                k = left;
            } else {
                break;
            }
        }
    }
    //System.out.println("  end:"+ Arrays.toString(array));
}

static void selectSort(int []array) {
    for (int i=0;i<array.length-1;i++) {
        int min  = i;
        for (int j = i+1;j<array.length;j++){
            if(array[min] > array[j]) {
                min = j;
            }
        }
        if( min != i) {
            int tmp = array[i];
            array[i] = array[min];
            array[min] = tmp;
        }

    }
}

static void shellSort(int []array) {
        //以length/2为增量
        for (int gap=array.length/2;gap>0;gap= gap/2) {
            //以gap分组，进行排序
           for(int i = gap;i<array.length;i++){
               int tmp = array[i];
               int j = i - gap;
               //相对直接插入，步长从1变成了gap
               while ( j>=0 && tmp<array[j] ) {
                   array[j+gap] = array[j];
                   j=j-gap;
               }
               array[j+gap] = tmp;
           }
        }
    }

9×4^i−9×2i+1  和 4^i−3×2^i+1  这两个算式

Socket socket = new Socket();
socket.connect(new InetSocketAddress("10.0.0.1",8080),20000);

Exception in thread "main" java.net.SocketTimeoutException: connect timed out
	at java.net.DualStackPlainSocketImpl.waitForConnect(Native Method)
	at java.net.DualStackPlainSocketImpl.socketConnect(DualStackPlainSocketImpl.java:85)
	at java.net.AbstractPlainSocketImpl.doConnect(AbstractPlainSocketImpl.java:350)
	at java.net.AbstractPlainSocketImpl.connectToAddress(AbstractPlainSocketImpl.java:206)
	at java.net.AbstractPlainSocketImpl.connect(AbstractPlainSocketImpl.java:188)
	at java.net.PlainSocketImpl.connect(PlainSocketImpl.java:172)
	at java.net.SocksSocketImpl.connect(SocksSocketImpl.java:392)
	at java.net.Socket.connect(Socket.java:589)

ServerSocket serverSocket = new ServerSocket(8080);
while ( true) {
    Socket socket = serverSocket.accept();
    new Thread(new P(socket)).start();
}

Socket socket = new Socket();
socket.connect(new InetSocketAddress("localhost",8080),20000);
socket.setSoTimeout(3000);

java.net.SocketTimeoutException: Read timed out
	at java.net.SocketInputStream.socketRead0(Native Method)
	at java.net.SocketInputStream.socketRead(SocketInputStream.java:116)
	at java.net.SocketInputStream.read(SocketInputStream.java:170)
	at java.net.SocketInputStream.read(SocketInputStream.java:141)
	at java.net.SocketInputStream.read(SocketInputStream.java:223)

Selector selector = Selector.open();
InetSocketAddress isa = new InetSocketAddress(host, port);
// 调用open静态方法创建连接到指定主机的SocketChannel
SocketChannel sc = SocketChannel.open(isa);

public void connect(){
	try{
		selector = Selector.open();
		InetSocketAddress isa = new InetSocketAddress(host, port);
		//10秒连接超时
		new Timer().schedule(tt, 10000);
		// 调用open静态方法创建连接到指定主机的SocketChannel
		sc = SocketChannel.open(isa);
		// 设置该sc以非阻塞方式工作
		sc.configureBlocking(false);
		// 将Socketchannel对象注册到指定Selector
		sc.register(selector, SelectionKey.OP_READ);
		Message msg = new Message();
		msg.what = 0;
		msg.obj = sc;
		handler.sendMessage(msg); // 连接成功
		new Thread(new NIOReceiveThread(selector, handler)).start();
	}catch (IOException e)	{
		e.printStackTrace();
		handler.sendEmptyMessage(-1); // IO异常
	}
}
TimerTask tt = new TimerTask(){
	@Override
	public void run(){
		if (sc == null || !sc.isConnected()){
			try{
				throw new SocketTimeoutException("连接超时");
			}catch (SocketTimeoutException e){
				e.printStackTrace();
				handler.sendEmptyMessage(-6); // 连接超时
			}
		}
	}
};

Bootstrap b = new Bootstrap();
b.option(ChannelOption.CONNECT_TIMEOUT_MILLIS, 10000)

public Response request(Request request) throws TransportException {
    int timeout = nettyClient.getUrl().getMethodParameter(request.getMethodName(), request.getParamtersDesc(),
            URLParamType.requestTimeout.getName(), URLParamType.requestTimeout.getIntValue());
	if (timeout <= 0) {
           throw new MotanFrameworkException("NettyClient init Error: timeout(" + timeout + ") <= 0 is forbid.",
                   MotanErrorMsgConstant.FRAMEWORK_INIT_ERROR);
       }
	NettyResponseFuture response = new NettyResponseFuture(request, timeout, this.nettyClient);
	this.nettyClient.registerCallback(request.getRequestId(), response);

	ChannelFuture writeFuture = this.channel.write(request);

	boolean result = writeFuture.awaitUninterruptibly(timeout, TimeUnit.MILLISECONDS);

	if (result && writeFuture.isSuccess()) {
		response.addListener(new FutureListener() {
			@Override
			public void operationComplete(Future future) throws Exception {
				if (future.isSuccess() || (future.isDone() && ExceptionUtil.isBizException(future.getException()))) {
					// 成功的调用 
					nettyClient.resetErrorCount();
				} else {
					// 失败的调用 
					nettyClient.incrErrorCount();
				}
			}
		});
		return response;
	}

	writeFuture.cancel();
	response = this.nettyClient.removeCallback(request.getRequestId());

	if (response != null) {
		response.cancel();
	}

	// 失败的调用 
	nettyClient.incrErrorCount();

	if (writeFuture.getCause() != null) {
		throw new MotanServiceException("NettyChannel send request to server Error: url="
				+ nettyClient.getUrl().getUri() + " local=" + localAddress + " "
				+ MotanFrameworkUtil.toString(request), writeFuture.getCause());
	} else {
		throw new MotanServiceException("NettyChannel send request to server Timeout: url="
				+ nettyClient.getUrl().getUri() + " local=" + localAddress + " "
				+ MotanFrameworkUtil.toString(request));
	}
}

NettyResponseFuture responseFuture = NettyClient.this.removeCallback(response.getRequestId());
if (responseFuture == null) {
	LoggerUtil.warn(
			"NettyClient has response from server, but resonseFuture not exist,  requestId={}",
			response.getRequestId());
	return null;
}

if (response.getException() != null) {
	responseFuture.onFailure(response);
} else {
	responseFuture.onSuccess(response);
}

public Object getValue() {
	synchronized (lock) {
		if (!isDoing()) {
			return getValueOrThrowable();
		}

		if (timeout <= 0) {
			try {
				lock.wait();
			} catch (Exception e) {
				cancel(new MotanServiceException("NettyResponseFuture getValue InterruptedException : "
						+ MotanFrameworkUtil.toString(request) + " cost="
						+ (System.currentTimeMillis() - createTime), e));
			}

			// don't need to notifylisteners, because onSuccess or
			// onFailure or cancel method already call notifylisteners
			return getValueOrThrowable();
		} else {
			long waitTime = timeout - (System.currentTimeMillis() - createTime);

			if (waitTime > 0) {
				for (;;) {
					try {
						lock.wait(waitTime);
					} catch (InterruptedException e) {
					}

					if (!isDoing()) {
						break;
					} else {
						waitTime = timeout - (System.currentTimeMillis() - createTime);
						if (waitTime <= 0) {
							break;
						}
					}
				}
			}

			if (isDoing()) {
				timeoutSoCancel();
			}
		}
		return getValueOrThrowable();
	}
}

// 先使用method的配置
int tryCount =
        refUrl.getMethodParameter(request.getMethodName(), request.getParamtersDesc(), URLParamType.retries.getName(),
                URLParamType.retries.getIntValue());
// 如果有问题，则设置为不重试
if (tryCount < 0) {
    tryCount = 0;
}

for (int i = 0; i <= tryCount; i++) {
    Referer<T> refer = referers.get(i % referers.size());
    try {
        request.setRetries(i);
        return refer.call(request);
    } catch (RuntimeException e) {
        // 对于业务异常，直接抛出
        if (ExceptionUtil.isBizException(e)) {
            throw e;
        } else if (i >= tryCount) {
            throw e;
        }
        LoggerUtil.warn(String.format("FailoverHaStrategy Call false for request:%s error=%s", request, e.getMessage()));
    }
}

static void insertSort1(int []sorts) {
    for(int i = 1;i<sorts.length;i++) {
        int tmp = sorts[i];//哨兵
        int j= i-1;
        while(j >=0 && tmp < sorts[j]) {
            sorts[j+1] = sorts[j];//比tmp大的全部往右移动
            j--;
        }
        //别的移完位置，把哨兵放到正确的位置
        sorts[++j] = tmp;
    }
}

/**
 * 分治法,从小到大排序
 * @param array
 */
public static int partition(int []array,int start,int end) {

    //取一位做为基数
    int pivot = array[end];//这儿取最后一位作为基数了

    int left = start;
    int right = end-1;//从倒数第二位开始比较

    //从两头向中间搜索,从小到大排序
    while (left < right) {
        //从left端开始搜索
        while(left < right && array[left] <= pivot) {
            left ++;
        }
        //从right端开始搜索
        while (left < right && array[right] >= pivot) {
            right -- ;
        }
        //两数交换,大的放到右边，小的放到左边
        if(left < right) {
            swap(array,left,right);
            left++;
            right--;
        }
    }
    //
    if(left != end && array[left] > array[end] ) {
        swap(array,left,end);
        return left;
    }
    //right == left
    return left+1;
}

/**
 * 分治法,从小到大排序
 * @param array
 * @param start
 * @param end
 */
private static void quicSort(int []array,int start,int end){
    if( start < end ){
        int partition = partition(array,start,end);
        print(array);
        quicSort(array,start,partition-1);
        quicSort(array,partition+1,end);
    }
}

int partion(int arr[], int begin, int end)
{
    int pit = arr[end];//挖最右数，留一个坑
    int left = begin;
    int right = end;

    while (left < right)
    {
        //从最左开始搜索比坑大的数
        while (left < right && arr[left] <= pit)
            left++;
        if (left<right) {
            arr[right] = arr[left];//拿left去填坑，left成为新坑
        }
        while (left < right && arr[right] >= pit)
            right--;
        if (left < right) {
            arr[left] = arr[right];//right去填left坑，left成为新坑
        }
    }

    arr[left] = pit;//用key填坑
    return left;
}

void QuickSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int mid = partion(arr, left, right);
        print(arr);
        QuickSort(arr, left, mid - 1);
        QuickSort(arr, mid + 1, right);
    }
}

int partion(int arr[], int left, int right)
{
    int key = arr[right];//取最后一位为key

    int cur = left;//当前指针
    int prev = left - 1;//前一个指针

    while (cur < right)
    {
        if(arr[cur] < key && ++prev != cur){//发现比key小的数
            swap(arr,cur,prev);
        }
        cur++;
    }
    //最后++prev交换
    swap(arr,++prev,cur);
    return prev;
}

void QuickSort(int arr[], int left, int right)
{
    if (left < right)
    {
        int mid = partion(arr, left, right);
        print(arr);
        QuickSort(arr, left, mid - 1);
        QuickSort(arr, mid + 1, right);
    }
}

/**
 * 传统写法
 * @param sorts
 */
private static void bubbleSort(int [] sorts){
    for (int i=0;i<sorts.length-1;i++) {
        for (int j= 0;j<sorts.length-1-i;j++) {
            if(sorts[j] < sorts[j+1]) {
                swap(sorts,j,j+1);
            }
        }
    }
}

private static void swap(int []sorts,int i,int j){
        int tmp = sorts[i];
        sorts[i] = sorts[j];
        sorts[j] = tmp;
    }

/**
 * 如果部分已经排序,设置一个flag,有序就跳出循环
 * @param sorts
 */
private static void bubbleSort1(int [] sorts){
    for (int i=0;i<sorts.length-1;i++) {
        boolean flag = false;
        for (int j= 0;j<sorts.length-1-i;j++) {
            if(sorts[j] < sorts[j+1]) {
                swap(sorts,j,j+1);
                flag = true;
            }
        }
        if(!flag) {
            break;
        }
    }
}

/**
 * 鸡尾酒排序，定向冒泡排序
 * @param sorts
 */
private static void bubbleSort2(int [] sorts){
    int i = 0;
    int j = sorts.length-1;
    while (i <= j) {
        for(int s = i;s<j;s++) {//从左往右
            if(sorts[s] < sorts[s+1]) {
                swap(sorts, s, s + 1);
            }
        }

        System.out.println(JSON.toJSONString(sorts));
        for(int e = j;e>i;e--) {//从右往左
            if(sorts[e] > sorts[e-1]) {
                swap(sorts, e, e - 1);
            }
        }
        j--;i++;
        System.out.println(JSON.toJSONString(sorts));
    }
}

/**
 * 异步取得channel
 * @param index
 * @param callback
 */
public void asynGetChannel(int index,final Callback callback) {
    // 1. 随机获取一条channel
    final int pos = ThreadLocalRandom.current().nextInt(MAX_CONNECTIONS);
    Channel target = channels[pos];

    // 2. 如果获取到了连接，直接返回
    if (target != null && target.isActive()) {
        logger.info("direct success "+index);
        callback.onSuccess(target);
        return;
    }

    synchronized (locks[pos]) {
        target = channels[pos];
        // 2. 如果获取到了连接，直接返回
        if (target != null && target.isActive()) {
            callback.onSuccess(target);
            return;
        }

        // 3.如果连接正在创建中，则加入queue
        if (target instanceof EmptyChannel) {
            boolean result = jobs.offer(callback);
            if (result) {
                return;
            } else {
                throw new RuntimeException("Can't connet to target server and the waiting queue is full");
            }
        }

        // 4. 连接尚未创建
        channels[pos] = new EmptyChannel();

       Connector.connect(host, port, new Callback() {
           @Override
           public void onSuccess(Channel channel) {
               logger.info(index + " ------------connect success---------"+pos + " channel:" +channels[pos].getClass().getName());
               List<Callback> tmpJobs;//建立一个tempJobs，快速释放锁
               synchronized (locks[pos]) {
                   // 设置channels，拷贝jobs队列，释放锁
                   channels[pos] = channel;
                   tmpJobs = drainJobs();
               }
               for(Callback pendingCallback : tmpJobs) {
                   try {
                       if(pendingCallback != callback) {
                           pendingCallback.onSuccess(channel);
                       }
                   } catch (Exception e) {
                       logger.error("call connectionCallback fail", e);
                   }
               }
           }

           @Override
           public void onError(Throwable e) {
               List<Callback> tmpJobs;//建立一个tempJobs，快速释放锁
               synchronized (locks[pos]) {
                   // 设置channels，拷贝jobs队列，释放锁
                   channels[pos] = null;
                   tmpJobs = drainJobs();
               }
               for(Callback pendingCallback : tmpJobs) {
                   try {
                       if(pendingCallback != callback) {
                           pendingCallback.onError(e);
                       }
                   } catch (Exception x) {
                       logger.error("call connectionCallback fail", x);
                   }
               }
           }
       });
    }
}

Future future = doTask1();
doTask2();
doTask3();
Result result = future.get();

T(n) = O(f(n))

规律       Big-O

2             O(1)   --> 就是一个常数

2n + 10       O(n)   --> n 对整体结果会产生最大影响

5n^2         O(n^2) --> n^2 具有最大影响

bool IsFirstElementNull(IList<string> elements)
{
    return elements[0] == null;
}

bool ContainsValue(IList<string> elements, string value)
{
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
}

for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

int Fibonacci(int number)
{
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

i=1;       
while (i<=n)
    i=i*2;

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)