保證相等元素的原始位置的排序被稱為是穩(wěn)固的。一個非穩(wěn)固排序（unstable sort）不保證相等的元素在排序之后還會保持原來的順序。
.NET使用的排序方法是不穩(wěn)固的。這些排序方法，包括 System.Array.Sort 和 System.Collections.Generic.List<T>.Sort，使用的是快速排序算法，相對來說是非?？斓摹?br>然而，總有時候你會需要穩(wěn)固排序，此時，一個解決方案是必須的。
示例：用一個例子可以很好的說明穩(wěn)固排序?？紤]下面這個Person類，其中包含Name和Age兩個屬性，同時它還實(shí)現(xiàn)了IComparable接口（其中包含CompareTo方法）。這里的CompareTo方法根據(jù)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 );
}
}
現(xiàn)在，讓我們創(chuàng)建、排序和寫一個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）出現(xiàn)在Charlie（23）前面。但是，由于兩個對象的age相等，并且List<T>.Sort方法是非穩(wěn)固的，使得兩個相等的對象的順序的位置顛倒了。以下是輸出結(jié)果：
Unstable List Sort:
Danielle -
18Charlie -
23Bob -
23Abby -
38有很多可用的穩(wěn)固排序。插入排序就是其中一個很簡單而有效的穩(wěn)固排序。
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類中添加一個靜態(tài)的Compare方法，它的簽名應(yīng)該是Comparison<T>。Compare方法調(diào)用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）前面，并且原始位置被保留了。下面是輸出結(jié)果：
Stable Insertion Sort:
Danielle -
18Bob -
23Charlie -
23Abby -
38
兩種排序的比較：當(dāng)然，快速排序在效率上要由于插入排序。所以，在一般情況下，使用.NET的排序方法就可以了；在確實(shí)需要穩(wěn)固排序的地方再用插入排序。
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點(diǎn)擊舉報。
