插入排序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块中，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

因为列表已经排序，所以只要找到一个比要插入的元素大的元素，就已经找到了插入位置。

Answer 2

我会说这是相当低效的。你怎么看出来的？您的方法创建了第二个数组，但在选择排序中不需要。您使用了很多操作--选择排序需要查找和交换，但您需要查找、追加、弹出、插入和反转。所以你知道你可能会做得更好。

Answer 3

def insertionsort( aList ):
  for i in range( 1, len( aList ) ):
    tmp = aList[i]
    k = i
    while k > 0 and tmp < aList[k - 1]:
        aList[k] = aList[k - 1]
        k -= 1
    aList[k] = tmp

这段代码取自geekviewpoint.com。显然，这是一个O(n^2)算法，因为它使用了两个循环。但是，如果输入已经排序，那么它就是O(n)，因为while-loop会因为tmp < aList[k - 1]失败而被跳过。