插入排序分为直接插入排序和希尔排序
直接插入排序：
直接插入排序原理就是，假设前面n-1(n>=2)个元素已经排好序，现在要把第n个元素找到正确的位置并插入。
import java.util.Arrays; public class Main { static int[] array = {7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2,10,-3}; public static void main(String[] args) throws InterruptedException { System.out.println(Arrays.toString(array)); insertionSort(array); System.out.println(Arrays.toString(array)); } //插入排序 public static void insertionSort(int[] array){ int len = array.length; int counter = 1; for(int i=1;i<len;i++){ int temp = array[i]; //存储待排序的元素值 int insertPoint = i-1; //与待排序元素值作比较的元素的下标 while(insertPoint>=0 && array[insertPoint]>temp){ //当前元素比待排序元素大 array[insertPoint+1]= array[insertPoint]; //当前元素后移一位 insertPoint--; } array[insertPoint+1]= temp; //找到了插入位置，插入待排序元素 System.out.print("第"+counter+"轮排序结果："); display(array); counter++; } } private static void display(int[] array){ System.out.println(Arrays.toString(array)); } }
[7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2, 10, -3] 第1轮排序结果：[7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2, 10, -3] 第2轮排序结果：[7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2, 10, -3] 第3轮排序结果：[6, 7, 8, 9, 1, 4, 3, 2, 5, 0, -1, -2, 10, -3] 第4轮排序结果：[1, 6, 7, 8, 9, 4, 3, 2, 5, 0, -1, -2, 10, -3] 第5轮排序结果：[1, 4, 6, 7, 8, 9, 3, 2, 5, 0, -1, -2, 10, -3] 第6轮排序结果：[1, 3, 4, 6, 7, 8, 9, 2, 5, 0, -1, -2, 10, -3] 第7轮排序结果：[1, 2, 3, 4, 6, 7, 8, 9, 5, 0, -1, -2, 10, -3] 第8轮排序结果：[1, 2, 3, 4, 5, 6, 7, 8, 9, 0, -1, -2, 10, -3] 第9轮排序结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -2, 10, -3] 第10轮排序结果：[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -2, 10, -3] 第11轮排序结果：[-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -3] 第12轮排序结果：[-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, -3] 第13轮排序结果：[-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
希尔排序：实质就是分组插入排序，该方法又称缩小增量排序
原理：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
比如一个长度为12的数组，
第一步就是分成增量为6的小数组，一共6个，每一个都含有2个元素，对每一个小数组都进行直接插入排序
第二步就是将数组分成增量为3的小数组，一共有4个，每个都含有3个元素，对每个小数组都进行直接插入排序
第三步就是将整个数组进行直接插入排序。
分别是12/2=6,6/2=3,3/2=1，增量为1时，其实就是对整个数组进行操作。
==========================================
如果是奇数怎么办呢？
比如一个长度为13的数组
第一步还是分成增量为6的小数组，一共6个，但是第一个小数组会有3个元素，其他的分别有两个，然后对每个小数组进行直接插入排序
第二步分成增量为3的小数组，一共有4个，但是第一个小数组有5个元素，其他的分别有4个元素，然后对每个小数组进行直接插入排序
第三步就是将整个数组进行直接插入排序。
============================================
import java.util.Arrays; public class Main { static int[] array = {7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2,-3}; public static void main(String[] args) throws InterruptedException { System.out.println(Arrays.toString(array)); shellSort(array); System.out.println(Arrays.toString(array)); } static void shellSort(int a[]) { int n=a.length; int i, j, gap; for (gap = n / 2; gap > 0; gap /= 2) //步长 { for (i = 0; i < gap; i++) //直接插入排序 { for (j = i + gap; j < n; j += gap) { if (a[j] < a[j - gap]) { int temp = a[j]; int k = j - gap; while (k >= 0 && a[k] > temp) { a[k + gap] = a[k]; k -= gap; } a[k + gap] = temp; } } System.out.print("增量："+gap+" "); for(int k=i;k<n;k+=gap){ System.out.print(a[k]+" "); } System.out.println(""); } } } }
[7, 8, 9, 6, 1, 4, 3, 2, 5, 0, -1, -2, -3] 增量：6 -3 3 7 增量：6 2 8 增量：6 5 9 增量：6 0 6 增量：6 -1 1 增量：6 -2 4 增量：3 -3 0 3 6 7 增量：3 -1 1 2 8 增量：3 -2 4 5 9 增量：1 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 [-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
http://blog.csdn.net/u012152619/article/details/47306209
http://blog.csdn.net/morewindows/article/details/6668714