python算法(三) 插入排序

算法分析

给出一个乱序的数列,将这个数列按从小大到(从大到小)重新排列

插入排序的的逻辑是从选这个数列,一个一个的插入一到一个新的数列中

如下:

初始数列: 5 1 3 7 9 6 4 2

第一个数插入空的数列

5

第二个数 1 < 5

插入5所在的位置

新的数列变成:

1 5

第三个数3

3>1 往后找

3 < 5 插入当前位置 , 新的数列变成

1 3 5

第四个数7

7>1 往后

7>3往后

7>5往后

因为5是最后一个数了,所以插在最后,新的数列变成

1 3 5 7

以此类推.将所有的数都插入新的数列即可

代码实现

# 作者:爱编程的章老师
# 创建:2021/1/23 7:47 下午 
# 邮箱:[email protected]
# 微信:slxxfl
# 微信公众号:A卫隆少儿编程
# 格言:给自己的生活增加一份向上的力，每都进步一点点

from random import shuffle

"""插入排序"""
# 将目标数组中的元素按从小到大的顺序进行重排.
def insertion_sort(num_list: list):
    result = [numlist[0]]
    for i in range(1, len(num_list)):
        for j in range(len(result)):
            # 如果要排的数比当前循环到的数要小
            # 如果比当前循环到的数要到,就继续循环直到最后
            if num_list[i] < result[j]:
            # 找到比当前要插入的元素大的位置,插入该位置
                result.insert(j, num_list[i])
                break
            # 如果查找到最后都没有找到比当前元素大的数,则插入新数列的末尾
            if j == len(result) - 1:
                result.append(num_list[i])
    return result

# 示例
num_list_demo = [x for x in range(100)]
shuffle(num_list_demo)
print(num_list_demo)
res = insertion_sort(num_list_demo)
print(res)