无法理解使用 "greater than or equal to" (>=) 时包含的内容

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

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

请注意，这两种理解（在排序方面收集元素 "before" 和 "after" 枢轴）都在 s[1:] 上运行，即 [=16= 之后的每个元素].因此，无论您应用什么其他谓词，它们都不会包含 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 较短的列表弥补了这一点？）但也许使概念更清楚一点，即所有 "less than" 元素都在 "equal" 元素之前，而 "equal" 元素在 "greater than " 元素之前。

这种方法还可以更轻松地尝试选择不同的轴心点；例如，如果您碰巧从一个已经排序（或大部分已排序）的列表开始，那么在中间而不是开头选择一个枢轴可能会快得多，因为您的递归调用树更广泛且更浅。

无法理解使用 "greater than or equal to" (>=) 时包含的内容

Trouble understanding what is included when using "greater than or equal to" (>=)

python

quicksort