Python之插入排序

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

import random


def insertionsort(arr: list) -> list:  # 实参要求是列表，函数返回列表
    if len(arr) <= 1:  # 如果是空列表或只有一个项的列表，返回列表
        return arr  # 结束程序，返回列表
    l = len(arr)  # 获取列表长度
    i = 1  # 索引变量，从1开始
    while i < l:
        value = arr[i]  # 获取列表中当前位置的value
        instertion = False  # 标记，是否交换数据
        for j in range(i):  # 从0号索引开始直到i,向前检查
            if value < arr[j]:  # 如果当前值小于列表前面某个值
                instertion = True  # 交换标签变量改为True
                break  # 结束循环循环
        if instertion:
            number = arr.pop(i)  # 删除并返回当前值
            arr.insert(j, number)  # 将删除的值插入目标位置
        print(arr, '------|', i)
        i += 1
    return arr


print('不重复数字的列表：')
numbers_list = random.sample(range(1, 50), 15)  # 非重复随机列表
print('原始列表：', numbers_list)
print(insertionsort(numbers_list))

print('有重复数字的列表：')
numbers_list = [random.randint(1, 10) for i in range(15)]  # 重复随机列表
print('原始列表：', numbers_list)
print(insertionsort(numbers_list))