pdf文档上看到的。
直接插入排序算法简便、容易实现。当待排序元素的数量n 很小时，
这是一种较好的排序方法，但是通常待排序元素数量n 很大，则不宜采用直接插入排序方法，
此时需要对直接插入排序进行改进。
直接插入排序的基本操作是向有序序列中插入一个元素，插入位置的确定是通过对有序
序列中元素按关键字逐个比较得到的。既然是在有序序列中确定插入位置，则可以不断二分
有序序列来确定插入位置，即搜索插入位置的方法可以使用折半查找实现。
折半插入排序所需的辅助空间与直接插入排序相同，从时间上比
较，折半插入排序仅减少了元素的比较次数，但是并没有减少元素的移动次数，因此折半插
入排序的时间复杂度仍为O(n2)。
class="java" name="code">package test.sort;
import java.util.Arrays;
public class BinInsertSort {
public int[] binInsertSort(int[] a){
for(int i=1;i
/**
*  保存当前操作值，记录高位hi用来做高低位的计算，低位永远是0
*  hi 是用来记录要插入的位置的上一个位置。
*  这样看来着个就是直接插入排序的一个改版，
*  只要记住：待操作元素前面的永远是有序的，对有序的集合做插入操作，找到插入点移动数据，插入就可以了。
*/
int tmp = a[i],hi = i-1,low = 0;
while(low<=hi){//折半确定位置
int mid = (low+hi)/2;
if(tmp
hi = mid -1;
}else{
low = mid+1;
}
}
for(int j =i-1;j>hi;j--){
a[j+1] =a[j];//在待插入位置后面的元素全部向后移动
}
a[hi+1] = tmp;//将元素插入指定空间
}
return a;
}
public static void main(String[] args) {
BinInsertSort b = new BinInsertSort();
int[] as = { 1, 34, 56, 23, 67, 82, 4, 3, 2, 0, 13, 76, 90, 21, 24, 44,
4 };
int[] a = b.binInsertSort(as);
System.out.println(Arrays.toString(a));
}
}

为什么要使用全文索引技术？
 
在网站应用中，我们经常需要用到站内搜索的功能来查找指定的关键字。在网站的后台
存储中，信息可能存储的地方主要有：数据库表、HTML静态页面文件、word、pdf、excel、ppt、txt等文本文件中。
基于文件的全文检索当然是使用分词技术来实现。在Java开源产品中，Lucene是一个使用最广泛的全文搜索引擎，我们可以使用Lucene的API将文本的内容进行分词处理。经分词处理后，Lucene会将解析的分词增加到文件索引库中，然后我们可以通过分词查询技术，将与查询内容相关的文件检索出来。
那么对于数据库的全文检索如何实现？在企业的网站中，大量的动态信息是存储在数据库中的，例如新闻内容、知识库、商品信息等都是存储在数据库表中的。如果我们使用数据库的like ‘%关键词%’这种方式查找信息显然是不可取的，因为数据库对于like ‘%关键词%’这种查询模式，数据库索引是起不到效果的，这样会严重影响查询的效率。所以对于数据库的全文检索，也应使用分词技术，在增加表记录的时候，将相关字段采用Lucene的分词技术增加到索引库中，并同时将记录的ID和对应的访问连接也同时加入到索引库中，我们就可以在查询关键词的时候，将对应信息的访问连接同时查找出来，这样就起到全文检索的效果。
 
网站内容管理系统(CMS)全文检索技术实现
 
在网站内容管理系统中，信息的正文一般是存储在数据库表中，信息表的结构一般包括
信息ID、标题、摘要、正文、所属栏目、关键词、作者、来源等字段。在信息发布的流程中，主要包括信息的编辑、送审、审批、发布、取消发布、信息删除等环节。信息正式发布的时候，除了需要生成此信息对应的html文件，还要将对信息的标题、摘要、正文等字段进行分词处理，这是为了在信息发布以后，可通过站内搜索功能，将查询内容关联的信息条目查找出来。在删除信息或取消发布时，还要将对应信息的分词从索引库中删除。
因为操作索引库的同时Lucene会对索引文件加锁，所以增加和删除索引库会导致并发问题，一旦索引库被锁定，则其他用户发布信息的时候就不能将词条增加到索引库中，所以我们在信息发布和取消发布的时候，只需要把发布或删除的信息记录到索引库待处理队列中，由定时器定时处理。
整个全文检索的实现需要设计以下功能：
 
索引库初始化工具：清空索引库，主要用于系统初始化的时候。
定时器及索引队列：定时处理索引队列，对增加的信息，向索引库中添加分词，对删除或取消发布的信息，从索引库中删除分词。
分词处理：主要用于添加分词、删除分词。对于内容管理系统而言，如果一篇文章如果带有word等附件，附件的正文也要参与分词处理。
分词查询：提供带分页功能的关键词查找。
 
下面具体介绍全文检索功能的实现：
 

索引库初始化：指定一个目录，创建Lucene的分词库文件。全文检索必须有索引库文件才能进行增加索引、删除索引和进行索引查询等操作。下面是初始化分词库代码：
 
    public static void initIndex(String dir) throwsCorruptIndexException, LockObtainFailedException, IOException

    {

        IndexWriter writer;   // new index being built

        try

        {

        File file = newFile(dir);

        file.mkdirs();

        }

        catch(Exception ex)

        {

        logger.error("创建目录失败!");

        }

       writer = newIndexWriter(FSDirectory.open(newFile(dir)), newStandardAnalyzer(Version.LUCENE_CURRENT), true,

                newIndexWriter.MaxFieldLength(1000000));

       writer.optimize();

       writer.close();

    }

 


 
(2) 索引队列数据库设计：
 
索引队列表Comm_Lucene_queue的表结构（只列出主要字段）：
 
 

字段


字段中文名


字段说明


Entity_name


表名


对于内容管理系统，主要是信息表需要处理全文检索，但系统还需支持对其他数据库表进行全文检索，所以设置一个表名字段用于区分


Entity_row_id


记录ID


记录要处理的表的哪条记录，用唯一行号区分。


Index_oper_type


全文检索处理方式


标识增加分词用add,标识删除分词用delete


Create_dt


队列创建时间


记录本条队列创建的日期+时分秒+毫秒，用于标识处理顺序


 


 


 

 
全文检索的定时器只需要定时处理这个数据库表的队列信息就可以了，处理完毕后，删除已处理的记录。定时器可以设置每几分钟读取几千条队列信息进行处理，处理队列信息就是根据index_oper_type来区分是增加分词还是删除分词，然后根据entity_name和row_id来确认处理哪个数据库表的哪条记录。因为对于信息表，在设计时就已经确认需要对标题、摘要、正文等字段进行分词，那么如果对于其他数据库表，系统如何知道哪些表的哪些字段需要分词呢？我们可以单独设置一个表字段信息配置表来标识哪些表哪些字段需要分词。下面是对数据库表字段基本信息表中增加的全文检索设置字段:
 
 

字段


字段中文名


字段说明


Table_name


数据库表名


 


Column_name


表字段名


 


Is_search


是否参与全文检索


如果字段参与全文检索，则需要设置是否分词和是否在索引库中存储字段值。


Is_lucene_analyzed


是否做分词解析


对于全文检索，如作者，信息ID,创建时间，对应的url都不需分词解析，因为这些字段拆分是没意义的，但需要存储到索引库


Is_lucene_indx


是否存储分词


对于大文本的正文一般只做分词，不存储。例如对于信息表，正文字段做分词处理，但不存储，信息ID做存储（存储在索引库而不是数据库），但不分词。

 
在这里顺便说明一下索引库的优化，因为Lucene索引库的增加和删除都需要打开和关闭索引文件，所以在处理索引队列时，不是每读一条记录就打开和关闭一次索引库，而是首先打开索引文件，然后按队列的记录信息逐条做增加或删除分词，知道本次查询的所有队列处理完毕后再优化和关闭索引文件。见下面的代码:

//第一步：首先打开索引文件

String indexPath = ServiceLocator.getSysConfigService().getStringValueByParmName("luceneIndexDir");//伪代码


IndexWriter writer = null;

writer = newIndexWriter(FSDirectory.open(newFile(indexPath)), newStandardAnalyzer(Version.LUCENE_CURRENT),false,

                     newIndexWriter.MaxFieldLength(1000000));

writer.setMergeFactor(100);

writer.setMaxBufferedDocs(50);

writer.setMaxMergeDocs(2000);

//第二步：索引队列处理（代码略）

//第三步：优化和关闭索引库

writer.optimize();//优化索引库

writer.close();   //关闭索引库

……


 


 

(3)分词处理
 
【删除分词】
关于分词的删除比较简单，当信息记录删除后，根据信息记录的唯一行号在分词库中查到对应的记录，然后删除分词：
String indexPath = ServiceLocator.getSysConfigService().getStringValueByParmName("luceneIndexDir");

String filePath = ServiceLocator.getSysConfigService().getStringValueByParmName("searchRoot");

Query query = null;   

IndexReader reader = IndexReader.open(FSDirectory.open(newFile(indexPath)), true);

IndexSearcher searcher = null;    

searcher = newIndexSearcher(reader);

Analyzer analyzer = newStandardAnalyzer(Version.LUCENE_CURRENT); 

//根据信息id查找对应的索引条目

QueryParser qp = newQueryParser(Version.LUCENE_CURRENT,"id", analyzer);

query = qp.parse(infoId);

//删除对应的索引

writer.deleteDocuments(query);


  
【增加分词】
在信息发布过程中，每条发布的信息已生成了对应的静态页面，为了让访问网站的用户能够在站内搜索中根据查询关键字查找到这条信息，需要增加此信息对应的分词，因为发布信息时，系统会往索引处理队列中插入记录，所以如果从队列中读取到标识为”add”的记录，就会执行增加分词操作，增加分词的基本处理逻辑就是根据信息ID,找到数据库中对应的记录，然后将表字段的值赋予给Lucene的Field(域)，然后构造一个Lucene特有的Document对象写入到索引库中。看下面的代码片段：
 
//首先创建一个Document对象。

Document doc = newDocument();

IndexReader reader = IndexReader.open(FSDirectory.open(newFile(indexPath)), true);

Analyzer analyzer = newStandardAnalyzer(Version.LUCENE_CURRENT); 

//添加Path域，这个非常重要，实际值是此信息对应的URL访问连接。Path域不需要分词，但//要存储,Index.NOT_ANALYZED表示不需要分词，Field.Store.YES表示需存储。

doc.add(newField("path", infEnt.getInfUrl(), Field.Store.YES,Field.Index.NOT_ANALYZED));

//增加标题域，信息在页面中显示的标题文字

doc.add(newField("title", infEnt.getInfTitle(), Field.Store.YES, Field.Index.ANALYZED));

//增加摘要域,Field.Store.YES表示需存储，Field.Index.ANALYZED表示需分词。

String summary = infEnt.getInfSummary();

if(summary==null)summary="";//空值是不能建立索引的

doc.add(newField("summary", summary, Field.Store.YES, Field.Index.ANALYZED));//或者取正文的某段做摘要。

……

//对于正文的处理：获取信息表的正文字段，如果有附件，根据附件格式//(word,pdf,excel,ppt,txt等)调用对应的正文读取器获取这些文件的正文，再加上信息//表的正文作为contents域的值参与分词解析，这样查询时，无论是正文还是附件，只要有对//应的关键词都可以被检索出来。如果信息是一个外部连接，可使用org.htmlparser包的API将对应html连接的正文获取下来，加入到contents中。

doc.add(newField("contents", buffer.toString(), Field.Store.NO, Field.Index.ANALYZED));//其中bugger.toString()是正文+附件的内容。

 

//增加ID表示域，增加这个用于区分对哪个索引条目进行处理，删除信息时，需要查找id值以便删除对应的索引分词。

doc.add(newField("id", infoId, Field.Store.NO, Field.Index.NOT_ANALYZED));

//将增加的索引分词添加到索引库

writer.addDocument(doc);

 

 
说明：Field域的标识是可以自己定义的，如上面的title,path,contents域，具体根据业务需要来定义，但定义的域一般都需要在编程中使用，否则就没有意义。
 
(4)分词查询
 
分词查询实际就是全文检索的最终目标，可以在网站的页面上输入关键词进行全文检索，简单的站内检索一般是针对正文关键词进行检索，如果设计的复杂一点，还可以按标题、作者、发布日期、摘要、信息分类等进行全文检索。分词查询需要实现：搜索条件输入页面、查询结果页面（带分页的）、后台分词查询算法。
一般首页、主要的二级页面都有站内搜索的输入框，如下图：
 

点击搜索后，系统将搜索参数提交到MVC控制层中进行全文检索查询，查询后返回搜索的结果页面，搜索结果页面必须是带分页功能，因为查询出来的匹配的记录可能会很多，另外搜索出来的每条信息都应有标题、摘要、查询出来符合条件的记录数，点击信息标题后可以连接到详细信息的查看页面。通过全文检索查询的效率比数据库直接查询效率会高出很多，查询出几万条符合条件记录需要的时间基本都在毫秒级。见下图查询结果页：

对Lucene的全文检索效率可到http://www.culturalink.gov.cn/中国文化网的首页上体验一下查询效率，使用“中国”作为查询内容大概可查到两万多条记录。
 具体的分词查询和分页算法的代码就不在这里赘述了。
 
带权限的全文检索
 
带权限的全文检索的实现也比较简单，可以首先设置每条信息应该归什么权限访问，例如某条信息的可以由AUTH_1,AUTH_2权限码访问，则在增加索引库的时候可添加一个名为auth_id的Field域，域的值为按逗号隔开的权限码，如auth_1,auth_2，在信息查询的时候，检查当前用户的权限集合是否有这些权限，在分词查询逻辑中增加对auth_id域的权限判断，就可以过滤掉自己无权查看的记录。