插入排序：
类似于打扑克
把列表[0]当作一个有序数列，将第2个数插入到序列中正确的位置，
把列表[0, 1]当作一个有序数列，将第3个数插入到序列中正确的位置
...
时间复杂度：O(n^2)
适用场景：每次插入都要移动数据，且只移动1位，在小规模数据集或”基本有序“数据集情况下，
插入排序会比较高效，但若数据集比较大时，效率就会比较低，优化方案：希尔排序
剖析：插入到某个位置（index），就说明[index, end_index] 区间内的值都需要 + 1
思路一：
1、从 [0, end_index] 先找到 end_index + 1 正确的位置(index)
2、将 [index, end_index] 的值都向后移动一位
3、将 end_index + 1 的值 赋值给 index
迭代实现：
def insert_sort_iteration(datas):
def _insert(index, data_index):
next_data = datas[index]
datas[index] = datas[data_index]
for index in range(index, data_index):
temp = datas[index + 1]
datas[index + 1] = next_data
next_data = temp
length = len(datas)
for j in range(1, length):
data = datas[j]
for i in range(0, j):
if datas[i] > data:
_insert(i, j)
break
return datas
递归实现：
def insert_sort_recursion(datas):
def _insert(index, data_index):
next_data = datas[index]
datas[index] = datas[data_index]
for i in range(index, data_index):
temp = datas[i + 1]
datas[i + 1] = next_data
next_data = temp
def _find_right_position(end_index):
target_index = end_index + 1
if target_index == length:
return
target_data = datas[target_index]
for index in range(0, target_index):
if datas[index] > target_data:
_insert(index, target_index)
break
_find_right_position(end_index + 1)
length = len(datas)
_find_right_position(0)
return datas
思路二：
将思路一中的 1、2 合并起来，即 ”边移动边找正确的位置“,
”挖坑“思想应用：
要把 end_index + 1 插入到 [0, end_index]的正确位置中：
将 end_index + 1 挖出来放到一边，值记作 current, 如果前一个值大于 current,
则把前一个值挖出填到坑中，然后再继续比较前面的值
1、遇到比 current 小的，这时停止循环比较，把 current 填到坑中
2、都没有比 current 小的，current 放在首位
迭代实现：
def insert_sort_iteration2(datas):
length = len(datas)
for index in range(0, length):
pre_index = index - 1
current = datas[index]
while pre_index >= 0:
if datas[pre_index] <= current:
break
datas[pre_index + 1] = datas[pre_index]
pre_index -= 1
datas[pre_index + 1] = current
return datas
递归实现：
def insert_sort_recursion2(datas):
def _move_insert(pre_index, target):
if pre_index < 0 or datas[pre_index] <= target:
datas[pre_index + 1] = target
return
datas[pre_index + 1] = datas[pre_index]
_move_insert(pre_index - 1, target)
length = len(datas)
for index in range(0, length):
_move_insert(index - 1, datas[index])
return datas