我想在一个阵列移动偶数正面和奇数到阵列的背面。 这道题为此在一个线性算法做到这一点到位。
我想出了这个：
def sort(a):
for i in range(0,len(a)-1):
if a[i]%2==0:
a.insert(0,a.pop(i))
return a
问题是，有人告诉我说，从技术上讲，a.insert是一个O（n）的功能，所以在技术上，这将被视为非线性算法（包括当for i in range的部分功能）。 由于该问这个问题是一对夫妇个月大的论坛，我不能要求一个解释。
基本上，我相信他说：“在技术上”，因为自从此将其插入在所述前，它不检查阵列中的元件的另一N个，因此使它在为O（n），而不是为O（n ^ 2）运行的实际用途。 这是一个正确的评估？
另外，有人在论坛上用a.append修改上面，改变它来寻找奇数。 没有人回答，所以我在想，是不是a.append一个O（n）的功能，因为它移动到结束了吗？ 它是O（1）？
感谢您的解释和澄清！
insert一个列表的第0索引处需要移位沿着这使得它的O（N）操作所有其他元素。 但是，如果您使用的是deque这个操作是O（1）。
append是摊销O（1）的操作，因为它简单地需要增加到列表的末尾的项目，并没有换档完成。 有时列表需要成长，因此并不总是O（1）操作。
这是正确的 - 插入在Python标准列表的前面为O（n）。 Python列表被实现为阵列，并且因此插入的东西在列表的前面需要在一个点移动的全部内容。 追加，在另一方面，不要求任何移位，并且因此摊销O（1）。
但是请注意，该a.pop(i) 也为O（n）的操作 ，因为它需要在一个点被弹起项后移的一切。 因此，简单地修改代码中使用append()而不是insert()仍然不会导致线性算法。
线性时间算法不会使用pop() ，而是会做这样的事情周围交换元件从而使该列表的其余部分并没有被修改。 例如，考虑一下：
def even_to_front(a_list):
next_even = 0
for idx in xrange(len(a_list)):
if not a_list[idx] % 2:
# a_list[idx] is even, so swap it towards the front
a_list[idx], a_list[next_even] = a_list[next_even], a_list[idx]
next_even += 1
下面是它可以在不追加/插入或出队完成
def sort(L):
i, j = 0, len(L)-1
while i<j:
# point i to the next odd number from the start
while i<j and not L[i]%2: i+=1
# point j to the next even number from the end
while i<j and L[j]%2: j-=1
L[i],L[j] = L[j],L[i]
检查这个复杂的表
你每次pop的列表元素，你必须复制列表的尾部将它移到了一个指数，以填补被删除的元素留下的空洞。 这是在弹出元件和列表的尾部之间的距离是线性的。
您每次insert一个元素到列表中，你必须复制列表的尾部将它移到了一个索引创建点插入新的元素。 这是在所插入的元件和列表的尾部到其中的位置之间的距离是线性的。
如果你使用collections.deque ，可以追加和流行的前面和后面都O(1)时间。 然而，从中间移除元素仍然是线性的（我认为你必须自己编写）。
