一、插入排序

思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。

关键问题：在前面已经排好序的序列中找到合适的插入位置。

方法：直接插入排序、二分插入排序、希尔排序

二、直接插入排序

基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。

java实现

public class ZhiJieChaRu {
    /**
     * 直接插入排序第一版
     * @param a
     * @return
     */
    public static int[] sort1(int[] a) {
        //假设第一个记录为已经待排序好的记录，那么要比较a.length-1个记录，所以外层循环是a.length-1次 
        //这里可以直接i=1从第二位开始处理也一样
        for(int i=1;i<a.length;i++) {
            //跟前面已排序的记录做对比，找到合适的位置，建议从后往前面比，若是比最后一位小，则向前移动一位，否则就直接找到该位置
            for(int j=i-1;j>=0;j--) {
                //如果当前待排序的数比这一个排序的数大，则跳出循环，否则交换位置
                if(a[j+1]>a[j]) {
                    break;
                }else {
                        //这种每次比较后都马上移动，每次都定义临时变量，我们其实可以找到位置，最后再出入一次即可
                        int temp = a[j+1];
                        a[j+1]=a[j];
                        a[j]=temp;
                    }
                }
            }
            return a;
    }
    /**
     * 插入排序改进版，找到位置最后才插入
     * @param a
     * @return
     */
    public static int[] sort2(int[] a) {
        //假设第一个记录为已经待排序好的记录，那么要比较a.length-1个记录，所以外层循环是a.length-1次 
        //这里可以直接i=1从第二位开始处理也一样
        for(int i=1;i<a.length;i++) {
            //缓存待排序的记录
            int temp = a[i];
            int j;//这个是待插入的位置-1
            //跟前面已排序的记录做对比，找到合适的位置，建议从后往前面比，若是比最后一位小，则向前移动一位，否则就直接找到该位置
            for(j=i-1;j>=0;j--) {
                //如果当前待排序的数比这一个排序的数大，则跳出循环，否则交换位置
                if(temp>a[j]) {
                    break;
                }else {
                    //把当前记录往后面移动一位
                    a[j+1]=a[j];
                }
            }
            a[j+1]=temp;
        }
            return a;
    }
    public static void main(String[] args) {
        int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
        System.out.print("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        System.out.println();
        System.out.print("sort1：");
        int[] a1 = sort1(a);
        int[] a2 = sort2(a);
        for (int i = 0; i < a1.length; i++) {
            System.out.print(a1[i]+" ");
        }
        System.out.println();
        System.out.print("sort2：");
        for (int i = 0; i < a2.length; i++) {
            System.out.print(a2[i]+" ");
        }
    }
}

上面有两种实现方法，第二种sort2比较好，不用每次都新建temp;