插入排序是最简单最直接，最符合人类思维的排序方式。
和打扑克一样，将未排序的数值插入到已排序的数列中。将待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。
数组：[8,20,9,1,34,27,1,10]插入排序如下：
先将0号元素8看做一个有序数列，即已经排好过的，从20开始，依次将后面的数插入。pre代表已经排好的最后元素，cur表示当前要排序的数，插入排序很简单，我想下面这张图已经表达的足够清晰：
插入排序是稳定算法，当待插入的数和有序数组中某个元素相同的时候，就插入到其后面，因为它本身就在有序数列的后面。
插入排序具体实现插入这个操作时，是将大于待排数值的每个元素依次向后移，直到找到属于它的位置。
Python实现：
def insertSort(arr):
l = len(arr)
if l <= 1:
return
for i in range(0,l-1):
pre_index = i
cur = arr[pre_index+1]
while cur <= arr[pre_index] and pre_index>=0:
arr[pre_index+1] = arr[pre_index] #依次后移
pre_index -= 1
if pre_index>=0:
arr[pre_index+1] = cur
