带有快速排序实现的堆栈溢出

Question

我正在尝试实现快速排序算法（在C＃中，这是我的代码：

public static void sort(ref int[] A)
{
    if (A.Length==0 || A.Length==1) 
    { 
        return; 
    }
    quickSort(ref A,0,A.Length-1);
}

private static void quickSort(ref int[] A, int left, int right)
{
    if (left >= right || left < 0 || right < 0) 
        return;

    int pivot = A[left];

    int i = left - 1;
    int j = right + 1;

    while (true) 
    {
        do 
        { 
            i++; 
        } 
        while (A[i] < pivot);

        do 
        { 
            j--; 
        } 
        while (A[j] > pivot);

        if (i >= j) 
            break;

        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    quickSort(ref A,left,j);
    quickSort(ref A, j + 1, right);
}

[此算法工作正常，但是似乎有些不合逻辑，我选择pivot等于A[left]，然后在while(true)循环中写了do{i++}while(A[i]<pivot)，现在我注意到它第一次增加i ]，因此A[i]将等于A[left]，它是枢轴值，因此这应该意味着do while循环将在i的第一个增量后停止，因此当我尝试将=运算符添加到[ C0]，这样它就不会在第一个增量之后停止：while我遇到了堆栈溢出异常（当我在第二个while(A[i]<=)：do while中添加equal运算符时，也得到了堆栈溢出异常），并且我不明白为什么会这样，有人可以解释吗？

Answer 1

这是Hoare分区方案。 do while循环需要使用，而不是<=或> =，因为它们依赖于在停止循环时查找等于或等于该枢轴的元素，并阻止循环超出范围[lo，您好]。通常，中间元素用作枢轴，例如

while(A[j]>=pivot)

使用当前代码，唯一不能用于数据透视的元素是A [right]，因为这将导致堆栈溢出（Quicksort调用最终将阻塞为high = low + 1）。