快速排序:快速排序中的控制流程
在我看来，快速排序的一个常见实现是，程序由一个分区子例程和两个递归调用组成，用于对这些(两个)分区进行排序。
因此，控制的流程，在最快速的伪码中，是这样的：
quicksort[list, some parameters]
.
.
.
q=partition[some other parameters]
quicksort[1,q]
quicksort[q+1,length[list]]
.
.
.
EndQ是分区之后的“枢轴”。第二个快速排序调用--那个会加快列表第二部分排序的调用，也使用了q。这是我不明白的。如果“控制流”首先通过第一个快速排序，q将被更新。当执行所有分区的第二部分时，相同的q如何在第二个快速排序中工作呢？
我想我的误解来自伪码的局限性。在用伪码表示快速排序算法的这个实现时，可能遗漏了一些细节。
编辑1这似乎与我的问题有关：
For[i = 1, i < 5, i = i + 1, Print[i]]第一次，我们会得到i=1，true，i=2，1。尽管我被更新为2，但我的身体仍然是1(即Printi=1)。这种“控制的流动”是我不明白的。，当i=1增加到2并且到达主体之前，它在哪里存储？
编辑2
作为我想要达到的一个例子，我把这个贴在这里。是从这里来的。
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)另一个例子可以在这里找到。
在这些算法中的位置或时间， q 被放入堆栈？中。
回答 3
Stack Overflow用户
发布于 2011-10-18 08:07:56
q没有更新。枢轴仍在他的位置上。在快速排序的每一次迭代中，唯一保证处于其正确位置的元素是支点。
另外，请注意，在递归调用期间“更改”的q实际上没有改变，因为它是一个不同的变量，存储在不同的区域，这是正确的，因为q是函数的局部变量，是为每个调用生成的。
编辑:对问题编辑的响应
在快速排序中，该算法实际上生成了存储在堆栈q中的s的数目。每个变量只对其自己的函数“活动”，在本例中只能从它访问。当函数结束时，局部变量将被自动释放，因此实际上您不只有一个枢轴，，实际上您有多少个枢轴，每个递归步骤都有一个。
Stack Overflow用户
发布于 2011-10-19 02:59:04
事实证明，快速排序需要额外的内存才能准确地工作，这样才能进行前面提到的引导。该算法的以下迭代版本(伪代码)可能会澄清问题：
quicksort(array, begin, end) =
intervals_to_sort = {(begin, end)}; //a set
while there are intervals to sort:
(begin, end) = remove an interval from intervals_to_sort
if length of (begin, end) >= 2:
q = partition(array, begin, end)
add (begin, q) to intervals_to_sort
add (q+1, end) to intervals_to_sort您可能会注意到，现在排序的间隔被显式地保存在一个数据结构中(通常只是一个数组，在结尾插入和删除，就像堆栈一样)，所以没有“忘记”旧间隔的风险。
可能让您感到困惑的是，快速排序最常见的描述是递归的，因此q变量会多次出现。这个问题的答案是，每次调用一个函数时，它都会创建一批新的局部变量，这样就不会碰旧的了。最后，前一个命令式示例中的显式堆栈最终被实现为一个带有函数变量的隐式堆栈。
(一个有趣的附带说明:一些早期的编程语言没有实现这样的整洁的局部变量，而且快速排序实际上是首先使用带有显式堆栈的迭代版本来描述的。只是后者，人们才知道在Algol中，快速排序是如何被优雅地描述为递归算法的。)
至于编辑后的部分，i=1会被遗忘，因为赋值会破坏性地更新变量。
Stack Overflow用户
发布于 2012-09-23 22:29:58
分区代码从数组中选择一些值(例如数组中点的值).示例代码选择最后一个元素) --这是支点。然后，它将所有值<=枢轴放在左边，所有值>=枢轴放在右边，然后将支点存储在它们之间的一个剩余槽中。在这一点上，支点必须在正确的槽，q，然后算法排序分区[p，q)和分区[q+1，r)，这是不相交的，但涵盖了所有的A，除q，导致整个数组排序。
https://stackoverflow.com/questions/7804140
复制相似问题
腾讯云开发者
