理解使用“大于等于”（> =）时包含的内容

Question

我需要为我的课程编写一个快速排序功能。随后给出的一种可能的解决方案是：

def quicksort(s):
    if len(s) <= 1:
        return s
    else:
        return quicksort([x for x in s[1:] if x < s[0]]) \
        +[s[0]] \
        + quicksort([y for y in s[1:] if y >= s[0]])


list = [5, 6, 8, 2, 7, 1] #any numbers you want
print(quicksort(list))

为什么需要+[s[0]]？ y >= s[0]中是否已经包含它？

Answer 1

您的列表中可能有多个相同的元素，并且在对它们进行排序的过程中不应丢失它们。

[请注意，两种理解（在排序方面收集了枢轴的“之前”和“之后”元素）都在s[1:]上操作，即s[0]之后的每个元素。因此，无论您使用什么其他谓词，它们都将永远不会包含s[0]本身。

>=在那里，因为如果仅在一侧包含> s[0]而在另一侧仅包含< s[0]，则在进行排序的过程中会丢失== s[0]的其他任何元素。

例如：

# don't give variables the same name as built-in types/functions!
numbers = [5, 5, 5, 6, 8, 2, 7, 1]
print(quicksort(numbers))

[1, 2, 5, 5, 5, 6, 7, 8]

如果改用y > s[0]怎么办？

def quicksort(s):
    if len(s) <= 1:
        return s
    else:
        return (
            quicksort([x for x in s[1:] if x < s[0]])
            + [s[0]]
            + quicksort([y for y in s[1:] if y > s[0]])
        )


# don't give variables the same name as built-in types/functions!
numbers = [5, 5, 5, 6, 8, 2, 7, 1]  # any numbers you want
print(quicksort(numbers))

[1, 2, 5, 6, 7, 8]

哇！

使用>=不一定是解决此问题的唯一方法。我们可以明确地使列表的中间部分是等于枢轴的所有元素（包括枢轴），例如：

def quicksort(s):
    if len(s) <= 1:
        return s
    p = s[0]  # could be any arbitrary element!
    return (
        quicksort([x for x in s if x < p])
        + [x for x in s if x == p]
        + quicksort([x for x in s if x > p])
    )

这可能会稍慢一些，因为您现在正在列表中进行额外的迭代（也许是因为您将第二个quicksort传递给较短的列表这一事实弥补了这一点？），但也许可以使概念稍微清楚一点，所有“小于”元素都在“等于”元素之前，而“相等”元素在“大于”元素之前。

这种方法还使选择不同的枢轴点变得更加容易；例如，如果您碰巧从一个已经排序（或大部分排序）的列表开始，那么在中间而不是在开头选择一个轴可以更快一些，因为您的递归调用树更广泛，更不深入。