Блог

Не уверен, почему я получаю такие нечетные числа, когда смотрю на количество вызовов средства сравнения.

Для 2 строк: 5 вызовов? Кроме того, там есть последовательности, подобные этой 12 строк: 66 вызовов 13 Строк: 85 вызовов 14 строк: 91 вызов 15 строк: 89 вызовов?????

Действительно ли было бы эффективнее сортировать 15 строк, чем 14?

 int Iterations = 20;
int LastCycle = 0;
int CallsToSort = 0;
while (Iterations > 0)
        {
            LastCycle = CallsToSort;
            CallsToSort = 0;
            var strings = new string[Iterations];
            for (int i = 0; i < Iterations; i  ) { strings[i] = "test"   i; }

            Array.Sort(strings, (s1, s2) => { CallsToSort  ; return s1.CompareTo(s2); });
            Console.WriteLine("Strings:{0}nCalls to Sort: {1}nttDiff:{2}nn", Iterations, CallsToSort, LastCycle-CallsToSort);
            Iterations--;
        }
  

Array.Sort() Метод (обычно) в конечном итоге использует версию QuickSort, в которой точки поворота выбираются детерминированно. Количество сравнений, используемых быстрой сортировкой, будет сильно зависеть от сводных данных, и вы видите это в своих результатах.

Некоторый код (из ILSpy):

     int num = left;
    int num2 = right;
    int num3 = num   (num2 - num >> 1);
    ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, num, num3);
    ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, num, num2);
    ArraySortHelper<T>.SwapIfGreaterWithItems(keys, comparer, num3, num2);
    T t = keys[num3];
  

Это t точка опоры. Вероятно, вы можете точно определить, почему вы видите результаты оттуда.