我已经在C#中实现了快速排序的一个版本，并进行了一些快速基准测试，以与C# List<T>.Sort 进行比较。我发现我的实现比库版本慢得多。我正在尝试理解为什么会这样。以下是一些粗略的基准测试数字。对于输入，我使用了随机生成的整数列表（均匀分布）和少量重复元素。请注意，所有基准测试时间都是若干次运行的平均值。
100,000 elements
My code 0.096 seconds
List<T>.Sort 0.011 seconds
1,000,000 elements
My code 1.10 seconds
List<T>.Sort 0.14 seconds
我的代码如下。这是我尝试过的优化措施及其结果列表:
- 内联 - 我试图内联我的
Swap和ChoosePivotIndex函数，使用时有约 10% 的提升。 - 枢轴选择 - 我知道我使用了一个天真的枢轴选择方法。我尝试过选用三个随机元素的中位数来作为枢轴，但没有多大改进。我猜测这是因为我用于基准测试的输入数据是均匀随机的。
- 并行处理 - 我尝试使递归的 Partition 调用并行处理。这似乎实际上增加了执行时间。
- 特殊情况小输入 - 我尝试切换到插入排序来处理小输入（就像
List<T>.Sort所声称的那样）。这可以使性能提高约 20%。
通过这些优化措施的组合，我已经将代码压缩到了...
100,000 elements - 0.062 seconds
1,000,000 elements - 0.740 seconds
这仍然比库排序慢得多。我的代码中是否有任何明显的问题可以解释性能差距，还是剩下的70-80％差距来自更小的调整？请注意，下面的代码是我的基本未优化版本
public class Quicksorter<T> where T : IComparable<T>
{
protected Random random;
public Quicksorter()
{
random = new Random();
}
public void Sort(IList<T> items)
{
Partition(items, 0, items.Count-1);
}
private void Partition(IList<T> items, int startIndex, int endIndex)
{
if (startIndex >= endIndex)
return;
int pivotIndex = ChoosePivotIndex(items, startIndex, endIndex);
T pivot = items[pivotIndex];
// swap pivot and first element
Swap(items, startIndex, pivotIndex);
int partitionIndex = startIndex + 1;
for (int frontierIndex = partitionIndex; frontierIndex <= endIndex; frontierIndex++)
{
if (items[frontierIndex].CompareTo(pivot) < 0)
{
Swap(items, frontierIndex, partitionIndex);
partitionIndex++;
}
}
// put pivot back
items[startIndex] = items[partitionIndex-1];
items[partitionIndex - 1] = pivot;
// recursively sort left half
Partition(items, startIndex, partitionIndex - 2);
// recursively sort right half
Partition(items, partitionIndex, endIndex);
}
protected virtual int ChoosePivotIndex(IList<T> items, int startIndex, int endIndex)
{
return random.Next(startIndex, endIndex);
}
private void Swap(IList<T> items, int aIndex, int bIndex)
{
T temp = items[aIndex];
items[aIndex] = items[bIndex];
items[bIndex] = temp;
}
}
List<T>是使用数组实现的。当您调用List.Sort时，它会转而调用Array.Sort。在排序时间方面，数组和列表之间没有区别（除了一个额外的函数调用）。将Partition修改为接受一个数组最终会要求 Quicksort 方法从传递的IList创建一个数组——以 O(n) 的额外空间代价——并且在排序完成后还需要将其复制回IList。这可能非常昂贵。 - Jim Mischel