我写了下面的插入排序算法
def insertionSort(L, reverse=False):
for j in xrange(1,len(L)):
valToInsert = L[j]
i=j-1
while i>=0 and L[i] > valToInsert:
L[i+1] = L[i]
i-=1
L[i+1] = valToInsert
return L
编辑:只需将final>;更改为<;即可使其反向工作。在
然而,大多数人在这种情况下会做什么?另一个写两次算法呢?在这种情况下,哪种方法是“正确的”来处理这些变化很小但只会完全改变循环/代码的性质的?在
我知道这个问题有点主观。在
您可能会注意到^{} 和^{} 以及所有其他执行任何类型潜在修饰处理的函数都有一个
key
参数,而那些专门进行排序的函数也有一个reverse
参数。(Sorting Mini-HOWTO涵盖了这一点。)所以,你可以看看它们是如何实现的。不幸的是,在CPython中,所有这些东西都是用C实现的。但我认为可以解释这里的关键部分,因为它非常简单。} ,您可以看到它如何处理
list.sort
代码与sorted
代码是分开的,它们都分布在大量函数上。但是如果您只查看顶层函数^{reverse
标志:为什么要颠倒开头和结尾的列表?好吧,在列表一开始几乎被排序的情况下,许多排序算法,包括timsort和您的插入排序,从正确的顺序开始比从后序开始要好得多。是的,它浪费了一个O(N)
reverse
调用,但你已经在做其中一个了,因为任何排序算法都至少是O(N logn),而你的算法是O(N^2),这并不会使算法变得更糟。当然,对于较小的N,更好的排序,以及随机顺序的列表,这个浪费的2N非常接近nlogn,所以它在实践中可以起到作用。这将是一个随着N变得巨大而消失的差别,但是如果你要对数百万个小的list
排序,而不是几个大的,那么这可能值得担心。在其次,请注意,它通过创建一个反向切片来实现反转。这一点,至少在潜在的情况下,可以通过使用
__getitem__
反向引用原始的list
对象进行优化,这意味着这两个反转实际上是O(1)。最简单的方法是创建一个反向切片:lst[::-1]
。不幸的是,这实际上创建了一个新的reversedlist
,因此timsort包含了它自己的自定义reverse slice对象。但是您可以在Python中通过创建一个ReversedList
类来做同样的事情。在实际上,在CPython中这可能不会更快,因为额外函数调用的成本可能很高,足以掩盖差异。但您抱怨的是两个
reverse
调用的算法开销,这有效地解决了问题,与内置的排序函数一样。在你也可以看看PyPy是怎么做到的。它的} 中实现的。根据列表包含的内容,它委托给几个不同的策略类中的一个,但是如果您查看所有的策略(除了那些没有什么要做的策略),它们基本上是做相同的事情:
list
是在^{sort
列表,然后reverse
它。在所以,这对CPython和PyPy来说已经足够好了……可能对你也足够好了。在
可以将变量用于小于运算符:
选项1:
选项2:
^{pr2}$相关问题 更多 >
编程相关推荐