重复主元的霍尔划分算法

Question

以下是根据 Wikipedia 的 Hoare 分区算法。

来自维基百科的伪代码：

algorithm partition(A, lo, hi) is 
  // Pivot value
  pivot := A[ floor((hi + lo) / 2) ] // The value in the middle of the array

  // Left index
  i := lo - 1 

  // Right index
  j := hi + 1

  loop forever 
    // Move the left index to the right at least once and while the element at
    // the left index is less than the pivot
    do i := i + 1 while A[i] < pivot
    
    // Move the right index to the left at least once and while the element at
    // the right index is greater than the pivot
    do j := j - 1 while A[j] > pivot

    // If the indices crossed, return
    if i ≥ j then return j
    
    // Swap the elements at the left and right indices
    swap A[i] with A[j]

一个java实现：

public class Main
{
    public static void main(String[] args) {
        int[] arr = new int[] { 2, 1, 2, 4, 3 };
        Hoare.partition(arr, 0, 4);

        for (int x : arr) System.out.println(x);
    }
}

class Hoare
{
    private static void Swap(int[] array, int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
 

    public static int partition(int []arr, int low, int high)
    {
        int pivot = arr[(low + high) / 2]; // pivot is 2 for this case.
        // Expected out is:
        // 1 2 2 3 4
        // or
        // 1 2 2 4 3
        //
        // Actual output is:
        // 2 1 2 4 3
        // Since 3 and 4 are greater than 2, then the partitioning isn't working.

        int i = low - 1;
        int j = high + 1;
     
        while(true)
        {
            do {
                i++;
            }
            while (arr[i] < pivot);
            
            do {
                j--;
            }
            while (arr[j] > pivot);
            
            if (i >= j)
            {
                return j;
            }
            
            Swap(arr, i, j);
        }
    }
}

为什么输出错误（在代码注释中指出）？这是 Hoare 算法的已知限制吗？是我的实现还是维基百科的伪代码不正确？

Answer 1

霍尔算法保证主元前的所有元素都小于或等于主元值，主元后的所有元素都大于或等于主元值。

这也意味着枢轴值位于最终排序数组中的正确索引处。这对快速排序算法很重要。

霍尔分区不保证所有等于枢轴值的元素都是连续的。这不是快速排序算法的要求，因此没有必要花费任何额外的计算能力来保证它。

也就是说，实现是正确的；结果是预期的；它将在快速排序中毫无问题地工作。

重复主元的霍尔划分算法

Hoare partitioning algorithm for duplicate pivot value

java

algorithm

quicksort

partitioning