插入排序算法（Python实现，图文并茂）

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

把 n 个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含 1 个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复 n-1 次可完成排序过程。

例如，有一组初始化数组 [8，2，5，9，7]，把数组中的数据分成两个区域，已排序区域和未排序区域，初始化的时候所有的数据都处在未排序区域中，已排序区域是空的。

1) 第一轮排序，从未排序区域中随机拿出一个数字，既然是随机，那么我们就获取第一个，然后插入到已排序区域中，如果已排序区域是空，那么就不做比较，默认自身已经是有序的了。


2) 第二轮排序，继续从未排序区域中拿出一个数，插入到已排序区域中，这个时候要遍历已排序区域中的数字遍历做比较，比大比小取决于我们是想升序排还是想倒序排，这里按升序排序。


3) 第三轮排序，排 5。


4) 第四轮排序，排 9。


5) 第五轮排序，排 7。


6) 排序结束。

【实例】　利用插入排序对序列 [11，11，22，33，33，36，39，44，55，66，69，77，88，99] 进行排序。

def insertion_sort(arr):
    """插入排序"""
    # 第一层 for 表示循环插入的遍数
    for i in range(1, len(arr)):
        # 设置当前需要插入的元素
        current = arr[i]
        # 与当前元素比较的比较元素
        pre_index = i - 1
        while pre_index >= 0 and arr[pre_index] > current:
            # 当比较元素大于当前元素则把比较元素后移
            arr[pre_index + 1] = arr[pre_index]
            # 往前选择下一个比较元素
            pre_index -= 1
        # 当比较元素小于当前元素，则将当前元素插入在其后面
        arr[pre_index + 1] = current
    return arr

print('排序后的结果为：')
print(insertion_sort([11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]))

运行程序，输出如下：

排序后的结果为:
[11,11,22,33,33,36,39,44,55,66,69,77,88,99]