插入排序
思想
列表被分为有序区和无序区两个部分, 最初有序区只有一个元素, 每次从无序区选择一个元素, 插入到有序区的位置, 直到无序区变空
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 lili = [i for i in range(0, 10000, 4)]
random.shuffle(li)
print(li)
print(insert_sort(li))
print(insert_sort2(li))
