昨天给某个同学做了一个Excel数据处理的小工具，最后需要把处理后的结果进行排序。大家都知道List类提供了一个Sort方法能够对列表中的元素进行排序，这个东东是怎么使用的呢？它又是怎么实现的呢？为了满足自己的“好奇心”，现在来进行“探秘”吧。
首先Array类的Sort方法有非常多的重载版本，其中每一种都有泛型和非泛型的方法：
看参数类型就知道每一个重载的使用场合。基本上，对于整个数组的排序，它提供了三种方式：默认比较器、IComparer接口的比较器和Comparison<T>的泛型委托。
List<T>是泛型类，它的Sort方法重载要简洁得多，我们还是从List<T>开始吧：
public void Sort();
public void Sort(Comparison<T> comparison);
public void Sort(IComparer<T> comparer);
public void Sort(int index, int count, IComparer<T> comparer);首先第一种方式，就是无参数的Sort方法，按照微软的说明，就是“使用默认比较器对整个 System.Collections.Generic.List<T> 中的元素进行排序”。这里的“默认比较器”，就是T类型实现的IComparable（或起泛型接口IComparable<T>）接口时所提供的比较器。对于简单的值类型，M$都实现了IComparable<T>接口，所以直接调用list.Sort()方法即可实现升序排列，非常简便。但是假如你的排序方式和默认的不同（例如是逆序或有其他特殊需求），又或者你使用的不是简单的值类型，那么.NET无论如何都不知道如何进行排序了，这时必须自己实现IComparable或泛型接口或者使用其他重载，否则会在运行时抛出System.InvalidOperationException类型的异常。这么说来在编译的时候，.NET是无法检测Sort方法是否有效的，因为在定义List<T>时它并未指定T是否需要实现IComparable<T>接口。
我现在定义了下面这样的一个OutputFormat结构体：
internal struct OutputFormat
{
public string UserIdentity;
public string OutputIdentity;
public string Content;
public decimal TotalMoney;
}然后呢，我希望它按照下面的规则进行排序：如果OutputIdentity是空字符串，那么就把它放在结果的最下面，其他的无所谓。
为了说明这个Sort方法比较“神奇”的地方，我分别尝试了如下几个实现方式：
1. 实现IComparable接口
这个接口并不是一个泛型接口，所以参数是一个object类型，首先呢，我按照下面这样来实现这个接口：
public int CompareTo(object obj)
{
OutputFormat that = (OutputFormat)obj;
if (that.OutputIdentity.Length == 0)
return 1;
return -1;
}恩，只要OutputIdentity为空，就认为它在被比较的元素后面，否则呢就认为它在被比较元素的前面。非常偷懒吧？嘿嘿，下面我们来运行一下：
杯具了，这么偷懒是不行的。错误提示里已经说得很清楚了，一个元素与自身比较时如果没有返回0，那么.NET认为比较器有问题，会抛出一个异常。
我偏偏就不信了，于是改成下面这样，不管怎么样都认为当前元素在另一元素的后面，这样也应该出错吧：
public int CompareTo(object obj)
{
return 1;
}可是神奇的是并没有出错！最后得到的结果是乱序的，根本不知道是按什么顺序排的！那么疑问就来了：.NET在排序前不会检查x.CompareTo(x)是否会返回0，那么什么时候会有这种情况呢？
2. 实现IComparable<T>接口
好吧，非泛型接口还要做类型转换，似乎比较麻烦，那么我们实现一下IComparable<T>这个泛型的接口吧，我还是像上面那样使用“错误”的方法进行排序：
public int CompareTo(OutputFormat other)
{
if (other.OutputIdentity.Length == 0)
return 1;
return -1;
}运行一下，嘿嘿，错误快抛出来！但是又杯具了，没有抛出任何异常，反而是程序无响应，说明Sort方法陷入了死循环！后来，我按照非泛型接口的方式直接return 1，这时错误又出现了！这个问题实在是很诡异，说明在调用这两个接口时，.NET的实现方式是不同的。它到底是如何实现的呢？我们还是来看一下.NET的源代码吧。
恩，跟踪源代码，发现List类调用的是Array.Sort<T>(_items, index, count, comparer)，并且comparer传入了null值，那么还是看下Array类的代码吧。省略掉一些参数的判断和Contracts的检查，这个方法的代码如下：
if (length > 1) {
if (comparer == Comparer.Default || comparer == null) {
bool r = TrySZSort(keys, items, index, index + length - 1);
if (r)
return;
}
Object[] objKeys = keys as Object[];
Object[] objItems = null;
if (objKeys != null)
objItems = items as Object[];
if (objKeys != null && (items==null || objItems != null)) {
SorterObjectArray sorter = new SorterObjectArray(objKeys, objItems, comparer);
sorter.IntrospectiveSort(index, length);
}
else {
SorterGenericArray sorter = new SorterGenericArray(keys, items, comparer);
sorter.IntrospectiveSort(index, length);
}
}总体来说分成了两种逻辑：提供了比较器和没提供比较器的。我们目前关心的当然是没提供比较器的情况，那么会使用TrySZSort这个方法。SZ的意思是“单维零下标”数组，看样子.NET似乎只能对这样的数组进行排序，如果不是单维或者不是0下标（这个是可以的），似乎是必须提供比较器的。
然后看TrySZSort方法，果然是native的代码，果断google取得之。绕了一大圈，最后调用了这个方法：
FCIMPL4(FC_BOOL_RET, ArrayHelper::TrySZSort, ArrayBase * keys, ArrayBase * items, UINT32 left, UINT32 right)
WRAPPER_CONTRACT;
STATIC_CONTRACT_SO_TOLERANT;
VALIDATEOBJECTREF(keys);
VALIDATEOBJECTREF(items);
_ASSERTE(keys != NULL);
if (keys->GetRank() != 1 || keys->GetLowerBoundsPtr()[0] != 0)
FC_RETURN_BOOL(FALSE);
_ASSERTE(left <= right);
_ASSERTE(right < keys->GetNumComponents() || keys->GetNumComponents() == 0);
TypeHandle keysTH = keys->GetArrayElementTypeHandle();
const CorElementType keysElType = keysTH.GetVerifierCorElementType();
if (!CorTypeInfo::IsPrimitiveType(keysElType))
FC_RETURN_BOOL(FALSE);
if (items != NULL) {
TypeHandle itemsTH = items->GetArrayElementTypeHandle();
if (keysTH != itemsTH)
FC_RETURN_BOOL(FALSE); // Can't currently handle sorting different types of arrays.
}
if (left == right || right == 0xffffffff)
FC_RETURN_BOOL(TRUE);
switch(keysElType) {
case ELEMENT_TYPE_I1:
ArrayHelpers<I1>::QuickSort((I1*) keys->GetDataPtr(), (I1*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
case ELEMENT_TYPE_U1:
case ELEMENT_TYPE_BOOLEAN:
ArrayHelpers<U1>::QuickSort((U1*) keys->GetDataPtr(), (U1*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
case ELEMENT_TYPE_I2:
ArrayHelpers<I2>::QuickSort((I2*) keys->GetDataPtr(), (I2*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
//省略一大段基元类型的判断方法
default:
_ASSERTE(!"Unrecognized primitive type in ArrayHelper::TrySZSort");
FC_RETURN_BOOL(FALSE);
}
FC_RETURN_BOOL(TRUE);
FCIMPLEND哦，那么它首先使用keysTH.GetVerifierCorElementType取得数组元素类型的内部表示，这是一个CorElementType类型的枚举（参见这里），如果发现不是基元类型，直接return false了。我们的显然不是基元类型，所以又转回Array的Sort方法了。顺便一提，可以看到M$对基元类型都是使用的QuickSort这个方法。这个玩意我们以后再看吧。
回到Array.Sort方法，排序使用了两种内部类：SortObjectArray和SortGenericArray。参考注释，这两种类唯一的不同就是获取元素的方式，对于可以直接转换成object[]类型的数组，都会使用SortObjectArray这个类，其他情况使用另一个（有什么数组不能转换到object[]呢？这点我还不明白）。那么我们来看SortObjectArray好了。
（更新： 这个方法传入的items和keys参数的类型都是Array。Array并没有提供索引器的泛型方法，而是提供了GetValue和SetValue来对其中的元素进行访问，而这两个方法的对象类型都是Object。Array类的索引器是实现自IList接口，而其也是调用的GetValue和SetValue方法。
对于任何一个用户使用标准语法定义的数组，比如string[] s，系统会实现IList<T>接口，这是在SZArrayHelper这个类中实现的。这样才能使用s[index]的方式进行随机访问，且返回值类型不是Object。而这些数组都可以被显式转换成Object[]类型。在List<T>和其他集合的内部，大多都使用T[]的形式存储元素，所以他们调用Sort方法时都会使用SortObjectArray。
从通常的角度来说，并不是每一个从Array类派生的数组都实现了IList<T>，因此不能假定都可以以T[index]的方式对元素进行访问。故此处对这两种情况进行了区分。
如果不进行这样的区分而都使用IList非泛型接口，那么得到的值都是Object的类型，那么进行排序的效率会降低很多。由此可见，当无法转换成Object[]类型的时候，会不可避免地使用SortGenericArray，效率会比SortObjectArray低很多。
用户不能自己从Array类派生，所以大多数情况应该都实现了IList<T>。我目前还不知道有没实现这个接口且从Array类派生的情况。如果发现了以后再更新。）
（更新2：List<T>调用的Array类的Sort方法应该是泛型重载 Sort<T>(T[] array, int index, int length, IComparer<T> comparer) 这个版本。因为List<T>传入的_items是一个实现了IList<T>的数组，在编译器应该会选择这个版本的重载，而不会像上面那样去判断需要使用SortGenericArray还是SortObjectArray。）
Sort调用的IntrospectiveSort称之为“内省式排序”，貌似没见过这种排序方法，不过没关系，我们来看一下：
IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));第三个参数是depthLimit，其值是Log2(Length)*2，顺带一提，这个FloorLog2的实现是这样的（ 至于为什么没有使用Math类，原因不明）：
internal static int FloorLog2(int n)
{
int result = 0;
while (n >= 1)
{
result++;
n = n / 2;
}
return result;
}接下来就是重点了，请擦亮眼睛：
private void IntroSort(int lo, int hi, int depthLimit)
{
while (hi > lo)
{
int partitionSize = hi - lo + 1;
if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
{
if (partitionSize == 1)
{
return;
}
if (partitionSize == 2)
{
SwapIfGreaterWithItems(lo, hi);
return;
}
if (partitionSize == 3)
{
SwapIfGreaterWithItems(lo, hi-1);
SwapIfGreaterWithItems(lo, hi);
SwapIfGreaterWithItems(hi-1, hi);
return;
}
InsertionSort(lo, hi);
return;
}
if (depthLimit == 0)
{
Heapsort(lo, hi);
return;
}
depthLimit--;
int p = PickPivotAndPartition(lo, hi);
IntroSort(p + 1, hi, depthLimit);
hi = p - 1;
}
}可以看出这个算法的核心还是快速排序，但是做了一点改进。
IntrosortSizeThreshold的取值是16，那么意味着：当前要排序的片段不超过16个时，使用插入排序；当元素个数超过16个时且depth为0时，改用堆排序完成这个片段。这样做的原因是：不当的枢轴选择，导致不当的分割，导致快速排序恶化为O(N^2)。其实这个算法也不复杂：当递归层次超过2Log(n)时，就认为快排有恶化的倾向，转向使用堆排序。当片段不超过16个元素，使用插入排序；此时每个序列有相当程序的排序，但尚未完全排序，这时使用插入排序，效率是非常高的。
OK，排序算法看完了，但是貌似跑题了，前面说的使用IComparable和IComparable<T>行为不一致的问题似乎还是没有得到解答。
导致越界的原因，是因为快速排序过程中有下面这个循环：
while (left < right)
{
while (comparer.Compare(keys[++left], pivot) < 0) ;
while (comparer.Compare(pivot, keys[--right]) < 0) ;
if (left >= right)
break;
Swap(keys, left, right);
}如果我们的比较器对于相同的元素不能返回0，那么就会越出keys这个数组的边界（因为没有下标保护）。当这里出错时，Array类自然会返回一个IndexOutOfRange的错误，这个时候.NET就认为是比较器有问题，从而抛出最开始的那个错误。
那么为什么两种实现方式会有两种结果呢？在两者都出错的情况下，通过查看异常的堆栈，发现使用了两种不同的类：GenericArraySortHelper<T>和ArraySortHelper<T>，通过名字就可以知道，前者是实现了泛型的IComparable<T>接口时使用的，后者则是没有实现泛型接口时使用的。当不提供泛型接口时，.NET会使用Comparer类（注意这个类也有一个泛型类IComparer<T>），而这个类提供了一个Compare的方法：
public int Compare(Object a, Object b) {
if (a == b) return 0;
if (a == null) return -1;
if (b == null) return 1;
if (m_compareInfo != null) {
String sa = a as String;
String sb = b as String;
if (sa != null && sb != null)
return m_compareInfo.Compare(sa, sb);
}
IComparable ia = a as IComparable;
if (ia != null)
return ia.CompareTo(b);
IComparable ib = b as IComparable;
if (ib != null)
return -ib.CompareTo(a);
throw new ArgumentException(Environment.GetResourceString("Argument_ImplementIComparable"));
}那么这里就可以看出与泛型接口的不同行为：
- 当使用泛型接口时，.NET直接调用CompareTo方法，也就是我们自己实现的接口方法；
- 当使用非泛型接口时，.NET首先进行引用判断，相同引用直接返回0。否则才使用我们实现的CompareTo方法。
但即使是这样，似乎也说明不了问题，从调试输出来看，并没有相同引用进行比较的过程。那么原因应该出自ArraySortHelper<T>这个类上。通过两个类的比较，总算发现了下面这个地方的行为稍有不同：
ArraySortHelper<T>类的比较过程为：left vs 基准，基准 vs right，而GenericArraySortHelper<T>则都是以基准元素为“起始”元素对left和right进行比较。
由于之前实现的CompareTo方法有问题，而两种实现方式取基准元素的行为不一致，所以导致排序过程中元素的排序顺序也不一致，最终才发生一个出错一个死循环。
绕了半天终于解答了自己心中的疑虑。看来有时候实现错误的方法并不是坏事，如果我没有好玩实现一个错误的比较器，也不会查看这方面的源代码去了解排序的机制。
从上面这个“探秘”过程可以发现，实现一个正确的CompareTo方法是非常重要的，这也可能会是很多问题潜伏的地方：看似相同的实现方式，结果可能不一致；看似排序没有问题的调试，可能在运行时由于数据的不同而出错或排序错误。所以，我们的CompareTo方法要尽可能地动脑筋写，上面这种偷懒的方式显然是不恰当的。
回到开始的部分，List类提供了多种Sort方法重载，这主要是为了应对多种排序方式。比如实现IComparable<T>和IComparable接口只能实现一种排序方式，对于基本类型也只能实现升序排列。如果需要多种排序方式，最方便地就是使用Comparison<T>这个重载，这个重载接收一个委托，我们只需要写一个Lambda表达式即可实现排序：
_outputList.Sort((x, y) =>
{
if (x.OutputIdentity.Length == 0 && y.OutputIdentity.Length > 0) return 1;
if (x.OutputIdentity.Length > 0 && y.OutputIdentity.Length == 0) return -1;
if (x.OutputIdentity.Length == 0 && y.OutputIdentity.Length == 0) return x.UserIdentity.CompareTo(y.UserIdentity);
return x.OutputIdentity.CompareTo(y.OutputIdentity);
});这个比较器应该是一个比较完美的比较器，它不仅可以实现最开始需要的功能（OutputIdentity为空的行在最后面），而且将不为空的行按照起字母顺序排列，为空的行之间还可以进行第二关键字的排序。
最后关于基本类型的Sort过程，这个东东在ArrayHelpers模板类里（clrsrcvmcomarrayhelpers.h），实现就是一个快速排序算法。我看的这个头文件和cpp文件的版本是2.0的，不知道在4.5版本里M$有没有像不是基本类型那样使用了自省式排序，不过看MSDN上貌似是使用了的，说明微软在2.0版本之后还是做了改进的。
至于排序效率，基本类型显然是最快的，因为它不需要调用任何接口方法也不会生成任何比较器（在不提供比较器的情况下），直接使用比较运算符，其次人家是native的方法，貌似不会进行边界检查。
如果需要逆序排序，是先用默认的排再使用Reverse方法反过来，还是提供一个比较器呢？个人认为应该是提供一个比较器，因为Reverse方法的代码是这样的：
static void Reverse(KIND array[], UINT32 index, UINT32 count) {
LEAF_CONTRACT;
_ASSERTE(array != NULL);
if (count == 0) {
return;
}
UINT32 i = index;
UINT32 j = index + count - 1;
while(i < j) {
KIND temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}显然是O(n)的复杂度。但是你说比较器有额外的开销，说不定会比这个要慢？恩，这点我还没试过，不过乃自己可以试试。 ^_^