我们可以把这个函数称为快速排序吗

Question

我在 Internet 上发现这个函数写在 python 中，我很困惑它是否是一种快速排序，因为它写在一行中并且运行得非常好而且很快，我认为它可以运行即使在最坏的情况下也有 O (n*log n) 的复杂性，所以这是代码：

def qsort(L): 
  return (qsort([x for x in L[1:] if x < L[0]]) +\
          L[0:1] + \
          qsort([x for x in L[1:] if x >= L[0]])) if L else []

Answer 1

是的，它是快速排序，因为它完全符合此算法定义：从列表中选取任意元素，将低于此元素的值移动到列表的开头（在选定元素之前）并递归执行快速排序：

qsort([x for x in L[1:] if x < L[0]])

大于或等于列表末尾的值（在选定元素之后）并递归执行快速排序

qsort([x for x in L[1:] if x >= L[0]])

如果列表为空（递归终止）那么结果当然是空列表。