插入排序
2020-12-17 13:33
标签：turn 最大的 位置 复杂 比较 insert sort 元素 逆向思维 将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数。即：序列的第一个元素，肯定是有序的，把第二个元素和第一个元素相比，插入到合适的位置，这样前两个元素就有序了，接着，把第三个元素插入到前面包含两个元素的有序列表中，以此类推，直至插完第n个数据。 ‘‘‘ ‘‘‘ 在最好的情况下，即序列已经是排好序的情况下，每次比较一次就退出while循环，则总比较次数是n-1次，时间复杂度是O(n) 插入排序 标签：turn 最大的 位置 复杂 比较 insert sort 元素 逆向思维 原文地址：https://www.cnblogs.com/kknote/p/14108533.html核心思想
正向思维
6和10比,6
6和8比，6
6和5比，6>5,结束
‘‘‘# @Time : ‘2020-12-9 0:52‘
# @Author : ‘pc.kang‘
a = [3, 5, 8, 10, 6]
def insert_sort(lst):
idx = len(lst)
for i in range(1, idx):
if lst[idx-i] 逆向思维
idx=4
i=4,a[4]和a[3]交换，得到3,5,8,6,10
i=3,a[3]和a[2]交换，得到3,5,6,8,10
i=2,a[2]>a[1],break
‘‘‘# @Time : ‘2020-12-9 0:52‘
# @Author : ‘pc.kang‘
def insert_sort(lst):
idx = len(lst)-1
for i in range(idx, -1, -1):
print("----第%s次----"%(idx-i+1))
if lst[i] 算法复杂度
在最坏的情况下，即每次循环都要比较到第一个元素，则：
第一次循环，比较了1次；
第二次循环，比较了2次；
...
第n-1次循环，比较了n-1次；
总的比较次数是1+2+3+...+(n-1) = n(n-1)/2。
我们上面所求得的n(n-1)/2，其时间复杂度，最大的影响因子是n^2/2，故其时间复杂度是O(n^2)。