"""
插入排序是一種簡單直覺的排序算法。它的工作原理是通過建構有序序列,對于未排序資料,在已排序序列中從後向前掃描,找到相應位置并插入。
插入排序在實作上,在從後向前掃描過程中,需要反複把已排序元素逐漸向後挪位,為最新元素提供插入空間。
"""
#第一次嘗試
def insert_sort1(my_list):
for i in range(1,len(my_list)):
insert_element = i
for j in range(i,0,-1):
if my_list[j-1] > my_list[insert_element]:
my_list[j-1],my_list[insert_element] = my_list[insert_element],my_list[j-1]
insert_element -= 1
#第二次嘗試
def insert_sort2(my_list):
"""
:param my_list:
:return:
需要交換時,插入元素位置減1,for循環自動減1(滿足要求),如果比較時出現不需要交換情況,說明之後已經不需要再進行比較了(前面的一定更小)
此時直接break退出内層循環(也就是最優時間複雜度優化)
反向for循環隻能取到1,不能取到0,要想取到0就需要循環變量做減1操作,是以循環範圍均需要加1
"""
for i in range(1,len(my_list)):
for j in range(i,0,-1):
if my_list[j-1] > my_list[j]:
my_list[j-1],my_list[j] = my_list[j],my_list[j-1]
else:
break
#第三次嘗試
def insert_sort3(my_list):
for i in range(1, len(my_list)):
while i >0:
if my_list[i - 1] > my_list[i]:
my_list[i - 1], my_list[i] = my_list[i], my_list[i - 1]
i -=1
else:
break
if __name__ == '__main__':
my_list = [35, 20, 15, 18, 45, 14, 20,77, 98, 66, 82]
insert_sort3(my_list)
print(my_list)