基本思想
首先，我们将数组中的数据分为已排序区间和未排序区间，初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
两种操作：比较和移动
代码示例
/**
处理流程： 设数组为a[0…n-1]。
1. 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
2.将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
3. i++并重复第二步直到i==n-1。排序完成。
* 直接选择排序与直接插入排序对比理解： 直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，
* 所不同的是直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，
* 而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。
*
* @author yeoggc
*
*/
public class 直接插入排序 {
// 打印序列
public void printPart(int[] list, int begin, int end) {
for (int i = 0; i < begin; i++) {
System.out.print("\t");
}
for (int i = begin; i <= end; i++) {
System.out.print(list[i] + "\t");
}
System.out.println();
}
public static void main(String[] args) {
// 初始化一个随机序列
// final int MAX_SIZE = 10;
// int[] array = new int[MAX_SIZE];
// Random random = new Random();
// for (int i = 0; i < MAX_SIZE; i++) {
// array[i] = random.nextInt(MAX_SIZE);
// }
// 初始化一个固定值序列
int[] array = { 0, 6, 7, 4, 4, 1, 0, 6, 2, 3 };
直接插入排序 insert = new 直接插入排序();
System.out.print("排序前:\t");
insert.printPart(array, 0, array.length - 1);
insert.insertSort(array);
System.out.print("排序后:\t");
insert.printPart(array, 0, array.length - 1);
}
private void insertSort(int[] array) {
// 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
// i表示待排序元素在数组的下标
for (int i = 1; i < array.length; i++) {
int temp = array[i];// 待排序的数据
int j = 0;// 有序区中待排序元素的下标，初始时，从有序区最后一个元素开始比较起
// 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
for (j = i - 1; j >= 0 && array[j] > temp; j--) {
array[j + 1] = array[j];
}
array[j + 1] = temp;// 把待排序的元素值放入合适的位置
System.out.format("i = %d:\t", i);
printPart(array, 0, i);
}
}
}
算法分析
直接插入排序是稳定的排序。
关于各种算法的稳定性分析可以参考
文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则每个待插入的记录只需要比较一次就能够找到合适的位置插入，故算法的时间复杂度为O(n)，这时最好的情况。若初态为反序，则第i个待插入记录需要比较i+1次才能找到合适位置插入，故时间复杂度为O(n2)，这时最坏的情况。
直接插入排序的平均时间复杂度为O(n2)。
