时间复杂度:O(n^2)
思想：维持一个已排好的字列表，其位置始终在列表的前部，然后逐步扩大这个字列表至全部，类似正例扑克牌的过程。从后半部分取出一个，然后找他应该在前面列表的位置。
比对和移动的图解如图所示：
def insertSort(alist): ‘‘‘ 插入排序 :param alist: :return: ‘‘‘ for index in range(1,len(alist)): currentvalue = alist[index] position = index while alist[position - 1] > currentvalue and position >0: alist[position] = alist[position -1] position = position -1 alist[position] = currentvalue #插入新项 alist = [54, 26, 93, 17, 77, 31, 44, 55, 20] insertSort(alist) print(alist)
原文：https://www.cnblogs.com/yeshengCqupt/p/13336355.html