本文共 1845 字，大约阅读时间需要 6 分钟。
一，插入排序介绍
插入排序是基于比较的排序。所谓的基于比较，就是通过比较数组中的元素，看谁大谁小，根据结果来调整元素的位置。
因此，对于这类排序，就有两种基本的操作：①比较操作； ②交换操作
其中，对于交换操作，可以优化成移动操作，即不直接进行两个元素的交换，还是用一个枢轴元素(tmp)将当前元素先保存起来，然后执行移动操作，待确定了最终位置后，再将当前元素放入合适的位置。（下面的插入排序就用到了这个技巧）--因为，交换操作需要三次赋值，而移动操作只需要一次赋值！
有些排序算法，比较次数比较多，而移动次数比较少，而有些则相反。比如，归并排序和快速排序，前者移动次数比较多，而后者比较次数比较多。
这里主要介绍插入排序
二，插入排序算法分析
插入排序算法有种递归的思想在里面，它由N-1趟排序组成。初始时，只考虑数组下标0处的元素，只有一个元素，显然是有序的。
然后第一趟 对下标 1 处的元素进行排序，保证数组[0,1]上的元素有序；
第二趟 对下标 2 处的元素进行排序，保证数组[0,2]上的元素有序；
.....
.....
第N-1趟对下标 N-1 处的元素进行排序，保证数组[0,N-1]上的元素有序，也就是整个数组有序了。
它的递归思想就体现在：当对位置 i 处的元素进行排序时，[0,i-1]上的元素一定是已经有序的了。
三，插入排序算法实现
1 public class InsertSort{ 2 3 public static > void insertSort(T[] a){ 4 for(int p = 1; p < a.length; p++) 5 { 6 T tmp = a[p];//保存当前位置p的元素，其中[0,p-1]已经有序 7 int j; 8 for(j = p; j > 0 && tmp.compareTo(a[j-1]) < 0; j--) 9 {10 a[j] = a[j-1];//后移一位11 }12 a[j] = tmp;//插入到合适的位置13 }14 }15 16 //for test purpose17 public static void main(String[] args) {18 Integer[] arr = {34,8,64,51,32,21};19 insertSort(arr);20 for (Integer i : arr) {21 System.out.print(i + " ");22 }23 }24 }
四，复杂度分析
①插入排序的时间复杂度 就是判断比较次数有多少，而比较次数与 待排数组的初始顺序有关，当待排数组有序时，没有移动操作（第8行for不成立），此时复杂度为O(N)，当待排数组是逆序时，比较次数达到最大--对于下标 i 处的元素，需要比较 i-1 次。总的比较次数：1+2+...+N-1 ，故时间复杂度为O(N^2)
①可以看出，算法中只用到了一个临时变量（第6行），故空间复杂度为O(1)
其实，插入排序的比较次数与数组的逆序数相关，因为插入排序在将某个元素插入到合适位置时（代码第12行），其实就是消除这个元素的逆序数。
由定理：N个互异数的数组的平均逆序数是 N(N-1)/4，可知：基于相邻元素之间的比较和交换的算法的时间复杂度的一个下界为O(N^2)
比较冒泡排序啊。。。。它采用的思路是：相邻两个元素比较，将小的放在前头。故冒泡排序的时间复杂度为O(N^2)。。。
基于上面这个定理，另外一个排序算法：希尔排序，采用了增量序列。因此，它可能获得一个更好的时间复杂度。
比如，当希尔排序使用Hibbard增量序列时，它的最坏运行时间为O(N3/2)
五，参考资料
《数据结构与算法分析》MAW著
本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/p/5517667.html，如需转载请自行联系原作者