algorithm - 快速排序 quickie : the flow of control in quicksort

Question

在我看来，这是一个常见的快速排序实现，该程序由一个分区子例程和两个对这些(两个)分区进行快速排序的递归调用组成。

所以控制流，在最快和最伪的伪代码中，是这样的:

quicksort[list, some parameters]
.
.
.
q=partition[some other parameters]
quicksort[1,q]
quicksort[q+1,length[list]]
.
.
.
End

q 是分区后的“枢轴”。第二个快速排序调用——将对列表的第二部分进行快速排序的调用，也使用 q。这是我不明白的。如果“控制流”首先通过第一个快速排序，则 q 将被更新。当需要执行所有这些分区的第二部分时，相同的 q 如何在第二个快速排序中工作？

我认为我的误解来自于伪代码的局限性。以伪代码表示此快速排序算法的实现时，可能遗漏了一些细节。

编辑 1 这似乎与我的问题有关:

For[i = 1, i < 5, i = i + 1, Print[i]]

第一次通过时，我们会得到 i=1, true, i=2, 1。即使 i 更新为 2，i 在 body 中仍然是 1(即 Print[i]=1)。这种“控制流”是我不明白的。 当 i=1 递增到 2 并到达 body 之前，i=1 存储在哪里？

编辑2

作为我想要达到的目标的示例，我将其粘贴在这里。 It's from here.

Partition(A,p,r)
x=A[r]
i=p+1
j=r+1
while TRUE
    repeat j=j-1
       until A[j]<=x
    repeat i=i+1
       until A[i]>=x
    if i<j
       then exchange A[i] with A[j]
       else return j

Quicksort(A,1,length[A])

Quicksort(A,p,r)
if p<r
    then q=Partition(A,p,r)
        Quicksort(A,p,q)
        Quicksort(A,q+1,r)

Another example can be found here.

在这些算法中何时何地 q 被放入堆栈？

Answer 1

q 未更新。枢轴仍然在他的位置上。在快速排序的每次迭代中，唯一保证位于其正确位置的元素是主元。

另外，请注意在递归调用期间“更改”的 q 实际上并没有更改，因为它是一个不同的变量，存储在不同的区域，这是真的，因为 q 是 local variable函数，并为每次调用生成。

编辑:[回复问题编辑]
在快速排序中，算法实际上生成了q的数量，它们存储在堆栈中。每个变量仅在其自身的函数上“有效”，并且[在本例中]只能从它访问。当函数结束时，局部变量会自动释放，所以实际上您并没有只有一个枢轴，您实际上有多个枢轴，每个递归步骤一个。