插入排序
插入排序的主要思想是从无到有的构建一个有序队列。假设一串数字：d1, d2, d3...di,dj...dn。假设di之前的串都是有序的，那我们只需要从d(i-1)开始将数字与di比较，比di大的交换，这样就能将di插入到有序队列的制定位置。就先纸牌游戏一样，我左手有一堆刚得到的乱序的牌，我想拿出第一张放在右手，然后在拿出第二张与右手的比较并放在指定的位置。图示如下：
实现代码如下：
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);}希尔排序
希尔排序是用于优化插入排序的。
基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列 中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
操作方式如下：
1.首先指定序列的跨度d。一般是长度的1/2。
2.从下标为0开始，将第0，0+d,0+2d...0+nd的数进行排序，排序方式使用插入排序。在拿将第1，1+d,1+2d...1+nd，排序，一次类推。直到达到第n,且n+d<数组长度。
3，从新计算跨度d=原有跨度的1/2，继续执行以上两个流程。
图示如下：
代码实现如下：
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[j-span]) {int temp = arr[end];arr[end] = arr[end-span];arr[end-span] = temp;end=end-span;}times = times + j/span;}}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);}