插入排序/希尔排序

       插入排序的核心思想：假设某一个数的左边时数据时有序的，哪他只要再有序的数组中找到自己的为止插入即可

过程如下：

       1. 取数组的第n(n>=2)位数字d(n)，一次比较d(n)与1到(n-1)位数字的大小。如果d(n) < d(n-1)，则交换两个数，直到比较到d(n) > d(n-x)为止。

        2. 取第n+1位的数字d(n+1)继续以上的步骤。

 代码实现如下：

public class InsertSort {
    public static void main(String[] args){
        int[] a= new int[]{5,4, 7, 2,22, 2, 6, 7, 3, 9, 15, 20, 23, 19, 17};
        insertSort(a);
        System.out.print("最终排序结果：");
        for(int i=0; i< a.length; i++){
            System.out.print(a[i] + " ");
        }
    }

    public static void insertSort(int [] arr){
        int times = 0;
        for(int i= 0; i < arr.length; i++){
            //插入排序法 在比较数组中找到当前的数据的位置并插入
            int end = i;
            while (end-1 >= 0 && arr[end] < arr[end-1]) {
                int temp = arr[end];
                arr[end] = arr[end-1];
                arr[end-1] = temp;
                end--;
                times++;
            }
        }
        System.out.println("次数：" + times);
    }
}

      希尔排序时对插入排序的优化。其思想是：将整个数组分为n组，对每一组进行插入排序。直到n组中每一个组都只有一个元素为止。

      过程如下：

      1.将数组分为 length/2 组。0、n/2；1，n/2 + 1；...； n/2 -1，n。并分别对这些组内的数据使用插入排序法排序。

      2.再将数组分为 length/2/2 组，并对这些组的组内数据进行插入排序。

      3.重复以上步骤，每次的分组的长度变为两倍。直到length/(2d) = 1结束。

实现过程如下：

public class ShellSort {

    public static void main(String[] args){
        int[] a= new int[]{5,4, 7, 2,22, 2, 6, 7, 3, 9, 15, 20, 23, 19, 17};
        shellSort(a, a.length/2);
        System.out.print("最终排序结果：");
        for(int i=0; i< a.length; i++){
            System.out.print(a[i] + " ");
        }
    }

    public static void shellSort(int [] arr, int span){
        if(span == 0) return;
        int times = 0;
        for(int i= 0; i + span< arr.length; i++){
            //分段排序
            int start = i + span;
            for(int j = i + span;  j < arr.length; j = j+span) {
                //插入排序法 在比较数组中找到当前的数据的位置并插入
                int end = j;
                while (end-span >= start && arr[end] < arr[end-span]) {
                    int temp = arr[end];
                    arr[end] = arr[end-span];
                    arr[end-span] = temp;
                    end=end-span;
                    times++;
                }
            }
        }
        System.out.print(span + "排序结果：");
        for(int i=0; i< arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.print("次数：" + times);
        System.out.println("");
        shellSort(arr, span/2);
    }
}