# 实现原理

将数组分为两部分，左边为有序集合，右边为无序集合，
取右边集合的第一个元素与左边的集合挨个对比，直到插入合适的位置。

inputArr = [10, 34, 29, 4, 0, 34, 5, 4, 36, 1, 8]

length = len(inputArr)

print("未排序集合:{0}".format(inputArr))
# 从第1个元素开始作为无须集合
for rightIndex in range(1, length):
    rightItem = inputArr[rightIndex]
    # 待插入位置
    insertIndex = rightIndex
    # 查找待插入位置
    while(insertIndex != 0):
        if(rightItem > inputArr[insertIndex-1]):
            break
        insertIndex -= 1

    if(rightIndex == insertIndex):
        continue
    # 向后平移元素
    while (insertIndex != rightIndex):
        inputArr[rightIndex] = inputArr[rightIndex-1]
        rightIndex -= 1
    # 插入正确的位置
    inputArr[insertIndex] = rightItem

print("已排序集合:{0}".format(inputArr))

inputArr = [10, 34, 29, 4, 0, 34, 5, 4, 36, 1, 8]
length = len(inputArr)

print("未排序集合:{0}".format(inputArr))

# 从第1个元素开始作为无须集合
for rightIndex in range(1, length):
    # 从有序集合由右到左依次比较知道插入正确的位置
    while(rightIndex != 0):
        if(inputArr[rightIndex] > inputArr[rightIndex-1]):
            break
        inputArr[rightIndex], inputArr[rightIndex-1]\
            = inputArr[rightIndex-1], inputArr[rightIndex]
        rightIndex -= 1

print("已排序集合:{0}".format(inputArr))