我的通用快速排序算法有两个我无法确定原因的问题。
- 列表有时未正确排序
- 在处理大于 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);
}
一旦我编写了堆栈溢出的解决方案，就会更新。