Python排序算法-插入排序

插入排序算，和选择排序算法类似，也是选取一个元素，向前插入到合适的位置，前面的元素逐个向后移动。

• 实现方式

通过两层循环的方式，遍历整个列表：

• 列表的长度为n，即列表所有元素的表示范围为：[0,n-1]
• 外层循环：i从1开始至尾部[n-1]结束，从 1开始（即nums[1]）取出元素base，作为与前面进行比较的基数，与前面已排序列表元素进行比较。因此外层列表的范围为nums[1,n-1]，循环for的写法为：for i in range(n)
• 内层循环：j从[i-1]开始至0结束，倒序方式先从[i-1]位置取出元素与base(nums[i])比较，如果nums[j]>base，将nums[j]向后移动一位，直到找到base大于nums[j]的位置，或者已经到列表最左侧（即0位置），循环结束。

需要注意的一点是，在while循环结束后，此时j已经到了合适位置的前一个位置，因此插入base时，j的下标需要j+1才能插入到正确位置。

# 插入排序
# 取出排序后的一个元素，与前面元素相比，插入对应的位置。
def insertion_sort(nums:list[int]):
    n=len(nums)
    for i in range(n):
        # 取出排序后的第一个元素base
        base=nums[i]
        j=i-1
        # 将比自己大的元素向后移动
        while j>=0 and nums[j]>base:
            nums[j+1]=nums[j]
            j-=1
        # 注意下标j+1的含义，在while循环中j已经跑到前一个位置了，因此需要j+1
        nums[j+1]=base

if __name__=="__main__":
    nums = [62, 65, 51, 15, 30, 63, 37, 8, 55, 70, 13, 84, 46, 44, 86, 11, 91, 10, 47, 3, 96, 9, 36, 54, 24, 55, 72,
            29, 45]
    insertion_sort(nums)
    print(nums)