c# - List.Sort 是否在排序列表上遇到最坏情况下的性能？

Question

根据 the docs List<T>.Sort使用 QuickSort 算法。我听说如果没有明智地选择基准，在预排序列表上调用时，这可能会表现出最坏的情况。

QuickSort 的 .NET 实现是否会在预排序列表中遇到最坏情况下的行为？

在我的例子中，我正在编写一个方法来对列表进行一些处理。该列表需要排序才能使该方法起作用。在大多数使用情况下，列表将被传递已经排序，但对顺序进行一些小的更改并非不可能。我想知道在每次方法调用时重新排序列表是否是个好主意。很明显，我陷入了 premature optimization陷阱。

Answer 1

编辑:我已经编辑了问题。

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

Does List<T>.Sort suffer worst case performance on sorted lists?

答案似乎是“否”。

我做了一些测试，似乎排序列表比随机列表需要更少的比较来排序: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而是为了避免这个问题。