插入排序（InsertionSort）可以说是最简单直观的排序算法了。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
通常以扑克牌举例： 右边新来的牌，与左边有序的老牌依次比较，最终插到合适的位置。
实现
- Basic： 新旧牌每次都要交换一下（两次操作：旧牌后移一位，新牌前移一位）。 （代码见下面基础版）
- Advanced： 每次比较，旧牌后移一位（一次操作）。新牌最后放到空位上。 （代码见下面改进版）
后者即为通常采用的in-place方式（即只需用到 O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
复杂度
平均时间复杂度： O(n^2)
最坏时间复杂度： O(n^2）
最优时间复杂度： O(n)
最坏空间复杂度： 总共 O(n) ，需要辅助空间 O(1)
图例
推荐VisuAlgo，一个数据结构和算法动态可视化的网站。
图片来源： 维基百科
图片来源： 【图解算法】排序算法——插入排序
python实现
基础版
Basic实现方法: 倒序遍历寻找元素arr[i]合适的插入位置
def InsertionSort(arr):
'''
插入排序思路： （扑克牌举例） 右边新来的牌，与左边有序的老牌依次比较，最终插到合适的位置。
实现：
Basic： 新旧牌每次都要交换一下（两次操作：旧牌后移一位，新牌前移一位）。
Advanced： 每次比较，旧牌后移一位（一次操作）。新牌最后放到空位上。
'''
n = len(arr)
for i in range(,n):
for j in range(i,,-):
if arr[j-]>arr[j]:
arr[j],arr[j-] = arr[j-],arr[j] # 交换
else:
break
改进版
Advanced实现方法： 每次比较，旧牌后移一位（一次操作）。新牌最后放到空位上。
（上面图例中第二张即直观表示了改进版的排序过程）
def InsertionSort(arr):
n = len(arr)
for i in range(,n):
temp = arr[i]
# j保存元素temp应该插入的位置
for j in range(i,-,-):
if arr[j-]>temp and j>:
arr[j] = arr[j-] # 后移即可
else:
break
arr[j] = temp