我正在 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;
}
}
最佳答案
您的实现是将枢轴包含在子列表中。通过在子列表中包含枢轴(在本例中为左侧列表,因为条件为 <=),如果该枢轴最终位于子列表的中间,则您将自己设置为可能的无限递归。
示例:
- 列表 = [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 (带有伪代码)
关于c# - 递归快速排序遇到 StackOverflowException,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2854372/