对 Comparer 的调用次数超出预期

Question

不知道为什么在查看比较器的调用次数时会得到如此奇数的数字。

对于 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}\n\t\tDiff:{2}\n\n", Iterations, CallsToSort, LastCycle-CallsToSort);
            Iterations--;
        }

Answer 1

Array.Sort() 方法（通常）最终会使用确定性选择枢轴的 QuickSort 版本。 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 是枢轴。您可能可以准确地弄清楚为什么您会从那里看到结果。