c# - 递归快速排序遇到 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) 左 = [3, 6, 12>, 4, 8] 右 = [ 空 ]
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]);
        ...

另请参阅:Wikipedia article on Quicksort (带有伪代码)