为什么List <string> .Sort()慢？

Question

所以我注意到树视图花了很长时间才排序,首先我发现在添加每个已排序的项目后,大部分时间都花在重新绘制控件上.但无论如何,我有一种直觉感觉List<T>.Sort()花费的时间超过了合理时间,因此我使用自定义排序方法对其进行基准测试.结果很有趣,List<T>.Sort()花费了大约20倍,这是我在.NET中遇到过如此简单的任务所遇到的最大失望.

我的问题是,这可能是什么原因？我的猜测是调用比较委托的开销,进一步必须调用String.Compare()(在字符串排序的情况下).增加列表的大小似乎会增加性能差距.有任何想法吗？我正在尝试尽可能多地使用.NET类,但在这种情况下我不能.

编辑:

    static List<string> Sort(List<string> list)
    {
        if (list.Count == 0)
        {
            return new List<string>();
        }

        List<string> _list = new List<string>(list.Count);
        _list.Add(list[0]);

        int length = list.Count;

        for (int i = 1; i < length; i++)
        {
            string item = list[i];

            int j;

            for (j = _list.Count - 1; j >= 0; j--)
            {
                if (String.Compare(item, _list[j]) > 0)
                {
                    _list.Insert(j + 1, item);

                    break;
                }
            }

            if (j == -1)
            {
                _list.Insert(0, item);
            }
        }

        return _list;
    }

Answer 1

答:不是.

我在一个简单的控制台应用程序中运行以下基准测试,您的代码速度较慢

    static void Main(string[] args)
    {
        long totalListSortTime = 0;

        long totalCustomSortTime = 0;

        for (int c = 0; c < 100; c++)
        {
            List<string> list1 = new List<string>();
            List<string> list2 = new List<string>();

            for (int i = 0; i < 5000; i++)
            {
                var rando = RandomString(15);
                list1.Add(rando);
                list2.Add(rando);
            }

            Stopwatch watch1 = new Stopwatch();
            Stopwatch watch2 = new Stopwatch();

            watch2.Start();
            list2 = Sort(list2);
            watch2.Stop();
            totalCustomSortTime += watch2.ElapsedMilliseconds;

            watch1.Start();
            list1.Sort();
            watch1.Stop();
            totalListSortTime += watch1.ElapsedMilliseconds;



        }

        Console.WriteLine("totalListSortTime = " + totalListSortTime);
        Console.WriteLine("totalCustomSortTime = " + totalCustomSortTime);

        Console.ReadLine();
    }

结果:

Answer 2

我没有时间对它进行全面测试,因为我有一个停电(现在从手机上写),但看起来你的代码(来自Pastebin)几次排序已经排序的列表,所以看起来你的算法可能更快...对已排序的列表进行排序.如果标准.NET实现是快速排序,这将是很自然的,因为QS在已经排序的列表上具有最坏的情况.