实现IComparable接口的困惑

Question

比较经常使用IComparable接口，实现类的排序今天一时心血来潮，单步调试了一下IComparable接口的运行顺序，结果发现就2个值的Sort，它都运行了CompareTo方法5次
3个值的Sort，运行了CompareTo方法7次，4个值则16次
比一般的冒泡排序效率低多了
这是为什么呢？难道Sort排序效率就是这么低？代码：    public partial class ztest : System.Web.UI.Page
    {
        protected void Page_Load(object sender, EventArgs e)
        {
            List<test> arr = new List<test>();
            test tmp = new test();
            arr.Add(tmp);
            tmp.a = "6";            tmp = new test();
            arr.Add(tmp);
            tmp.a = "5";            tmp = new test();
            arr.Add(tmp);
            tmp.a = "4";            arr.Sort();
            Response.Write(test.cnt.ToString());
        }
    }    public class test:IComparable<test>
    {
        public static int cnt = 0;
        public string a;
        public int CompareTo(test other)
        {
            cnt++;
            return this.a.CompareTo(other.a);
        }
    }

Answer 1

你的测试结果有问题
我用 Array.Sort(Test[]) 在 .NET Framework 下做个测试，结果正常

Answer 2

我的验证结果：100个元素的排序，比较了803次。是O(n*log n)这个档次，没有什么不正常啊。using System;
using System.Collections.Generic;class Program : IComparable<Program>
{
    public static int cnt = 0;
    public int i;    public Program(int i)
    {
        this.i = i;
    }
    public int CompareTo(Program other)
    {
        cnt++;
        return i.CompareTo(other.i);
    }    static void Main(string[] args)
    {
        List<Program> list = new List<Program>();
        Random r = new Random(123456);
        for (int i = 0; i < 100; i++)
        {
            list.Add(new Program(r.Next()));
        }
        list.Sort();        Console.WriteLine(Program.cnt);         //803
    }
}

Answer 3

2个值的Sort，正常应该循环1次就够了
3个值，冒泡的话，应该3次就够了

Answer 4

下面是一个正常的排序，2个元素比较一次，3个元素比较3次，4个元素比较6次，明显比那个接口比较次数少
int count = 0;
int[] arr1 = {4, 3, 2, 1 };
for (int i = 0; i < arr1.Length; i++)
{
    for (int j = i + 1; j < arr1.Length; j++)
    {
        count++;
        if (arr1[i] > arr1[j])
        {
            int tmp1 = arr1[i];
            arr1[i] = arr1[j];
            arr1[j] = tmp1;
        }
    }
}
Response.Write(count.ToString() + "<hr>");

Answer 5

1、你观察的不错。在元素的数量少的时候，简单的排序方法比‘复杂’的方法要快。在很多‘高级’排序的实现中，当子数组的元素小于比如说10的时候，往往采用了简单的排序方法。2、当元素少得时候，实际上用什么算法都不重要。对排序算法来讲，它的好坏不在于对一二十个元素的效率，而是在于较大量数据下的效率，在于最坏情况下的效率。3、比如你在6楼的算法，它的复杂度是O(n*n)。在元素100或1000个的时候，你再统计一下比较次数，你就发现它的效率远不如.Net的Arrar.Sort了。

Answer 6

汗，确实如8楼所说，数组个数较多时，比较就少了只是测试了个位数的Sort。在网上找了下，System.Array.Sort其内部使用了大数据量时效率最高的快速排序算法。谢谢8楼及其它各位xd。