一、插入排序
思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。
关键问题：在前面已经排好序的序列中找到合适的插入位置。
方法：直接插入排序、二分插入排序、希尔排序
二、二分法插入排序
基本思想：二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。
Java实现
publicclassErFenCharRu{publicstaticvoidmain(String[]args){int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};//假设第一个记录为已经待排序好的记录，那么要比较a.length-1个记录，所以外层循环是a.length-1次//这里可以直接i=1从第二位开始处理也一样for(inti=1;i<a.length;i){//缓存待排序的记录inttemp=a[i];//下面用二分法来在前面排好序的位置中找到插入的位置//找到前面已排序的起点intleft=0;//找到已排序的终点intright=i-1;//中间位置坐标intmid=0;//如果左边小于右边，就表明数据大于1，可以用二分法while(left<=right){//这个如果是偶数，比如4，则第二位当做中间值，若是5则第三位mid=(rightleft)/2;//对比当前排序的数目和该数据的大小、if(temp>a[mid]){//继续右边比较left=mid1;}else{//继续左边比较right=mid-1;}}//循环结束后，left值和right值一定相同，并且比最一次比较的mid向左或者右偏移一位，所以位置就是left插入//此时必须把已排序好的从left开始往后移动//这里找到位置后，需要把该位置往后面的都右移for(intj=i-1;j>=left;j--){a[j1]=a[j];}if(left!=i){a[left]=temp;}}for(inti=0;i<a.length;i){System.out.print(a[i]"");}}}