1、算法步骤

a. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

b. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

2、动图演示

3、代码

# 定义一个函数insertionSort，参数为一个列表arr
def insertionSort(arr):
    # 外层循环，遍历列表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
    # 返回排序后的列表arr
    return arr

打赏 支付宝打赏 微信打赏