插入排序是一种简单直观的排序方法，其基本思想在于每次将待排序的一个记录，按其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成。由插入排序的思想可以引申为三个重要的排序算法：直接插入排序，折半插入排序和希尔排序。
直接插入排序
直接插入排序是最简单的插入排序算法。假设在排序过程中，待排序表L[1…n]在某次排序过程中的某一时刻状态如下：
| 有序序列L[1…i-1] | L(i) | 无序序列L[i+1…n] |
为了实现元素L(i)插入到有序序列L[1…i-1]中，需要做如下操作：
- 找出L(i)在L[1…i-1]中插入的位置K
- 将L[k…i-1]中所有元素全部后移一位
- 将L(i)复制到L(k)
为了实现对L[1…n]的排序，可以将L(2)-L(n)依次插入到前面已经排好序的子序列中，初始假定L[1]是一个已经排好序的子序列。上述操作执行n-1次就哼得到一个有序的表。插入排序在实现上通常采用就地排序(空间复杂度O(1))，因而从后先前的比较过程中，需要反复把已排序元素逐步向后挪位，为新的元素提供插入的空间。
示例代码
public static void insert1(int[] arr){ int length = arr.length; int i=0,j=0; for(i=1; i<length;i++){ //依次将A[2]~A[n]插入到前面已排序序列中 if(arr[i]<arr[i-1]){ //若A[i]的关键码小于其前驱,需将A[i]插入到有序表中 int key=arr[i]; //复制欲插入的值 for(j=i-1; j>=0 && key<arr[j]; j--) //从后往前不断将K与序列中的值进行比较,小于则将其后移 arr[j+1] = arr[j]; if(j < 0) //j小于0表明欲插入的值比序列中的值都小 arr[0] = key; //将关键字插入到0的位置 else arr[j+1] = key; } } }
折半插入排序
在直接插入排序时，总是边比较边移动元素(第二个for循环)。折半插入是将查找的移动分开，先通过折半查找找到关键字插入的位置，然后同意地移动待插入位置之后的所有元素。如果排序表为顺序表时，则可以使用折半插入算法。
示例代码
public static void insert2(int[] arr){ int i,j,low,high,mid; for(i=1;i<arr.length;i++){ low = 0; high = i-1; while(low <= high){ //通过折半查找找出欲插入的位置 mid = low + (high-low)/2; if(arr[i] < arr[mid]) high = mid - 1; else low = mid + 1; } int key = arr[i]; for(j=i-1;j>=high+1;j--)//将元素统一后移 arr[j+1] = arr[j]; arr[high+1] = key; } }
折半插入排序只是提高了查找的速率，但是并没有改变元素移动的次数，因为总的时间复杂度仍为O(n^2)
希尔排序
从前面可以看出，如果初始序列基本有序且数据量不大时,直插和折半插入的效果会很好(减少移动)。由此有人提出了希尔排序。其思想是先将待排序表分割成若干个形如L[i，i+d，i+2d，…i+kd]的"特殊"子表，分别进行直接插入排序，当整个表中的元素已”基本有序“时，在对全体记录进行一次直接插入排序。希尔排序的排序过程如下：
先取一个小于n(n为元素的个数)的步长d1，把表中的全部记录分组，距离为d1的倍数的记录在同一个组当中。如记录49，38，65，97，76，13，27，49，55，04，99，我们设定步长为d1=4,则分成的组为[49，76，55]，[38，13，04]，[65，27，99]，[97，49]。然后在各组中进行直接插入排序；然后取第二个步长d2<d1，重复上面的过程，直到所取的d=1，即所有的记录放在同一个组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，所以可以很快得到最终结果。不过目前没有得到一个最好的增序(d1,d2..dn)，希尔提出的方法是d1=n/2，di+1=di/2。
示例代码
public static void shellsort(int[] arr){ for(int dk=arr.length/2;dk>0;dk=dk/2){//设定步长 for(int i=dk;i<arr.length;i++){ //进行插排 if(arr[i]<arr[i-dk]){ //比较的跨度改为dk int key = arr[i]; int j=0; for(j=i-dk; j>=0 && key<arr[j];j-=dk) //移动的跨度也改为dk arr[j+dk] = arr[j]; arr[j+dk] = key; } } } }