python---插入排序的实现

插入排序

思想

​ 列表被分为有序区和无序区两个部分, 最初有序区只有一个元素, 每次从无序区选择一个元素, 插入到有序区的位置, 直到无序区变空

import random
from cal_time import get_running_time


@get_running_time
def insert_sort(li):
    n = len(li)

    for i in range(1, n):  # 执行n-1趟, i为要插入元素的下标

        tmp = li[i]  # 要插入的值
        j = i - 1

        # j=-1停止后挪, li[j]比插入值小停止后挪
        while j >= 0 and li[j] > tmp:  # 往后挪就循环, 2个条件都满足
            li[j + 1] = li[j]
            j -= 1

        # 循环结束时, j要么是-1, 要么是比插入值小的值
        li[j + 1] = tmp

    return li


@get_running_time
def insert_sort2(li):
    n = len(li)

    for i in range(1, n):       # 执行n-1趟
        tmp = li[i]
        for j in range(i - 1, -1, -1):

            if li[j] > tmp:     # li[j]比插入值大 后挪
                li[j + 1] = li[j]
            else:               # li[j]比插入值小 停止后挪
                li[j + 1] = tmp
                break

        # 循环结束时, 如果 j= 0,
        if li[0] > tmp:
            li[0] = tmp

    return li


li = [i for i in range(0, 10000, 4)]
random.shuffle(li)
print(li)
print(insert_sort(li))
print(insert_sort2(li))