插入排序：

　　插入元素分为：直接插入排序，二分插入排序，链表插入排序，希尔排序。

　　（1）直接插入排序

　　　　插入元素就像整理扑克牌一样，当我们摸到新牌时，需要针对手中已经有序的牌进行从后向前寻找，看最终插到哪里。

　　　　插入排序主要思想：每步将待排序的元素插入到已有序的元素中，直到所有元素插入完毕。

　　　　

　　　　直接插入排序代码如下（仅供参考）：

　　

//直接插入排序    public static void insert_Sort(int[] arr,int low,int high){        if(arr==null||arr.length<=0||low>high) return;        for(int i=low+1;i<=high;i++){            int value=arr[i],k=i;            for(int j=i-1;j>=0&&arr[j]>value;j--){                arr[j+1]=arr[j];                k=j;            }            if(k!=i){                arr[k]=value;            }        }    }    public static void main(String[] args){        int[] arr={1,4,2,3,5,9,6,7,8,5,5,4,2,1,1,1,2,2,2,3,3,3};        insert_Sort(arr,0,12);        System.out.println(Arrays.toString(arr));    }

　　　　直接插入排序特点：

　　　　（1）具有稳定性。由于直接插入排序不会将相同元素进行交换，因此是稳定排序。

　　　　（2）平均情况下需要N²/4次比较和N²/4次交换。最好情况下需要N-1次比较和0次交换（元素已有序）。最坏情况下需要N²/2次比较和N²/4次交换（元素逆序）。

　　　　（3）适用于数据量较小的排序。尤其适用于元素距离它的最终位置不远的元素排序。

　　　　（4）交换操作和倒置操作数量相同，每次交换都会减少一次倒置操作。

　　　　（5）jdk源码中，经常将其用于某些算法的较小数组的引用，例如快速排序，当元素个数小于47时使用插入排序完成元素的排序操作。