向插入排序添加反向特征的典型方法是什么？

Question

我写了下面的插入排序算法

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>；更改为<；即可使其反向工作。在

然而，大多数人在这种情况下会做什么？另一个写两次算法呢？在这种情况下，哪种方法是“正确的”来处理这些变化很小但只会完全改变循环/代码的性质的？在

我知道这个问题有点主观。在

Answer 1

您可能会注意到^{}和^{}以及所有其他执行任何类型潜在修饰处理的函数都有一个key参数，而那些专门进行排序的函数也有一个reverse参数。（Sorting Mini-HOWTO涵盖了这一点。）

所以，你可以看看它们是如何实现的。不幸的是，在CPython中，所有这些东西都是用C实现的。但我认为可以解释这里的关键部分，因为它非常简单。list.sort代码与sorted代码是分开的，它们都分布在大量函数上。但是如果您只查看顶层函数^{}，您可以看到它如何处理reverse标志：

1982     /* Reverse sort stability achieved by initially reversing the list,
1983     applying a stable forward sort, then reversing the final result. */
1984     if (reverse) {
1985         if (keys != NULL)
1986             reverse_slice(&keys[0], &keys[saved_ob_size]);
1987         reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
1988     }

为什么要颠倒开头和结尾的列表？好吧，在列表一开始几乎被排序的情况下，许多排序算法，包括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来说已经足够好了……可能对你也足够好了。在