高效的列表排序

Question

我目前正在测试按键值排序列表的最佳算法。

我有一个非常简单的对象(以下代码片段来自c#)

class BasicObject
{
int Key;
}

Key是在构造Object时随机设置的。

所以我有一个BasicObject对象的列表，需要按键值排序。

List<BasicObject> basicList = new List<BasicObject>();
for (int i = 0; i < someAmount; i++)
{
basicList.Add(new BasicObject());
}

我的想法是，创建一个名为orderedList左右的新列表，并每次循环它，对于每个BasicObject，并检查其Key是否高于当前值或更低。像这样:

List<BasicObject> orderedList = new List<BasicObject>();
bool objectWasInserted = false;
orderedList.Add(basicList[0]); // Inserting 1 Object as reference for the upcoming loop
for (int i = 1; i < someAmount; i++)
{
objectWasInserted = false;
for (int c = 0; c < orderedList.Count; c++)
{
if (basicList[i].Key > orderedList[c].Key) // The Key of the current object is higher than the key of the current object of the ordered List
{
orderedList.Insert(c, basicList[i]);
objectWasInserted = true;
break;
}
}
if (!objectWasInserted)
{
orderedList.Add(basicList[i]);
}
}

尽管这是有效的，但它太慢了。在测试50000个对象时，它已经花费了8秒。

LINQ Method OrderBy要快得多。

orderedList = basicList.OrderByDescending(x => x.Key).ToList();

对于50000个对象只需要7毫秒!

然而，这是一个辅助方法，我想摆脱它，而是使用我自己的算法按键对对象列表排序。

我还尝试了LinkedList而不是普通的List。这比LINQ方法快了一点，但距离LINQ方法还是很远。

那么有没有一种方法，可以稍微加快对象的排序速度呢?:)

谢谢你的帮助，提前!!

Answer 1

如果你不想使用Linq(对我来说看起来很奇怪)，你可以使用List<T>.Sort:

basicList.Sort((o1,o2) => o1.Key.CompareTo(o2.Key));

Answer 2

即使你想使用自己的算法，它也不会像LINQ OrderByDescending()方法中实现的算法那样高效和快速。我们不知道LINQ中使用的是哪种排序算法，但我们知道它已经被优化，实现得很高效，并且使用了框架的力量，否则它不会花费7毫秒来排序50000个对象。

看看这一页，考虑不同的排序算法。

如果你要改变编程语言，你将不得不使用该编程语言的特性。对我来说，如果你必须改变编程语言，那么在已经有排序算法的情况下开始实现排序算法是没有意义的，因为排序算法是针对你目前使用的语言(比如c#)进行优化的。如果你已经知道你将使用哪种语言，那么考虑一下该语言可以提供的工具来解决你的问题。