插入排序是排序中最基本的了，它的效率不高，但是却比桶排序之类的算法更精妙，本质上此算法开始挖掘程序的时间复杂性，本质上时间复杂性比空间复杂性更重要，如果给我足够的空间我可以一眼看穿任何事，然而时间却会越发冲淡一切，时间拖得越久越对解决问题不利，计算机的重要性就在于其单位时间处理问题的能力而不是它能如何好的利用空间，因此比较排序算法是比非比较算法更精密的，循环本质上就是计算机特有的概念，而递归则不是，数学上早就有了递归的概念，但是数学的发明者--人类却不会用循环来解决任何问题，因此数学上根本就没有循环的任何概念，循环意味着一个一个尝试而不是智能定位，循环意味着需要将大量时间花在循环本身上，因此对于计算机而言，时间是更值得压缩的而不是空间，空间仅仅与机器的寄存器，cache，内存，磁盘，带宽有关系，而和计算机本身的处理能力关系并不大。

一般的教科书总是将冒泡排序排到最基本的位置，认为那是最傻的算法，其实插入排序更加基本，插入算法实现的很单纯，就是将一个元素取出，然后插入到已经排序的序列中，试想如果序列初始本身就是几乎已经排过序的，那么速度就会很快，反之如果序列起初是逆序，那么速度将会极其慢，它慢就慢在每一个元素只能一个一个和前面的已排序序列比较，而不能一下子跳跃好几个元素，于是希尔排序解决了这一个问题，希尔排序的精髓在于先将待排序列排序成一个大致有序的序列，注意这个大致排序的过程其实也是一系列的插入排序，只不过不是一个一个移动元素的，而是按照一个步长移动的，效率肯定比一个一个移动要高，比如初始步长为d，按照一个函数递减d，当d为1的时候，就是普通的插入排序过程，但是此时由于前面比较大的d已经将数据排列的大致有序了，那么现在的插入排序就简单了，而前面的大致排序的过程比精确排序的开销要小的多，随着步长d减小，开销本应增大，但是由于大步长的补偿，因此开销很稳定，这就是希尔排序的精髓，希尔排序的时间复杂度和插入排序一样，都是O(n^2)，单单从时间复杂度不能看出算法的优劣，各种算法都有自己的适用范围。

 本文转自 dog250 51CTO博客，原文链接:http://blog.51cto.com/dog250/1274006