python - 仅 2 个元素的快速排序

Question

在“Grokking Algorithms”中，作者给出了快速排序实现的基本情况的代码:

def quicksort(array):
  if len(array) < 2:
    # base case, arrays with 0 or 1 element are already "sorted"
    return array

然后写道“让我们看看更大的数组。具有两个元素的数组也很容易排序 - 检查第一个元素是否小于第二个元素，如果不是，则交换它们。”

稍后，在浏览一个示例时，他写道“嗯​​，快速排序基本情况已经知道如何对两个元素的数组进行排序。”

我不明白这是怎么回事。是不是少了一步？当然，该代码可以工作，但我看不到显式处理 2 元素列表的算法的一部分，那么 2 元素列表如何排序？ IE。 “检查第一个元素是否小于第二个元素，如果不是，则交换它们”的逻辑在哪里？

完整的算法如下:

def quicksort(array):
  if len(array) < 2:
    # base case, arrays with 0 or 1 element are already "sorted"
    return array
  else:
    # recursive case
    pivot = array[0]
    # sub-array of all the elements less than the pivot
    less = [i for i in array[1:] if i <= pivot]
    # sub-array of all the elements greater than the pivot
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])

Answer 1

您应该看一下#递归案例:

# recursive case
pivot = array[0]
# sub-array of all the elements less than the pivot
less = [i for i in array[1:] if i <= pivot]
# sub-array of all the elements greater than the pivot
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)

如果有 2 个元素，less 或 greater 将是一个空列表，另一个(非空)将连接到第一个元素(枢轴)在左侧或右侧，具体取决于较大或较小。

顺便说一句。快速排序算法对于非常短的数组来说效果不佳，普遍的看法是使用更简单的方法，例如如果元素数量少于(例如，五个)，甚至可以使用冒泡排序。