原本想写Base64算法的，不过我还是想写点有趣的，而不是Base64这样没有什么思维难度的模版。在手贱在hihoCoder上看到了一个关于非有序数组的二分查找的题目，要求在非有序的数组上做线性的查找（于是就不能排序了），找到这个数组中第K大的值。做了一个下午，到晚上搞定，终于抠完几个细节。不过想的过程还是蛮棒的，这个算法是从快速排序衍生而来的，而从经典算法出发去yy，能让我们思考更多经典算法的细节，感受经典算法的那种美。

快速排序

在讲这个二分查找算法的之前我们还是先看看它的基础：快速排序算法。虽然快速排序有很多缺点：它不稳定、难理解、会被奇葩数据拿去卡，但在实践当中还是个很快很靠谱的排序算法，比Java和Python所采用的TimSort不知道高到哪里去了。我觉得作为一个IT从业者，不能理解快排就好像一个中国人没读过《论语》一样。
讲解快排的文章有很多，任何一本算法书也都不可能不讲快排。不过我这里需要特别阐述一下快排究竟在干什么。
基本的观点是，每一“趟”的快排是针对原来数据的一个区间上进行的。首先在这个区间上随意取一个值mid，然后遍历一遍这个区间，使得能够把所有数据中小于等于mid的扔到区间的左部分，大于等于mid的扔到区间的右部分。然后左右分别继续搞。这么说太抽象了，我们拿几个数据玩玩看：
假设初始的数据是34 10 23 78 56，那么如果我们取第一个34为mid，我们就要遍历一遍数组（在O(n)的时间内）变成10、23、34在左边，56、78在右边。至于10、23、34它们之间的顺序则无关紧要，不论是10、23、34还是23、34、10还是34、10、23还是别的什么都不管，反正前三个都是小于等于34的，后两个都是大于等于34的。

其实34也可能在后面一半。这点非常重要，因为这就意味着mid的值位置是不确定的，如果数据中有多个mid，它可能左右两部都有分布。实际上一趟快排结束后，我们只能保证小于mid的在左边，大于mid的在右边，至于mid在哪？不知道。

现在我放一段我的快排实现。我取mid一般是取中间那个位置，正常情况下是要随机取，而算法讲解的时候一般取第一个。

void Qsort(int l,int r){
    int mid=A[(l+r)/2];
    do{
        while (A[i]<mid) i++;
        while (A[j]>mid) j--;
        if (i<=j){
            int k=A[i];
            A[i]=A[j];
            A[j]=k;
            i++;j--;
        }
    }while (i<=j);
    if (l<j) Qsort(l,j);
    if (i<r) Qsort(i,r);
}

这段程序能保证的是，所有小于mid的都在l～j范围内，而所有大于mid的都在i到r范围内。同时j+1到i-1范围内的（至多一个，可能是零个），一定是mid。但是所有是mid的值，位置是不确定的。

非有序数组的线性查找算法

我们现在可以开始想怎么在非有序的数组里，避免全部排序整个数组，而找到某个数是第几大了。由快速排序的算法的思想出发，我们可以发现，如果一趟快排结束，那么我们每次能把小于mid的扔到区间左边，大于mid的扔到区间右边，平均来看，查找范围就缩小了一半。（当然被卡是可能的，我们只是寻求一个期望复杂度的较优。）这样一个算法能够实现，那么整体复杂度就是
要注意的是i与j之间的差。在上述的快排程序跑过一趟之后，j<i，但是我们并不确定j和i中间是否会有一个数。这个数可能有，也可能没有，必须特殊判断。最后写出来的线性查找算法如下：

int Search(int l,int r){
    if (l==r) return A[l];
    int i=l,j=r;
    int mid=A[(l+r)>>1];
    do{
        while (A[i]<mid) i++;
        while (A[j]>mid) j--;
        if (i<=j){
            int k=A[i];
            A[i]=A[j];
            A[j]=k;
            i++;j--;
        }
    }while (i<=j);
    if (j==i-2){
        if (j+1==K) return A[j+1];
    }
    if (K<=j) return Search(l,j);
    if (K>=i) return Search (i,r);
}

我拿了一个用algorithm库提供的sort函数做的O(NlogN)排序程序做对拍，在N=106的情况下，不开O2速度快一倍，开了O2快30%左右，效率提升还是很显著的。

文件上传可以说是Web应用中很常用的一块，前几天打算研究一下HTML5提供的FileReader API，并且用Tomcat作为后端来实验大文件的上传（只是学校的课程作业必须用Java写，都不允许使用最好的编程语言php>.<）。可Java Servlet与php这种喜闻乐见的Web码农语言不同，并没有提供一个很简单的处理文件上传的API，所以还捣鼓了蛮久，也对一般的文件上传的HTML控件和实现原理稍微有了一点了解。

对面宿舍的一位同学说我很久没更了不太好，于是我就写一篇，谢谢他的提醒。

首先，我们都知道最常见的HTML的文件上传控件是喜闻乐见的<input type="file">，但一定要搭配form的属性enctype="multipart/form-data"，服务器上要有一个接收上传的cgi或者别的什么，既然我们用java写，就叫uploadServlet。于是有了一个如下的常见的上传表单。

<form action="uploadServlet" enctype="multipart/form-data" method="POST">
    <input name="password" type="password" />
    <input name="File1" type="file" />
    <input type="submit" value="Upload" />
</form>

然后我们在后端处理。由于Java Servlet的API是没有提供什么$_FILES数组这样傻瓜式的文件操控方式，我们必须自己处理request。我们不妨先把收到的request输出到文件当中，看看Servlet会收到什么，再想想怎么处理。放这样一个servlet的代码：

import javax.servlet.*;
import javax.servlet.http.*;
import java.io.*;

public class UploadServlet extends HttpServlet{
    @Override
    public void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException{
        response.setContentType("text/plain;charset=utf-8");
        PrintWriter writer=response.getWriter();
        InputStream in=request.getInputStream();
        File f = new File("/tmp/upload");
        //把文件存到/tmp/upload
        FileOutputStream fout = new FileOutputStream(f);
        byte[] b=new byte[1024];
        int n=0;
        while ((n=in.read(b))!=-1){
            fout.write(b,0,n);
        }
        fout.close();
        in.close();
        writer.println("Finished uploading files!");
        writer.close();
    }
}

有了Servlet就拖出去跑一跑。这里我的表单不仅会发送文件，还会发送一个密码域。如果我随便发一个文本文件，那么我得到了这样的结果。

多上传几次还会发现那一堆横杠开头的数字会变动。这下不好玩了，虽然我们可以看到我们上传的数据，但要解析它有点过于复杂了。这个请求是依据RFC1867来写的，虽然有标准可依，但我们这么懒怎么会去依照标准写一个解析器呢？

于是我们需要请出Apache开发的文件上传处理库Commons FileUpload。这个网站提供了最新版的下载链接和基本的使用指南。文档讲得过于全面了，而我们一般不需要那么多功能，够用就好。翻了几篇教程，写出来了一个简单的文件上传接收代码。

javaimport javax.servlet.*;
import javax.servlet.http.*;
import java.io.*;
import java.util.*;
import org.apache.commons.fileupload.*;
import org.apache.commons.fileupload.servlet.*;
import org.apache.commons.fileupload.disk.*;

首先需要多装载三个库，以及一个java.util.List，因为到时候处理的时候，Commons FileUpload会把搞成一个List返回回来，我们需要接收这个List并处理解析它。

public class UploadServlet extends HttpServlet{
    private String filepath;
    private String temppath;
    private String buf;
    public void init(ServletConfig config) throws ServletException{
        super.init(config);
        ServletContext context=getServletContext();
        filepath=context.getRealPath("/"+config.getInitParameter("filepath"));
        temppath=context.getRealPath("/"+config.getInitParameter("temppath"));
    }

为了方便维护，我把保存上传文件的目录用Init Parameter的方式写到web.xml里面去，然后在这个地方读出来。我们需要一个保存上传文件的目录和一个用来做缓存的临时目录。如果你接收上传文件之后不打算保存而是直接拿去处理，也没有问题，但是一定要有一个缓存目录，在后面有用。

接下来是真正激动人心的处理上传的代码了。我懒得写doGet了所以就只有一个doPost。

     @Override
    public void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException{
        response.setContentType("text/plain;charset=utf-8");
        PrintWriter writer=response.getWriter();
        int count=0;
        try{
            DiskFileItemFactory diskFactory = new DiskFileItemFactory();
            diskFactory.setSizeThreshold(4 *1024 );
            diskFactory.setRepository(new File(temppath));

这里我们开了一个diskFactory，就是FileUpload所需要使用的缓存，当内存存不下上传的文件的时候，它会自动写入缓存目录。通过setSizeThreshold方法可以设置内存的使用上限，也就是当内存用了这么多却还存不下，就开始写缓存。显然这个值很大程度上会决定这个Servlet的效率。

    ServletFileUpload upload = new ServletFileUpload(diskFactory);
    upload.setSizeMax(4 * 1024 * 1024);
    List fileItems = upload.parseRequest(request);
    Iterator iter = fileItems.iterator();

这里我们就真正建了一个ServletFileUpload的实例upload来处理文件的上传。可以设置上传文件的最大大小。然后把request对象直接交给upload来解析，它会返回一个一个List，这个List的每一项实际上是一个FileItem对象，后面就要用迭代器处理这个列表。

    while (iter.hasNext()){
        FileItem item = (FileItem) iter.next();
        if (item.isFormField()){
            writer.println(item.getFieldName()+" : "+item.getString());
        }

要注意的是ServletFileUpload也会处理非文件的信息，可以用isFormField方法来检查，然后将信息获取出来。但这在这里不是重点，只是必须要处理掉而已。

        else{
            String filename = item.getName();
            filename = filename.substring(
            filename.lastIndexOf("\\")+1,filename.length());
            File uploadFile = new File(filepath+"/"+filename);
            item.write(uploadFile);
            writer.println("Get file:"+ filename);
            writer.println(" filetype: "+item.getContentType());
            count++;
        }
        }
    } catch (Exception e){
        e.printStackTrace();
    }
    writer.println("Finished uploading files!");
    writer.close();
}
}

处理文件的代码就这么点，如果还要说什么的话，就是每个文件的FileItem对象不仅可以用write方法来直接写到什么文件里面去，也可以用getInputStream方法得到一个输入流来解析，或者用get方法直接读到一个byte数组里面去。可以说这个库提供了一个很方便的方法解析上传的文件。

最后提一下，Apache Commons是一个Java增强库，提供了大量的优质Java资源库，涉及很多开发领域。如果不出意外，应该我会在近期写一篇关于JavaScript FileReader的blog，敬请期待。

参考的文章：
Servlet实现基本文件上传
在Servlet中使用开源fileupload包实现文件上传功能

高考考完开始进行算法竞赛的康复训练（好吧其实是从零开始直接学，过完高三什么都忘了T T），在POJ上做了一些水题。今天做到这道欧拉回路，很有感触，因为第一次学这个算法的时候并没有学透，今天再做才发现原来求欧拉回路的算法有这么精妙。

先讲题意吧，原文链接：http://poj.org/problem?id=2230。大意是给你一个无向图，要求找一条路径，走过每一条边恰好两次，且每次走的方向不同。很容易就能想到把这图转化为有向图求欧拉回路。题目保证一定能找到从1点出发回到1点的答案。

现在的关键就是求这个回路了，一个朴素的想法就是直接DFS，每次经过一条边就删除它，回退的时候再还原。如果经过了原图边数恰好两倍就找到了一个答案。但这个算法实在太慢，直接TLE。

现在我们考虑搜索的过程：如果不还原一个点所遍历的边，那么当这个点去掉所有边之后，再去掉这个点，剩下的图是什么？先上图，这是题目所给的样例的草图：

然后从1开始，我们丧心病狂一点，直接把1就搞掉不碰与1无关的边，反正遍历的顺序是不确定的，这么做未尝不可。那么就变成了这样：

我们看到，剩下的还是一个欧拉回路。我们可以猜想，一个欧拉回路，删掉一个点，仍然是一个欧拉回路。这个结论其实非常容易证明，随便想想就明白这是对的。进一步研究，会发现一个更普遍的结论：从一个欧拉回路中拖走一个小欧拉回路，结果也是一个欧拉回路。这个性质也很明显，而且前一个结论是后一个结论的推论。由这个结论，我们可以考虑，有公共点的两个欧拉回路其实是可以拼接的。于是下面这个搜索算法就很好理解了：

void DFS(int now)
{
    for (int p=G.Head[now];p;p=G.Pre[p])
    {
        if (!G.Vis[p])
        {
            G.Vis[p]=1;
            DFS(G.V[p]);
        }
    }
    printf("%d\n",now);
}

G是图，我用了一个邻接表，G.Vis是标记这条边是否走过。如果一条边还没走过，就标记然后走下去，关键在如果一个点已经走完了怎么办：直接输出。每次从v出发回到v，就是扒走了一个回路，根据栈的性质，这样得到的顺序其实是相反的。不过由于这题的图中边是成对出现，所以没关系，倒过来也是可以的。输出的过程就是把一个个欧拉回路拼在一起。对于无向图，通过拼接也可以得到欧拉回路，不过相对于这个算法要复杂不少。最后提供Gitcafe代码链接，如有需要参考请看：https://gitcafe.com/linmx0130/OJCode/blob/master/POJ/P2230/main.cpp