一、插入排序

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

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

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

二、希尔排序

基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

java实现

public class XiEr {
    public static void main(String[] args) {
        //希尔排序
        int[] a = {49,38,65,97,76,13,27,49,78,34,12,64,1};
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        //主要是取增量d
        int d = a.length;
        while(true) {
            d=d/2;
            //开始进行分组插入排序,对d组进行排序，到最后d=1 就是一组排序
            for(int x=0;x<d;x++) {
                //每一组分别进行直接插入排序
                for(int i=x+d;i<a.length;i=i+d) {
                    //缓存待排序的记录
                    int temp = a[i];
                    int j;//这个是待插入的位置-1
                    //跟前面已排序的记录做对比，找到合适的位置，建议从后往前面比，若是比最后一位小，则向前移动一位，否则就直接找到该位置
                    for(j=i-d;j>=0;j=j-d) {
                        //如果当前待排序的数比这一个排序的数大，则跳出循环，否则交换位置
                        if(temp>a[j]) {
                            break;
                        }else {
                            //把当前记录往后面移动一位
                            a[j+d]=a[j];
                        }
                    }
                    a[j+d]=temp;
                }
            }
            //因为可能会只有一个元素
            if(d == 1||d==0){
                break;
            }
        }
          System.out.println();
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i]+" ");
            }
    }
}