algorithm - Hoare 与 Lomuto 的分区

Question

您能举例说明 2 个分区方案给出不同的结果吗？对于 Lomuto，我们必须这样写:

quicksort(A,l,p)
quicksort(A,p+1,h)

与霍尔在一起时:

quicksort(A,l,p+1)
quicksort(A,p+1,h)

(在 [low,high) 中执行的操作)

有什么区别？

Answer 1

基本的 Lomuto 分区方案将主元交换到一边，进行分区，将主元交换到位，然后将索引返回到主元的排序位置。在这种情况下，枢轴可以从递归调用中排除:

基本的 Hoare 分区方案从两端向分区内的某个点扫描，将所有小于主元的元素放在所有大于主元的元素的左侧，但是任何等于主元的元素，包括主元本身，可以在分区中的任何位置结束，并且返回的索引是左(元素 <= 主元)和右(元素 >= 主元)之间的分割点，因此调用代码不能排除从 Hoare 分区函数返回的索引处的元素来自递归调用。如果将 Hoare 方案修改为类似于 Lomuto，将主元交换到任一端，进行分区，然后将主元交换到拆分索引，那么调用代码可以排除主元，但这最终会变慢。