1

我确实知道 4.5 的排序算法是从 4.​​0 改变的，但我怀疑内省排序的实现有问题。似乎在反向排序列表的情况下表现不规律，当有人期望与“排序”情况（如 4.0 中）相同数量的比较时，这个数字非常大。

.net 4 x64

随机25514058，排序20525265，反转20525285

.net 4.5 x64

随机22112103，排序16935357，反转31148728！！

我用来获取比较次数的代码（使用 4.0 和 4.5 编译）是：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace sortTest {
class Program {
    class CmpCount : IComparer<int> {
        private int _count;
        /// <summary>
        /// 
        /// </summary>
        public int Count {
            get {
                return _count;
            }
        }



        public int Compare( int x, int y ) {
            _count++;
            return x.CompareTo( y );
        }
    }
    static void Main( string[] args ) {
        Random rnd = new Random(1234);
        List<int> list = new List<int>();
        for ( int i = 0; i < 1000000; i++ ) {
            list.Add( rnd.Next() );
        }
        CmpCount cmp = new CmpCount();
        list.Sort( cmp );
        int random = cmp.Count;

        cmp = new CmpCount();
        list.Sort( cmp );
        int sorted = cmp.Count;

        cmp = new CmpCount();
        list.Reverse();
        list.Sort( cmp );
        int reversed = cmp.Count;

        Console.WriteLine("random {0}, sorted {1}, reversed {2}",random,sorted,reversed);
    }
}
}

编辑：我正在调试源代码，似乎从未调用过 HeapSort。也许它需要一个特制的输入来触发它。所以实际上在上述情况下，4.5 排序实际上只是进行快速排序。

快速查看源代码，似乎 4.0 的快速排序更复杂，而 4.5 的实现很差（直接来自书籍？）。

如果我理解正确，4.5 似乎也盲目地偏爱已经排序的列表。这可能是反向排序列表的问题

4

1 回答 1

2

introsort 的 .NET 4.5 实现首先尝试进行快速排序。当它看到递归深度超出特定点时，它会停止快速排序并重新开始堆排序。

因此，期待更多的比较并不是不合理的，因为该算法正在执行部分排序，然后重新启动以执行完整排序。

此外，没有人知道 .NET 快速排序是如何挑选项目来进行分区的。可能它使用的中位数为 3。但它是随机选择三个吗？第一、中、最后？对于同一数组的两种类型，分区可能不同（因此比较次数可能不同）。

无论如何，Introsort 并不声称自己是完美的。即使使用快速排序会更快，该算法很有可能会检测到潜在的最坏情况并切换到堆排序。Introsort 避免了最坏情况的行为，但有时会表现出非最佳行为。

此外，不能保证您排序的数组是相同的。您确定Random.NET 4 和 .NET 4.5 之间的类实现没有变化吗？在 4.5 上创建的序列可能与Random(1234)在 4.0 上创建的序列不同。如果是这样，您就不是在比较同一个数组上的排序。

于 2013-06-12T17:09:41.040 回答