本篇介绍第二种排序算法，插入排序。

插入排序一般举的例子是“整理手牌”，从牌堆中摸一张牌，放在手里，按照顺序整理好，一般是将新摸到的牌和手中已有的牌依次比较，可以从小到大也可以从大到小。然后选择合适的位置“插入”。

先看完整的代码实现，这个代码是从大到小（逆序）的方式进行比较的：

public static void InsertSort0(){		int[] a={5,1,4,8,3,9,0,2,7,6};		//1 4 5 8 		for(int i=1;i
     
      =0&&temp
     

 我们先分析一下，这个算法的大的流程。先选定一个待排序的元素，然后找到一个合适的位置，把元素插入进去。

核心的就是找到合适的位置。

第一步：在一个已经排好序的数组中，找到一个位置，使得当前要插入的元素放入后，其左边的都不大它，其右边的都不小于它。

这个算法用一个循环就可以搞定：

public int GetCorrectIndex(int[] a){		int temp = a[a.length-1];		int j = a.length-2;		while(j>=0 && temp

 这个是在以当前的数组的最后一个元素为基准，向前进行搜索。改进为“人为指定”，增加一个重载版本：

public static int GetCorrectIndex(int[] a,int endIndex){		int temp = a[endIndex];		int j = endIndex-1;		while(j>=0 && temp

 这个函数，输入参数是数组a以及，这个数组中待排序的元素的索引endIndex，也就是说endIndex之前的元素都是有序的。

返回值是这个元素中合适的位置。这个位置就是带排序的元素应插入的位置。

第二步：选定一个待排序的元素，并将带排序的元素插入到合适位置：

public static void InsertSort(int a[]){		for(int i=1;i

 经过这两部，就完成了插入排序，完整代码如下：

package asen.yang;public class insertSort {	public static void main(String[] args) {		// TODO Auto-generated method stub		//InsertSort0();				int[] a={5,1,4,8,3,9,0,2,7,6};		InsertSort(a);		for(int i=0;i
     
      =0 && temp
      
       =0 && temp
       
        =0&&temp