algorithm - 快速排序分区算法。它是如何工作的

Question

这是一种快速排序中的分区算法。

设 a=x[lb](lb 指的是下限)是要查找其最终位置的元素。up和down两个引用分别初始化为子数组的上界和下界。在执行过程中的任何时刻，up 上方位置的每个元素都大于 a。

上下两个引用按以下方式相互移动
第一步:重复将指针向下增加一个位置，直到x[down] > = a

第二步:指针向上重复减少一个位置，直到x[up] < a

第 3 步:如果向上 > 向下，则将 x[向下] 与 x[向上] 互换。重复该过程，直到第 3 步中的条件失败(即 up =< down)，此时 x[up] 与 x[lb](等于 a)互换，寻找其最终位置和 j(即最终位置) 设置为向上。

使用这个算法我必须对数组进行分区

25,57,48,37,12,92,86,33  

pivot 被选为数组中的第一个元素。因此a=25。

最初向下=0，向上=7。
由于满足条件 x[down]>=a 向下指针不必移动。
下降4倍后
向下指向 0，向上指向 4。

然后将 x[down] 与 x[up] 交换

12,57,48,37,25,92,86,33

在向下增加一次并向上减少 4 次后，我想出了 up=0 ，down =1。
然后我必须将 x[up] 与 x[lb] 互换。
然后我有 12,57,48,37,25,92,86,33，j=up=0。

这是正确的吗？?
然后，当应用于快速排序算法时，我必须执行 Quicksort(x,1,7)。

也就是说，我必须对数组 57,48,37,25,92,86,33 进行分区

选择第一个元素作为基准 a=57。

然后向下=0，向上=6。

将 x[down] 与 x[up] 互换我得到 33,48,37,25,92,86,57。
向下指针重复增加 4 次并重复向上指针减少 3 次我有 33,48,37,25,92,86,57

然后向下=4，向上=3。
交换 x[up] 与 x[lb]
我有 25,48,37,33,92,86,57 j=up=3。

但显然这在 57 左右没有正确划分。

我看不出我在犯什么错误。因此，如果有人能帮我弄清楚这个错误，那将非常有帮助

Answer 1

将 x[down] 与 x[up] 互换后，您还必须更新 down 和 up。步骤3应修改为:第 3 步:如果 up > down 则将 x[down] 与 x[up] and down++ and up-- 互换。重复该过程，直到第 3 步中的条件失败(即 up =< down)，此时 x[up] 与 x[lb](等于 a)互换，寻找其最终位置和 j(即最终位置) 设置为向上。