QuickSort堆栈溢出
我的通用QuickSort算法有两个问题，我无法确定原因。
在处理大于20,000项的列表时，我经常会遇到堆栈溢出，如果值重复了很多次(我认为这不是一个真正的问题)，则经常会出现堆栈溢出(我认为这不是真正的问题)
没有正确排序的列表是相当罕见的，因此列表必须相当大。下面的粘贴显示了安装软件的172元素列表的前13个元素，其中第一列显示第一排序之后的输出，第二列显示第二排序。
Adobe AIR 7-Zip 4.65 (x64 edition)
7-Zip 4.65 (x64 edition) Adobe AIR
Adobe Community Help Adobe Community Help
Adobe Encore CS4 Codecs Adobe Encore CS4 Codecs
Adobe Media Encoder CS4 Exporter Adobe Media Encoder CS4 Exporter
Adobe Media Encoder CS4 Importer Adobe Media Encoder CS4 Importer
Adobe Media Player Adobe Media Player
Adobe Reader X (10.1.0) Adobe Reader X (10.1.0)
Adobe Setup Adobe Setup
Adobe Setup Adobe Setup
Apple Application Support Adobe Setup
Adobe Setup Apple Application Support
Apple Mobile Device Support Apple Mobile Device Support
... ...如您所见，第一次排序时，有一些不正确的行为，这是通过执行另一种方法来解决的。
堆栈溢出的第二个问题发生在我对我的大型Windows事件日志列表进行排序时。如果我对跨越4周的52,000个日期进行排序，这似乎是一件令人高兴的事情；但是，如果我对52,000个重复的ID号进行排序，那么在系统崩溃之前，我的堆栈大小就变成了998项。如果我按照一列主要是“gupdate”的列对30,000长的列表进行排序，也会发生这种情况。
现在，据我所见，堆栈计数应该是log2(n)，因为添加到堆栈中的数量等于所完成的一半的裁剪量。
我做了我的枢轴随机，以帮助这一效果，但它没有产生很大的区别。
Log2(60000) = 16。这还不够堆栈溢出！
这是有关的守则：
private static void QuickSortFunction<T>(T[] array, int start, int end, Comparer<T> comparer)
{
if (end - start >= 1)
{
int leftPtr, rightPtr, pivot;
Random random = new Random();
pivot = random.Next(start, end);
Swap(array, pivot, start);
pivot = start;
leftPtr = start + 1;
rightPtr = end;
while (leftPtr < rightPtr)
{
while ((comparer.Compare(array[leftPtr], array[pivot])) <= 0 && (leftPtr < rightPtr))
{
leftPtr++;
}
while ((comparer.Compare(array[rightPtr], array[pivot])) >= 0 && (leftPtr <= rightPtr))
{
rightPtr--;
}
if (leftPtr < rightPtr)
{
Swap(array, leftPtr, rightPtr);
}
}
Swap(array, pivot, rightPtr);
pivot = rightPtr;
QuickSortFunction(array, start, pivot - 1, comparer);
QuickSortFunction(array, pivot + 1, end, comparer);
}
}
private static void Swap<T>(T[] array, int pointer1, int pointer2)
{
T temp = array[pointer1];
array[pointer1] = array[pointer2];
array[pointer2] = temp;
}对任何感兴趣的人来说，这是解决无序故障的方法。基本上，当2元素数组出现故障时，它无法识别出来。例如{E，B}，它不会改变，因为它不看自己的枢轴。
if (end - start >= 1)
{
int leftPtr, rightPtr, pivot;
Random random = new Random();
pivot = random.Next(start, end);
Swap(array, pivot, start);
pivot = start;
leftPtr = start;
rightPtr = end;
while (leftPtr < rightPtr)
{
while ((comparer.Compare(array[leftPtr], array[pivot])) < 0 && (leftPtr < rightPtr))
{
leftPtr++;
}
while ((comparer.Compare(array[rightPtr], array[pivot])) >= 0 && (leftPtr < rightPtr))
{
rightPtr--;
}
if (leftPtr < rightPtr)
{
Swap(array, leftPtr, rightPtr);
}
}
Swap(array, pivot, rightPtr);
pivot = rightPtr;
QuickSortFunction(array, start, pivot - 1, comparer);
QuickSortFunction(array, pivot + 1, end, comparer);
}一旦我为堆栈溢出编写了解决方案，将进行更新。
回答 2
Stack Overflow用户
发布于 2012-04-28 11:32:33
让我们先来看看无序的问题。大循环一直持续到leftPtr >= rightPtr。由于您的第二个循环测试了leftPtr <= rightPtr，可能在leftPtr > rightPtr结束时，您将(在大循环之后)交换支点和一个被认为是"OK“的元素(rightPtr指向经过leftPtr传递的东西)。
不确定堆栈溢出问题，但Hammar的建议似乎是合理的，特别是您说这个问题发生在包含许多相同元素的大列表中。
Stack Overflow用户
发布于 2013-02-21 19:33:11
看看你创造的无限循环..。功能必须终止，其内在价值才能在使用中实现。
https://stackoverflow.com/questions/10362939
复制相似问题
腾讯云开发者
