打开APP
userphoto
未登录

开通VIP,畅享免费电子书等14项超值服

开通VIP
C# Stable Sort(稳固排序)
保证相等元素的原始位置的排序被称为是稳固的。一个非稳固排序(unstable sort)不保证相等的元素在排序之后还会保持原来的顺序。
.NET使用的排序方法是不稳固的。这些排序方法,包括 System.Array.Sort 和 System.Collections.Generic.List<T>.Sort,使用的是快速排序算法,相对来说是非常快的。
然而,总有时候你会需要稳固排序,此时,一个解决方案是必须的。

示例:
用一个例子可以很好的说明稳固排序。考虑下面这个Person类,其中包含Name和Age两个属性,同时它还实现了IComparable接口(其中包含CompareTo方法)。这里的CompareTo方法根据Age来排序。
class Person : IComparable
{
    public Person( string name, int age )
    {
        this.Name = name;
        this.Age = age;
    }
    public string Name;
    public int Age;

    public int CompareTo( object obj )
    {
        int result = 1;
        if (obj != null && obj is Person)
        {
            Person person = (Person)obj;
            result = this.Age.CompareTo( person.Age );
        }
        return result;
    }

    public override string ToString()
    {
        return String.Format( "{0} - {1}"this.Name, this.Age );
    }
}
现在,让我们创建、排序和写一个Person类的集合。
Person p1 = new Person( "Abby"38 );
Person p2 = new Person( "Bob"23 );
Person p3 = new Person( "Charlie"23 );
Person p4 = new Person( "Danielle"18 );

List<Person> list = new List<Person>();
list.Add( p1 );
list.Add( p2 );
list.Add( p3 );
list.Add( p4 );
list.Sort();

Console.WriteLine( "Unstable List Sort:" );
foreach (Person p in list)
{
    Console.WriteLine( p );
}
他们的原始位置是,Bob(23)出现在Charlie(23)前面。但是,由于两个对象的age相等,并且List<T>.Sort方法是非稳固的,使得两个相等的对象的顺序的位置颠倒了。以下是输出结果:
Unstable List Sort:
Danielle - 18
Charlie - 23
Bob - 23
Abby - 38

稳固的插入排序
有很多可用的稳固排序。插入排序就是其中一个很简单而有效的稳固排序。
public static void InsertionSort<T>( IList<T> list, Comparison<T> comparison )
{
    if (list == null)
        throw new ArgumentNullException( "list" );
    if (comparison == null)
        throw new ArgumentNullException( "comparison" );

    int count = list.Count;
    for (int j = 1; j < count; j++)
    {
        T key = list[j];

        int i = j - 1;
        for (; i >= 0 && comparison( list[i], key ) > 0; i–)
        {
            list[i + 1] = list[i];
        }
        list[i + 1] = key;
    }
}
注意InsertionSort<T>方法要求有一个Comparison<T>的委托,因此,我们需要在Person类中添加一个静态的Compare方法,它的签名应该是Comparison<T>。Compare方法调用Person类的CompareTo方法:
static public int Compare( Person x, Person y )
{
    int result = 1;
    if (x != null && x is Person &&
        y != null && y is Person)
    {
        Person personX = (Person)x;
        Person personY = (Person)y;
        result = personX.CompareTo( personY );
    }
    return result;
}
同样的,这里Bob(23)也在Charlie(23)前面,并且原始位置被保留了。下面是输出结果:
Stable Insertion Sort:
Danielle - 18
Bob - 23
Charlie - 23
Abby - 38

两种排序的比较:

当然,快速排序在效率上要由于插入排序。所以,在一般情况下,使用.NET的排序方法就可以了;在确实需要稳固排序的地方再用插入排序。
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请点击举报
打开APP,阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
【热】打开小程序,算一算2024你的财运
C# Sort排序
Java 中Comparable和Comparator区别比较
C# List 排序各种用法与比较
对象的比较与排序:IComparable和IComparer接口
List<T>的各种排序方法
集合排序
更多类似文章 >>
生活服务
热点新闻
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!

联系客服