以降序排序数组的最快方法

Question

为什么是以下代码

Array.Sort(values);
Array.Reverse(values);

与以下相比,按降序排序数组的速度要快得多

Array.Sort(values, (a,b)=>(-a.CompareTo(b)));

代码在调试器外部的发布模式下运行.

为阵列生成降序排序的最有效方法是什么,最好是在一个班轮中？

Answer 1

这是一个很好的问题.我打赌你的values数组是一个原始类型的数组!

它实际上是这里的主导,因为Reverse的复杂性是O(n),而排序是O(n logn).

问题在于,在对基本类型进行排序时,.NET实际上会调用本机函数,这非常快 - 比使用比较或比较器快得多.

该函数被称为TrySZSort:

[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[SecurityCritical]
[MethodImpl(MethodImplOptions.InternalCall)]
private static bool TrySZSort(Array keys, Array items, int left, int right);

以下是在Array类中调用它的方式:

[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[SecuritySafeCritical]
public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer)
{
  if (array == null)
    throw new ArgumentNullException("array");
  else if (index < 0 || length < 0)
    throw new ArgumentOutOfRangeException(length < 0 ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  else if (array.Length - index < length)
    throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  else if (length > 1 && (comparer != null && comparer != Comparer<T>.Default || !Array.TrySZSort((Array) array, (Array) null, index, index + length - 1)))
    ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
}