《算法技术手册》分析

在最好情况下，n个元素中每一个元素都在其正确的位置，因此插入排序将花费线性时间O(n)。不过提这个也许看起来是没有价值的（你会有多大几率排序一个有序序列呢？），不过却是很重要的，因为插入排序是本章中讨论的唯一基于比较的排序算法。

很多现实世界的数据都已经是部分有序了，所以若要使插入排序在现实数据上高效运行，优化和现实就会发生冲突。但是很不幸的，如果每一种输入数列排列出现概率是相等的，那么最优数据（所有元素已经有序）的概率仅仅是1/n!。当n=10时，360 000个输入数据才会出现一个。注意重复元素越多，插入排序的效率越高，因为插入排序需要执行更少的交换操作。

不幸的是，插入排序在随机数据面前太过于保守。如果所有n个元素都是不同的，而且数组是随机（数据的所有排列出现概率相等），那么每一个元素离其最终的位置平均距离是n/3[1]。所以在平均情况和最坏情况下，n个元素中的每个元素会被移动一个线性的距离，插入排序是二次方的运行时间，O(n2)。

插入排序对于基于值的数据效率很低，因为很多内存需要移位，以给新的值腾出位置。表4-1包含了在直接比较。我们将会执行10次随机实验，排序n个元素，最好和最坏结果将会被抛弃。这个表给出了剩余8次结果的平均值。注意这个实现是如何通过内存块移动而不是通过单独的内存交换来改善性能的。当数组大小加倍的时候，执行时间大约也会乘以4，整好验证了插入算法的O(n2)性能。即使使用了内存块移动来改善性能，插入排序仍然是二次的，因为使用内存块移动的插入排序的性能是原生插入排序性能的常数倍（大约1/7）。插入排序的问题是它是一种保守的算法（叫做本地移位排序），这类算法每个元素一次移动一个位置。

当插入排序排序基于值的数据时，交换元素的操作将会更加的高效，编译器能够产生更高效的代码，以图最少地执行高开销的内存存取操作。