递归快速排序遇到 StackOverflowException

Question

我正在 GenericList 类中实现递归快速排序方法。我将有第二种方法，它接受一个compareDelegate来比较不同的类型，但出于开发目的，我对GenericList<int>进行排序。

我根据列表大小在不同的地方接收 stackoverflow 区域。

我已经盯着并跟踪这段代码几个小时了，可能只需要一双新的（更有经验的）眼睛。我绝对想了解它为什么坏了，而不仅仅是如何修复它。

public void QuickSort()
{
    int i, j, lowPos, highPos, pivot;
    GenericList<T> leftList = new GenericList<T>();
    GenericList<T> rightList = new GenericList<T>();
    GenericList<T> tempList = new GenericList<T>();

    lowPos = 1; highPos = this.Count;
    if (lowPos < highPos)
    {
        pivot = lowPos;
        for (i = 2; i <= highPos; i++)
        {
            if (this[i].CompareTo(this[pivot]) <= 0)
                leftList.Add(this[i]);
            else
                rightList.Add(this[i]);
        }
        leftList.Add(this[pivot]);
        leftList.QuickSort();
        rightList.QuickSort();

        for(i=1;i<=leftList.Count;i++)
            tempList.Add(leftList[i]);
        for(i=1;i<=rightList.Count;i++)
            tempList.Add(rightList[i]);

        this.items = tempList.items;
        this.count = tempList.count;
    }

}

成品：

public void QuickSort()
{
    Random random = new Random();
    int i, j, lowPos, highPos, pivot;
    GenericList<T> leftList = new GenericList<T>();
    GenericList<T> rightList = new GenericList<T>();
    GenericList<T> tempList = new GenericList<T>();

    if (this.Count > 1)
    {
        pivot = random.Next(1,this.Count);
        for (i = 1; i <= this.Count; i++)
        {
            if (i == pivot) continue;
            if (this[i].CompareTo(this[pivot]) < 0)
                leftList.Add(this[i]);
            else
                rightList.Add(this[i]);
        }
        leftList.QuickSort();
        rightList.QuickSort();

        for(i=1;i<=leftList.Count;i++)
            tempList.Add(leftList[i]);
        tempList.Add(this[pivot]);
        for(i=1;i<=rightList.Count;i++)
            tempList.Add(rightList[i]);

        this.items = tempList.items;
        this.count = tempList.count;
    }

}

Answer 1

您的实现是将枢轴包含在子列表中。通过将枢轴包含在子列表中（在本例中为左侧列表，因为条件为 <=），如果该枢轴最终位于子列表的中间，则您将自己设置为可能的无限递归。

示例：

1. 列表 = [3, 6, 12, 4, 8] 枢轴 = 3 (12) 左 = [3, 6, 12 , 4, 8] 右 = [ 空 ]
2. 列表 = [3, 6, 12, 4, 8] 枢轴 = 3 (12) 左 = [3, 6, 12, 4, 8] 右 = [ 空 ]
3. 列表 = [3, 6, 12, 4, 8] 枢轴 = 3 (12 ) Left = [3, 6, 12, 4, 8] Right = [ Empty ]
4. ... 无限循环

由于未排除枢轴（尽管其最终位置已知），因此可能会导致您永远对同一个列表进行排序，而不是减小列表的大小以在每次递归调用时进行排序。

如果您从子列表中排除数据透视表（按索引，而不是按值）并将其添加回 leftList 和 rightList 之间的最终 tempList 中，它将正常工作。

        ...
        for (i = 1; i <= highPos; i++)
        {
            if (i == pivot) continue; // Add this
            if (this[i].CompareTo(this[pivot]) <= 0)
        ...
        for (i = 1; i <= leftList.Count; i++)
            tempList.Add(leftList[i]);
        tempList.Add(this[pivot]); // Add this
        for (i = 1; i <= rightList.Count; i++)
            tempList.Add(rightList[i]);
        ...

另请参阅：有关快速排序的维基百科文章（带有伪代码）

Answer 2

我不建议将枢轴放入两组中的一组。如果只有两个相等的元素，则可能会出现无限循环。例如，如果您尝试对数组 {1,1} 进行排序，您应该会遇到无限循环，这可能是堆栈溢出的原因。大多数快速排序通过将枢轴与边缘上的元素交换，然后对数组的其余部分进行排序来避免这种情况。处理此问题的另一种方法是放入一行，以确保您不会将枢轴添加到 leftList，例如

if(i != pivot)

然后您将在添加 leftList 和添加 rightList 之间将枢轴添加到 tempList。

编辑：

尼克是正确的，因为您会遇到其他情况（例如 {5,2}）的问题。但是，即使您通过不将数据透视表放入将再次排序的列表中来解决当前问题，您也可能需要确保您的代码可以处理重复的元素。全部相同数字的大数组会给你带来 O(N^2) 时间复杂度，如果 N 足够大，那么你会遇到堆栈溢出。

Answer 3

看看当您有一个包含 [5,2] 的 List 时会发生什么。 您的 pivot 将等于 1，所以用于比较的值为5。 this[i].CompareTo(this[pivot]) <= 0 行将为 True，并且将放置数字 5在leftList中。下一次与 2 的比较也将是 True，将 2 放在 leftList 中。现在，您的 leftList 将与它开始的位置完全相同：[5,2]，您将再次调用 QuickSort...它会出现完全相同的令人作呕的结果：StackOverflow。