快速排序 Python 递归 - 递归函数是如何工作的

Question

所以我了解分区的工作原理，但是我不了解快速排序功能的工作原理。这是我在网上找到的代码，但是大多数版本都非常相似。快速排序函数如何拼凑整个排序列表？当分区生成列表的子集时，我不明白 return 语句 return 如何成为一个完整的排序列表。那么这里的 return 值不应该是一个或两个数字吗？

我正在寻找的是_quicksort()函数如何逐步运行的解释。非常感谢任何人的帮助！

def partition(xs, start, end):
    follower = leader = start
    while leader < end:
        if xs[leader] <= xs[end]:
            xs[follower], xs[leader] = xs[leader], xs[follower]
            follower += 1
        leader += 1
    xs[follower], xs[end] = xs[end], xs[follower]
    return follower

def _quicksort(xs, start, end):
    if start >= end:
        return
    p = partition(xs, start, end)
    _quicksort(xs, start, p-1)
    _quicksort(xs, p+1, end)

def quicksort(xs):
    _quicksort(xs, 0, len(xs)-1)

Answer 1

这是 Lomuto 分区方案的一个示例，其中 partition() 将输入分成值 <= pivot, pivot, values > pivot。这样做的结果是值 <= pivot 将被交换，因此它们小于 (follower-start) 远离它们的最终排序位置，值 > pivot 将被交换，因此它们小于 (end-follower) 远离它们最终排序的位置，并且 pivot (xs[end]) 将被放置在它的排序位置。然后它递归地为左右组调用自己。组的每个递归级别都会将该组中的元素置于更接近其最终排序位置的位置，并且一旦达到基本情况（0 或 1 个元素），该元素就处于其最终排序位置。

你可以认为这是随着递归的每一级数据变得更接近排序，并且一旦遍历了整个递归堆栈树，数组就结束了排序。

虽然快速排序通常被称为分而治之的方法，但通过交换更接近其最终排序位置的元素所做的工作是在除法之前完成的，一旦除法达到 1 个元素的基本情况，该元素现在处于这是最终排序的位置，在 returns 备份调用链期间什么也没做。

看看

https://en.wikipedia.org/wiki/Quicksort#Algorithm

https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme

快速排序 Python 递归 - 递归函数是如何工作的

Quick Sort Python Recursion - how does the recursive function work

python

recursion

quicksort