gpt4 book ai didi

c# - 递归快速排序遇到 StackOverflowException

转载 作者:行者123 更新时间:2023-12-02 13:25:53 26 4
gpt4 key购买 nike

我正在 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;
}

}

最佳答案

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

示例:

  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 (带有伪代码)

关于c# - 递归快速排序遇到 StackOverflowException,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2854372/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com