比較器調用的意外次數

Question

不知道爲什麼在查看比較器的調用次數時我會得到這樣的奇數。

對於2個字符串：5個電話？ 再加上有在那裏序列這樣 12琴絃：66個呼叫 13根琴絃：85個呼叫 14個Strigns：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是樞轉。你大概可以弄清楚爲什麼你會從那裏看到結果。