1

根据文档 List<T>.Sort使用 QuickSort 算法。我听说如果没有明智地选择枢轴，当在预先排序的列表上调用时，这可能会表现出最差的性能。

QuickSort 的 .NET 实现是否在预排序列表上遇到最坏情况？

就我而言，我正在编写一个将对列表进行一些处理的方法。需要对列表进行排序才能使该方法起作用。在大多数使用情况下，列表将通过已经排序，但对顺序进行一些小的更改并非不可能。我想知道在每个方法调用上重新排序列表是否是个好主意。很明显，我陷入了过早的优化陷阱。

4

3 回答 3

5

编辑：我已经编辑了这个问题。

我猜我的问题被问得很糟糕。真的应该是：

List<T>.Sort在排序列表上会遭受最坏情况的性能吗？

答案似乎是“否”。

我做了一些测试，似乎排序列表比随机列表需要更少的比较来排序：https ://gist.github.com/3749646

const int listSize = 1000;
const int sampleSize = 10000;

var sortedList = Enumerable.Range(0,listSize).ToList();
var unsortedList = new List<int>(sortedList);

var sortedCount = 0;
sortedList.Sort((l,r) => {sortedCount++; return l - r;});
//sortedCount.Dump("Sorted");
// Returns: 10519   

var totalUnsortedComparisons = 0;
for(var i = 0; i < sampleSize; i++)
{
    var unsortedCount = 0;
    unsortedList.Shuffle();
    unsortedList.Sort((l,r) => {unsortedCount++; return l - r;});
    totalUnsortedComparisons += unsortedCount;
}

//(totalUnsortedComparisons / sampleSize).Dump("Unsorted");
// Returns: 13547

当然，@dlev 提出了一个有效的观点。我永远不应该让自己陷入不确定我的列表是否已排序的情况。

我已经改用SortedList来避免这个问题。

于 2012-09-19T13:28:05.910 回答
2

除非您有硬性指标可以进行比较，否则您将陷入过早的优化陷阱。在循环中运行您的代码超过 1000 次，并使用两种不同的方法收集执行时间，以查看哪种方法更快以及是否有所作为。

于 2012-09-17T16:40:05.437 回答
2

选择正确的算法并不是过早的优化。

当您的列表已经排序或接近排序时，使用稳定排序是有意义的。 .NET 附带一个，LINQ 的OrderBy实现。 不幸的是，它会多次复制你的整个列表，但复制仍然是 O(N)，所以对于一个非平凡的列表，它仍然会更快。

于 2012-09-17T16:43:18.783 回答