堆栈溢出与快速排序实现

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 的第一个增量，所以当我尝试将 = 运算符添加到 while 以便它不会在第一次增量后停止时： while(A[i]<=) 我得到了一个堆栈溢出异常（也当我在第二个 do while: while(A[j]>=pivot)) 中添加等于运算符时出现堆栈溢出异常，我不明白为什么会这样，有人可以解释一下吗？

Answer 1

这是霍尔分区方案。 do while 循环需要使用 < 或 >，而不是 <= 或 >=，因为它们依赖于找到枢轴或等于枢轴的元素来停止循环并防止循环超出范围 [lo,你好]。通常使用中间元素作为支点，比如

    int pivot = A[(left+right)/2];   // or A[left + (right-left)/2]

在当前代码中，唯一不能用于主元的元素是 A[right]，因为这会导致堆栈溢出（快速排序调用最终会卡在 high = low + 1）。

因此使用 pivot = A[left]，第一个 do while 以 i == left 停止，第二个 do while 以 j <= right 停止。如果 i < j，则发生交换，将枢轴交换到 A[j] 并将元素 <= 枢轴交换到 A[i == left]。每次交换都会阻止下一对 do whiles 运行越过边界 [low, high]，因此在这对 do whiles 之后只需要检查 i >= j 以检查分区步骤是否完成。

为数据透视表选择中间元素有助于某些数据模式，例如已排序的数据或反向排序的数据。尽管如此，如果左侧元素 == pivot.

，第一个 do while 将在第一个循环中停止

请注意，Hoare 分区方案仅将分区拆分为元素 <= 主元和元素 >= 主元。主元或等于主元的任何元素可以在分区步骤后的任何位置结束。这不是问题，因为最终枢轴或等于枢轴的元素最终将位于正确的位置（这可能不会发生，直到达到低 == 高的递归级别）。

堆栈溢出与快速排序实现

stack overflow with quicksort implementation

c#

stack-overflow

algorithm

quicksort