如何为插入排序添加反向功能？

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

补充一下：只需要把最后的 > 改成 < 就可以让它反向工作。

不过，大多数人在这种情况下会怎么做呢？会在两个 if 语句中写两遍算法，一个是 >，另一个是 <？那么，通常处理这种小改动但会完全改变循环或代码性质的情况，"正确"的方法是什么呢？

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

Answer 1

你可能会注意到，sorted、list.sort以及其他一些可能会进行特殊处理的函数都有一个叫做key的参数，而那些专门用于排序的函数还会有一个reverse参数。（关于这个内容，可以参考排序小指南。）

所以，你可以看看它们是怎么实现的。不幸的是，在CPython中，这些东西都是用C语言写的。而且，它使用了一种叫做“timsort”的自定义算法（详细描述见listsort.txt）。不过我觉得可以简单解释一下关键部分，因为这其实很简单。list.sort的代码和sorted的代码是分开的，而且它们的实现分布在很多函数中。但如果你只看顶层函数listsort，你就能看到它是如何处理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 log N)，而你的算法特别是O(N^2)，这并不会让算法变得更糟。当然，对于小规模的N，以及更好的排序算法和随机顺序的列表，这浪费的2N和N log N差不多，所以在实际操作中是有可能会有影响的。随着N变得很大，这种差异会消失，但如果你要排序的是数百万个小列表，而不是几个大的列表，这可能就值得关注了。

其次，注意它是通过创建一个反向切片来进行反转的。这至少在某种程度上可以通过以反向顺序引用原始list对象来优化，这样两个反转的操作实际上是O(1)。最简单的方法就是直接创建一个反向切片：lst[::-1]。不幸的是，这样做实际上会创建一个新的反向list，所以timsort包含了自己定制的反向切片对象。不过，你也可以通过创建一个ReversedList类在Python中实现类似的功能。

在CPython中，这样做可能不会更快，因为额外的函数调用成本可能会足够高，以至于掩盖了这些差异。但你是在抱怨两个reverse调用的算法成本，而这个方法在效果上解决了这个问题，和内置的排序函数做的方式基本相同。

你也可以看看PyPy是怎么做的。它的list是在listobject.py中实现的。它根据列表的内容委托给几个不同的策略类，但如果你查看所有策略（除了那些无事可做的），它们基本上都做同样的事情：先sort列表，然后reverse它。

所以，对于CPython来说，这样做是足够的，对于PyPy来说……这可能也足够适合你。

Answer 2

选项 1:

def insertionSort(L, reverse=False):
    # loop is the same...
    if reverse:
        L.reverse()
    return L

选项 2:

def insertionSort(L, reverse=False):
    if reverse:
        cmpfunc = lambda a, b: cmp(b, a)
    else:
        cmpfunc = cmp
    for j in xrange(1,len(L)):
        valToInsert = L[j]
        i=j-1
        while i>=0 and cmpfunc(L[i], valToInsert) > 0:
            L[i+1] = L[i]
            i-=1
        L[i+1] = valToInsert
    return L

Answer 3

你可以用一个变量来表示小于操作符：

import operator
def insertionSort(L, reverse=False):       
    lt = operator.gt if reverse else operator.lt        
    for j in xrange(1,len(L)):
        valToInsert = L[j]
        i = j-1
        while 0 <= i and lt(valToInsert, L[i]):
            L[i+1] = L[i]
            i -= 1
        L[i+1] = valToInsert
    return L