如何防止我的快速排序算法抛出 StackOverflowException

Question

我正在尝试用 C# 编写一个 quicksort 算法，但最近一段时间我一直得到 System.WhosebugExceptions，但不知道为什么。

这是我的 Class:

    class quicksort : sortalgorithm
{
    int pivotIndex = -1;
    int pivotSwapped = 0;
    Random rand = new Random();

    public quicksort(int[] arr)
    {
        if (arr.Length < 5)
        {
            throw new Exception("Array has too few Entries");
        }
        toSort = arr;
    }

    protected override int sort()
    {
        if (pivotIndex == -1) getPivot();
        int indexL = getIndexLeft();
        int indexR = getIndexRight();
        if (indexR != -1 && indexL != -1 && indexL != toSort.Length-1)
        {
            swap(indexL, indexR);
        }
        if (indexL > indexR)
        {
            Console.WriteLine("Index thingy");
            swap(toSort.Length - 1, indexL);
            pivotSwapped++;
            if (pivotSwapped == toSort.Length - 1)
            {
                return 1;
            }
            else
            {
                Console.WriteLine("new piv");
                pivotSwapped++;
                getPivot();
                sort();
                return -1;
            }
        }
        else
        {
            sort();
            return -1;
        }
    }

    private void swap(int i, int j)
    {
        int temp = toSort[i];
        toSort[i] = toSort[j];
        toSort[j] = temp;
    }

    private void getPivot()
    {
        pivotIndex = rand.Next(0, toSort.Length - 1);
        swap(toSort.Length - 1, pivotIndex);
    }

    private int getIndexLeft() // Larger then Pivot Starting: Left
    { //Error Here
        int itemFromLeft = -1;
        for (int i = 0; i < toSort.Length - 1; i++)
        {
            if (toSort[i] >= toSort[toSort.Length - 1])
            {
                itemFromLeft = i;
                i = toSort.Length + 1;
            }
        }
        //Console.WriteLine(itemFromLeft);
        return itemFromLeft;
    }

    private int getIndexRight()// Smaller then Pivot Starting: Right
    {
        int itemFromRight = -1;
        for (int i = toSort.Length - 1; i >= 0; i--)
        {
            if (toSort[i] < toSort[toSort.Length - 1])
            {
                itemFromRight = i;
                i = -1;
            }
        }
        //Console.WriteLine(itemFromRight);
        return itemFromRight;
    }
}

希望有人能帮助我。

P.S。 class sortalgorithm 在这种情况下只有数组 toSort.

我的控制台输出总是看起来像这样：

[4, 28, 62, 33, 11] // The unsorted array
Index thingy
new piv
Index thingy
new piv
Index thingy
new piv

Process is terminated due to `WhosebugException`.

Answer 1

当递归出错时，通常会发生堆栈溢出错误，即函数不断调用自身，直到堆栈中没有剩余空间来保存所有引用，

唯一明显的候选人是

            **sort();**
            return -1;
        }
    }
    else
    {
        **sort();**
        return -1;
    }

所以一个或另一个递归调用可能不正确，需要删除，我想这个问题会得到解决

编辑：

因为您无法调试您的代码这就是快速排序的样子

public int sort()
{
    qsort(0, toSort.Length - 1);
    return 0;
}

private void qsort( int left, int right)
{
    if (left < right)
    {
        int pivot = Partition( left, right);

        if (pivot > 1)
        {
            qsort( left, pivot - 1);
        }
        if (pivot + 1 < right)
        {
             qsort( pivot + 1, right);
        }
    }
}
private int Partition( int left, int right)
{
    int pivot = toSort[left];
    while (true)
    {

        while (toSort[left] < pivot)
        {
            left++;
        }

        while (toSort[right] > pivot)
        {
            right--;
        }

        if (left < right)
        {
            if (toSort[left] == toSort[right]) return right;

            int temp = toSort[left];
            toSort[left] = toSort[right];
            toSort[right] = temp;


        }
        else
        {
            return right;
        }
    }
}

注意如果left >= right什么都不做

Answer 2

这个 Hoare 分区方案的简单实现演示了如何通过在较小的分区上递归并为较大的分区循环返回来避免堆栈溢出，这是原始快速排序中使用的想法。堆栈 space 复杂度限制为 O(log2(n))，但最坏情况下的时间复杂度仍为 O(n^2)。

        static public void Quicksort(int [] a, int lo, int hi)
        {
            while(lo < hi){                 // while partition size > 1
                int p = a[(lo + hi) / 2];
                int i = lo, j = hi;
                i--;                        // Hoare partition
                j++;
                while (true)
                {
                    while (a[++i] < p) ;
                    while (a[--j] > p) ;
                    if (i >= j)
                        break;
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
                i = j++;                    // i = last left, j = first right
                if((i - lo) <= (hi - j)){   // if size(left) <= size(right)
                    Quicksort(a, lo, i);    //   recurse on smaller partition
                    lo = j;                 //   and loop on larger partition
                } else { 
                    Quicksort(a, j, hi);    //   recurse on smaller partition
                    hi = i;                 //   and loop on larger partition
                }
            }
        }

如何防止我的快速排序算法抛出 StackOverflowException

How can I prevent my Quicksort Algorithm from throwing a StackOverflowException

c#

algorithm

quicksort