使用递归的选择排序

Question

对于这里的每个人来说，这种递归选择排序是什么样子的？我是不是错过了任何关于我所做的事情的“奏鸣曲”？

def selection_sort(li, out=None):
    if out is None:
        out = []    
        li = li[:]

    if len(li) == 0:
        return out

    small = min(li)
    li.remove(small)
    out.append(small)
    return selection_sort(li, out)

Answer 1

def selection_sort(li, out=None):

我不喜欢“李”这个名字，我认为缩写是不好的。

    if out is None:
        out = []    
        li = li[:]

我建议创建一个独立的内部函数，而不是使用out参数。否则，函数的调用方可能会合理地传递=某样东西，而它只打算在内部使用。

    if len(li) == 0:
        return out

最好使用if not li:

    small = min(li)
    li.remove(small)
    out.append(small)
    return selection_sort(li, out)

要评估这段代码有点困难，因为您正在做两件不应该做的事情，在没有必要时使用递归，并实现自己的排序例程。但如果你这样做是为了学习的目的，那也没关系。

编辑

迭代解决方案：

def selection_sort(li):
    li = li[:]
    out = []

    while li:
        smallest = min(li)
        li.remove(smallest)
        out.append(smallest)

    return out

但是，为什么这比递归解决方案更好：

1. 堆栈空间是有限制的。如果您尝试使用这个函数对一个大列表排序，您将得到一个RuntimeError
2. 调用函数有额外的开销，循环中的迭代不会，迭代版本会更快。
3. 循环通常比递归更容易阅读。while循环可以很容易地看到所做的事情，而递归版本则需要对代码进行一些思考才能看到逻辑。