插入排序
插入排序的核心思想：假设某一个数的左边时数据时有序的，哪他只要再有序的数组中找到自己的为止插入即可
过程如下：
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);}
}