python - 插入排序 Python

Question

我已经在Python中实现了插入排序，并且想知道如何确定算法的复杂性。这是实现插入排序的低效方法吗？对我来说，这似乎是最具可读性的算法。

import random as rand
source = [3,1,0,10,20,2,1]
target = []
while len(source)!=0:
 if len(target) ==0:
  target.append(source[0])
  source.pop(0)
 element = source.pop(0)
 if(element <= target[0]):
  target.reverse()
  target.append(element)
  target.reverse()
 elif element > target[len(target)-1]:
  target.append(element) 
 else:
  for i in range(0,len(target)-1):
   if element >= target[i] and element <= target[i+1]:
    target.insert(i+1,element)
    break
print target 

Answer 1

而不是:

target.reverse()
target.append(element)
target.reverse()

尝试:

target.insert(0, element)

此外，也许可以使用 for 循环，而不是 while 循环，以避免 source.pop()？:

for value in source:
  ...

在最后的 else block 中，if 测试的第一部分是多余的:

else:
   for i in range(0,len(target)-1):
     if element >= target[i] and element <= target[i+1]:
        target.insert(i+1,element)
        break

由于列表已经排序，只要您找到比要插入的元素大的元素，您就找到了插入位置。