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

3
这是一个快速排序中用于划分的算法。
让a=x[lb] (lb代表下限)成为我们要寻找最终位置的元素。初始化两个指针up和down,分别指向数组的上限和下限。在执行过程中,每个元素在up位置以上都大于a。
接下来,这两个指针将以以下方式一步步靠近:
步骤 1:重复将指针down向后移动一位,直到 x[down] > = a
步骤 2:重复将指针up向前移动一位,直到 x[up] < a
步骤 3:如果up > down,则交换x[down]和x[up]。重复此过程,直到步骤3的条件不再成立(即 up =< down)。此时,x[up]与x[lb](即a)进行交换,a的最终位置被找到,j(即最终位置)设置为up。 使用此算法,我需要对数组进行划分。
25,57,48,37,12,92,86,33  

数组中选择了枢轴作为第一个元素。因此a=25。

初始时down=0,up=7。
由于满足条件x[down] >= a,down指针无需移动。
在将up减小4次后
down指向0,up指向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。

然后down=0,up=6。

交换x[down]和x[up],我得到33,48,37,25,92,86,57
重复向下移动指针4次和重复向上移动指针3次,我得到33,48,37,25,92,86,57

然后down=4,up=3。
交换x[up]和x[lb]
我有25,48,37,33,92,86,57,j=up=3。

但显然这不是围绕57正确地进行了分区

我看不出自己犯了什么错误。因此,如果有人能帮助我找出这个错误,那将非常有帮助。


重复将指针向下移动一个位置,直到x[down]> a。之后,您想指向57,这比枢轴大,并且应该与数组右侧较小的元素进行交换。 - 500 - Internal Server Error
我这里当然是指左手的食指。 - 500 - Internal Server Error
@500-服务器内部错误:那么错误在算法中,对吗? - clarkson
是的,基本上就是这样:只要左手索引所指向的值小于等于枢轴值,就增加左手索引。然后,只要右手索引所指向的值大于等于枢轴值,就减少右手索引。如果索引还没有相遇,就交换两个值,增加/减少索引,并重复此过程。 - 500 - Internal Server Error
@500-InternalServerError 是否等于包括小于或等于和大于或等于?如果x [down]> a且x [up] <= a,则此算法有效。 - clarkson
文献中有一些变化,但通常与枢轴相等的值可以放在任一侧。 - 500 - Internal Server Error
1个回答

2

在交换x [down]和x [up]之后,您还需要更新down和up。 步骤3应修改为: 第三步:如果up > down,则交换x [down]和x [up] 并down ++和up--。重复此过程,直到步骤3中的条件失败(即up =< down),此时x [up]与x [lb](等于a)进行交换,其最终位置被寻求,j(即最终位置)设置为up。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接