递归QuickSort遭受StackOverflowException - c#

我正在研究GenericList类中的递归QuickSort方法实现。我将有第二种方法,该方法接受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;
    }

}

c#参考方案

您的实现包括将枢轴包含在子列表中。通过将透视表包含在子列表中(在本例中为左列表,因为您的条件为<=),如果该透视表最终位于子列表的中间,则可以进行无限次递归。

例:

列表= [3,6,12,4,8]轴心= 3(12)左= [3,6,12,4,8]右= [空]
列表= [3,6,12,4,8]轴心= 3(12)左= [3,6,12,4,8]右= [空]
列表= [3,6,12,4,8]轴心= 3(12)左= [3,6,12,4,8]右= [空]
... 无限循环

因为不排除枢轴(尽管其最终位置是已知的),所以它可能导致您一遍又一遍地对同一列表进行排序,而不是减小列表的大小以对每个递归调用进行排序。

如果从子列表中排除数据透视表(按索引而不是按值),然后将其重新添加到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(带有伪代码)

Java中的“ <<”运算符 - java

最喜欢的语句来自Java的Character类:(1 << Character.PARAGRAPH_SEPARATOR)) >> type PARAGRAPH_SEPARATOR是字节,type是整数。这句话中的操作员,他们做什么?如何以及在哪里可以使用这些运算符?这是oracles java.lang.Character文档。该类中…

LeetCode题解拼凑硬币

小Q十分富有,拥有非常多的硬币,小Q拥有的硬币是有规律的,对于所有的非负整数K,小Q恰好各有两个面值为2^k的硬币,所有小Q拥有的硬币就是1,1,2,2,4,4,8,8.....小Q有一天去商店购买东西需要支付n元钱,小Q想知道有多少种方案从他拥有的硬币中选取一些拼凑起来恰好是n元(如果两种方案某个面值的硬币选取的个数不一样就考虑为不一样的方案)输入:输入包…

LeetCode题解爱丽丝和鲍勃

爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。最初,黑板上有一个数字 N 。在每个玩家的回合,玩家需要执行以下操作:选出任一 x,满足 0 < x < N 且 N % x == 0 。用 N - x 替换黑板上的数字 N 。如果玩家无法执行这些操作,就会输掉游戏。只有在爱丽丝在游戏中取得胜利时才返回 True,否则返回 false。假设两…

将对象转换为List <object> - c#

我看过类似的问题,但没有什么合适的。我有一个碰巧包含列表的对象。我想把它变成我可以列举的东西。例如:object listObject; // contains a List<Something> List<object> list; list = listObject as List<object>; // list c…

LeetCode题解求一根绳子被切两刀能组成一个三角形的概率。

如题题解:我们可以设绳长为1,设:- 其中两段长为x, y且x, y都>0- 故第三段长为1-x-y且>0故可以在二维坐标轴画出一个三角形(由x=0;y=0;1-x-y=0围成)要想构成三角形还要满足:- x+y > 1-x-y => x+y > 0.5- x+1-x-y > y => y < 0.5- y+1…