Самый быстрый способ сортировки массива в порядке убывания

Ответ 1

Это отличный вопрос. Уверен, что ваш массив значений - это массив примитивного типа!

Это действительно тот вид, который здесь доминирует, потому что сложность Reverse - O (n), а sort - O (n logn).

Дело в том, что при сортировке примитивных типов .NET на самом деле вызывает нативную функцию, которая чрезвычайно быстра - намного быстрее, чем при использовании Comparison или Comparator.

Функция называется 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);
}

Ответ 2

Как указывает ссылка

Метод сортировки здесь всегда заканчивается во внутреннем TrySZSort или QuickSort когда он не генерирует исключение. Внутренняя система TrySZSort метод оптимизирован для одномерных массивов, также известный как "Zero", массивы или векторы

Поскольку метод TrySZSort, используемый в библиотеках базового класса, реализованный в собственном коде, он был сильно оптимизирован. Следовательно, этот метод, скорее всего, быстрее, чем любое решение, написанное на С# Язык

Ответ 3

Делегаты.

Вызов делегата намного медленнее, чем вызов по умолчанию IComparable.CompareTo

Update:

Если вам нужна такая же (или близкая) скорость, реализуйте интерфейс IComparer и передайте это методу сортировки.

http://msdn.microsoft.com/en-us/library/bzw8611x

Ответ 4

Поскольку в вашей второй версии он должен вызывать вашу (анонимную) функцию каждый раз, когда она выполняет сравнение, а затем вызывает .CompareTo внутри этого, поэтому у вас есть две ссылки, тогда как в противном случае они могут использовать встроенные сравнения (для примитивных типов).

В основном вы платите за накладные расходы функций, которые, как я полагаю, устраняются для собственных примитивных типов при выполнении этих видов операций. Хотя технически возможно (я думаю), я сомневаюсь, что Джиттер способен полностью встроить их во второй случай.