前面说过最原始的复杂度为 O(n2) 的冒泡和选择排序，也跳跃到了复杂度为 O(n log n) 的快速排序，现在又再看一个复杂度同样为 O(n2) 的插入排序。从排序名称结合代码我们理解了为什么叫做冒泡或是选择，快速排序自认高名，那么何以这又谓之插入排序呢？是怎么插入，从左边往右边插，还是从右边往左边插，这得搞清它的排序原理：
它在列表较低的一端维护一个有序的子列表(从最左端一个元素开始)，并逐个将每个新元素(高端的)"插入"这个子列表。插入的时候遍历低端列表，找准位置插入便是，插入点后的元素需后移，当所有高端的元素插入完成了，整个列表就变得有序了。
整个排序操作示意图如下： 阅读全文 >>