**
【千锤百炼Python—1】：十大排序算法总结（动画+代码）**
简单插入排序是排序算法系列的第五个要介绍的算法！
简单插入排序既属于比较类排序也属于内部排序。
一、算法原理 1. 算法原理插入排序（Insertion Sort）是一种简单直观的排序算法，属于插入排序的一种。
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
2. 算法步骤- 步骤一：从序列的第一个元素开始，将该元素视为已被排序的序列（目前该序列中仅包含一个元素）；
- 步骤二：从未排序序列中取出下一个元素，在已排序序列的元素中从后向前扫描；
- 步骤三：若待排序元素小于已排序序列中正在比较的元素，则将待排序元素继续前移；
- 步骤四：重复步骤三，直至从已排序元素中找到<=新元素的位置，并将新元素置于其后；
- 步骤五：重复上述步骤，直至所有元素排序完毕。
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
if __name__ == '__main__':
arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
sort = insertionSort(arr)
print(sort)
输出结果为：
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
