使用JetBrains的DotPeek工具能够方便地查看.net的部分源代码。于是看了一下.NET的内部是怎样实现排序的算法。
在System.Collections.Generic 命名空间下能够看到ArraySortHelper<T>的实现。
public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
{
try
{
if (comparer == null)
comparer = (IComparer<T>) Comparer<T>.Default;
if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer);
else
ArraySortHelper<T>.DepthLimitedQuickSort(keys, index, length + index - 1, comparer, 32);
}
catch (IndexOutOfRangeException ex)
{
IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer((object) comparer);
}
catch (Exception ex)
{
throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), ex);
}
}
发如今.NET4.5以上的版本号，開始使用一种叫做 Introspective Sort的排序方法。
internal static void IntrospectiveSort(T[] keys, int left, int length, IComparer<T> comparer)
{
if (length < 2)
return;
ArraySortHelper<T>.IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer);
} private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer<T> comparer)
{
for (; hi > lo; {
int num;
hi = num - 1;
}
)
{
int num = hi - lo + 1;
if (num <= 16)
{
if (num == 1)
break;
if (num == 2)
{
ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi);
break;
}
else if (num == 3)
{
ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi - 1);
ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi);
ArraySortHelper<T>.SwapIfGreater(keys, comparer, hi - 1, hi);
break;
}
else
{
ArraySortHelper<T>.InsertionSort(keys, lo, hi, comparer);
break;
}
}
else if (depthLimit == 0)
{
ArraySortHelper<T>.Heapsort(keys, lo, hi, comparer);
break;
}
else
{
--depthLimit;
num = ArraySortHelper<T>.PickPivotAndPartition(keys, lo, hi, comparer);
ArraySortHelper<T>.IntroSort(keys, num + 1, hi, depthLimit, comparer);
}
}
} private static int PickPivotAndPartition(T[] keys, int lo, int hi, IComparer<T> comparer)
{
int index = lo + (hi - lo) / 2;
ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, index);
ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi);
ArraySortHelper<T>.SwapIfGreater(keys, comparer, index, hi);
T obj = keys[index];
ArraySortHelper<T>.Swap(keys, index, hi - 1);
int i = lo;
int j = hi - 1;
while (i < j)
{
do
;
while (comparer.Compare(keys[++i], obj) < 0);
do
;
while (comparer.Compare(obj, keys[--j]) < 0);
if (i < j)
ArraySortHelper<T>.Swap(keys, i, j);
else
break;
}
ArraySortHelper<T>.Swap(keys, i, hi - 1);
return i;
}
而.NET4.5下面使用的是还有一种排序的方案。
在排序的数字小于16个的时候，直接使用插入排序。
private static void InsertionSort(T[] keys, int lo, int hi, IComparer<T> comparer)
{
for (int index1 = lo; index1 < hi; ++index1)
{
int index2 = index1;
T x;
for (x = keys[index1 + 1]; index2 >= lo && comparer.Compare(x, keys[index2]) < 0; --index2)
keys[index2 + 1] = keys[index2];
keys[index2 + 1] = x;
}
}
而假设大于16个的时候，且当递归深度在32次之内的话（也就是数字小于4GB的数量时），使用高速排序。
internal static void DepthLimitedQuickSort(T[] keys, int left, int right, IComparer<T> comparer, int depthLimit)
{
while (depthLimit != 0)
{
int index1 = left;
int index2 = right;
int index3 = index1 + (index2 - index1 >> 1);
ArraySortHelper<T>.SwapIfGreater(keys, comparer, index1, index3);
ArraySortHelper<T>.SwapIfGreater(keys, comparer, index1, index2);
ArraySortHelper<T>.SwapIfGreater(keys, comparer, index3, index2);
T obj1 = keys[index3];
do
{
while (comparer.Compare(keys[index1], obj1) < 0)
++index1;
while (comparer.Compare(obj1, keys[index2]) < 0)
--index2;
if (index1 <= index2)
{
if (index1 < index2)
{
T obj2 = keys[index1];
keys[index1] = keys[index2];
keys[index2] = obj2;
}
++index1;
--index2;
}
else
break;
}
while (index1 <= index2);
--depthLimit;
if (index2 - left <= right - index1)
{
if (left < index2)
ArraySortHelper<T>.DepthLimitedQuickSort(keys, left, index2, comparer, depthLimit);
left = index1;
}
else
{
if (index1 < right)
ArraySortHelper<T>.DepthLimitedQuickSort(keys, index1, right, comparer, depthLimit);
right = index2;
}
if (left >= right)
return;
}
ArraySortHelper<T>.Heapsort(keys, left, right, comparer);
}
而假设大于4GB的数量时，使用堆排序。
private static void Heapsort(T[] keys, int lo, int hi, IComparer<T> comparer)
{
int n = hi - lo + 1;
for (int i = n / 2; i >= 1; --i)
ArraySortHelper<T>.DownHeap(keys, i, n, lo, comparer);
for (int index = n; index > 1; --index)
{
ArraySortHelper<T>.Swap(keys, lo, lo + index - 1);
ArraySortHelper<T>.DownHeap(keys, 1, index - 1, lo, comparer);
}
} private static void DownHeap(T[] keys, int i, int n, int lo, IComparer<T> comparer)
{
T x = keys[lo + i - 1];
for (; i <= n / 2; {
int num;
i = num;
}
)
{
num = 2 * i;
if (num < n && comparer.Compare(keys[lo + num - 1], keys[lo + num]) < 0)
++num;
if (comparer.Compare(x, keys[lo + num - 1]) < 0)
keys[lo + i - 1] = keys[lo + num - 1];
else
break;
}
keys[lo + i - 1] = x;
}
最后，附上swap函数的实现：
private static void SwapIfGreater(T[] keys, IComparer<T> comparer, int a, int b)
{
if (a == b || comparer.Compare(keys[a], keys[b]) <= 0)
return;
T obj = keys[a];
keys[a] = keys[b];
keys[b] = obj;
} private static void Swap(T[] a, int i, int j)
{
if (i == j)
return;
T obj = a[i];
a[i] = a[j];
a[j] = obj;
}