第63页 | 算法技术手册 | 阅读 ‧ 电子书库

结论

如图4-7所示，插入排序需要移动60个已经有序的元素。由于只有15次迭代，平均每次迭代要移动4个元素。最优性能出现在数组是顺序有序的时候，如果数组是逆序有序的时候，那么很显然是最坏的情况。如果这个数组是已经几乎有序，插入排序将会做得很好，因为只需要移动很少的元素。