Python中的Heapsort

Question

请查看Python中Heapsort的以下就地实现：

def heapsort(l):
    def plunge(l, i, n):
        lchild = 2 * i + 1
        while lchild < n:
            rchild = lchild + 1
            if rchild < n and l[lchild] < l[rchild]:
                child = rchild
            else:
                child = lchild

            if l[i] > l[child]: break

            l[i], l[child] = l[child], l[i]
            i, lchild = child, 2 * child + 1

    for i in range(len(l) // 2, -1, -1):
        plunge(l, i, len(l))

    for i in range(len(l) - 1, -1, -1):
        l[0], l[i] = l[i], l[0]
        plunge(l, 0, i)

Answer 1

您的代码大多是好的，只有小的改进是可能的：

使用条件表达式代替语句

一个条件语句(如您使用的语句)可能执行两个完全不同的分支，而条件表达式只能返回一个值。这稍微简化和缩短了代码：

if rchild < n and l[lchild] < l[rchild]:
    child = rchild
else:
    child = lchild

变成：

child = rchild if rchild < n and l[lchild] < l[rchild] else lchild

要清楚地表明，您只是在决定child的值应该是什么，而不是其他任何东西。

给公共论点起了很好的名字

l只有一个字母长，很容易与1混淆，至少在小字体大小下是如此。形式参数名称是文档的第一种形式，但是应该给出。例如，我建议使用list_或xs ( FP约定)。

编写了一个额外的助手：heapify

维基百科和罗塞塔代码都使用了heapify助手，将其写入您的代码将使其更加可读性，使其类似于这些描述。

另外，附加函数将更清楚地表明，首先要创建堆，然后从堆中提取元素开始实际的排序列表构造。

Answer 2

详情：

成语

sift_down似乎是一个比plunge更常见的名字。使用常用的词汇可能是个不错的选择。

反向环

可能是个人喜好，但我发现range(len(l) - 1, -1, -1)一开始很难理解，我宁愿读reversed(range(len(l)))。

Answer 3

        rchild = lchild + 1
        if rchild < n and l[lchild] < l[rchild]:
            child = rchild
        else:
            child = lchild

这引起了我的注意，因为rchild只在这里使用过。如果我们内联它，然后看看我们是否可以不同地重构它呢？

if lchild + 1 < n and l[lchild] < l[lchild+1]:
    child = lchild + 1
else:
    child = lchild

...is笔直的衬里.所以现在重构：

child = lchild
if lchild + 1 < n and l[lchild] < l[lchild+1]:
    child += 1

或者倒转：

child = lchild + 1 # see if right child is usable
if child >= n or l[lchild] >= l[child]:
    # not usable, fall back to left child
    child = lchild

..which把我带到我的下一个评论:你缺乏评论。就像选择好的名字一样，评论可以填补空白，从总结的角度阐明为什么要做一些事情，因为代码本身解释了正在做的事情。