1.引例
打牌习惯性地将牌按照一定大小顺序排列，在摸牌过程中，每摸到一张牌，就会按照大小规则将它插入到手中的牌，这就是插入排序。
2.算法描述
插入排序分为两组数据，已经排序的数据。等待排序的数据，从等待排序的数据，向已经排序的数据中对比插入。
3.算法示图
4.代码实现
def InsertionSort(array):
# 从第二个元素开始遍历
for i in range(1,len(array)):
# 需要排序的元素
target = array[i]
# j表示已经排序好的数量
j = i-1
# 所有元素向后移动，直至target找到合适的位置
while(j>=0 and target<array[j]):
# 数据右移
array[j+1] = array[j]
j -= 1
# 如果j=0，说明target需要插入第一位。注意：此时while中判断为array[-1]，在某些编译器中会出现数组值错误
# 避免错误的解决方式(在pythona中无需添加这段代码,fortran中需要添加，否则报错越界,需要注意的是在java中while判断中会出现array[-1]的情形,array[-1]不被准许，但由于j>=0已经为False，所以程序不再往后读取，直接退出循环，但某些编译器可能会出现问题)
if j==0:
break;
array[j+1] = target
print(array)
return array
if __name__ == '__main__':
arr = [344,4,345,78,5,68,9,4879,1548,44,23,99,14785,457,233]
InsertionSort(arr)
5.运行结果
[4, 344, 345, 78, 5, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 344, 345, 78, 5, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 78, 344, 345, 5, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 78, 344, 345, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 68, 78, 344, 345, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 68, 78, 344, 345, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 68, 78, 344, 345, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 68, 78, 344, 345, 1548, 4879, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 44, 68, 78, 344, 345, 1548, 4879, 23, 99, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 344, 345, 1548, 4879, 99, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 344, 345, 1548, 4879, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 344, 345, 1548, 4879, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 344, 345, 457, 1548, 4879, 14785, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 233, 344, 345, 457, 1548, 4879, 14785]
6.来源——阳光沙滩微信公众号
链接：阳光沙滩插入排序算法
