6

我写了以下插入排序算法

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 语句中编写算法两次，一个是 >，另一个是 <？通常处理这些变化很小但它只是完全改变循环/代码的性质的场景的“正确”方法是什么？

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

4

3 回答 3

10

您可以为小于运算符使用变量：

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
于 2013-03-19T20:35:15.880 回答
1

选项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
于 2013-03-19T20:36:41.307 回答
1

您可能会注意到，sorted以及list.sort所有其他进行任何可能修饰处理的函数都有一个key参数，而那些专门进行排序的函数也有一个reverse参数。（Sorting Mini-HOWTO涵盖了这一点。）

所以，你可以看看它们是如何实现的。不幸的是，在 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的 s 进行排序，而不是几个大的，则可能值得担心。

其次，请注意它通过创建一个反向切片来进行反转。这至少可以通过以相反的顺序引用原始list对象来优化__getitem__，这意味着两个反转实际上是 O(1)。最简单的方法是从字面上创建一个反向切片：lst[::-1]. 不幸的是，这实际上创建了一个新的 reversed list，因此 timsort 包含了它自己的自定义 reverse-slice 对象。但是你可以通过创建一个ReversedList类在 Python 中做同样的事情。

这在 CPython 中可能实际上不会更快，因为额外函数调用的成本可能高到足以掩盖差异。但是您抱怨这两个调用的算法成本reverse，这解决了问题，有效地与内置排序函数相同。

您还可以查看 PyPy 是如何做到的。它list在listobject.py. 它根据列表包含的内容委托给几个不同的策略类之一，但是如果您查看所有策略（除了那些无关的策略），它们基本上做同样的事情：sort列表，然后reverse是它。

所以，它对于 CPython 来说已经足够好了，对于 PyPy 来说……它可能对你来说已经足够好了。

于 2013-03-19T21:14:18.577 回答