OrderBy函数排序算法类型

Question

我正在学习C#LINQ,我想知道使用的排序算法的类型

Answer 1

它使用快速排序,因为它可以在EnumerableSorter类的源代码中看到,该类在OrderedEnumerable类中使用,它将源包装IEnumerable在OrderBy方法内:

   void QuickSort(int[] map, int left, int right) {
        do {
            int i = left;
            int j = right;
            int x = map[i + ((j - i) >> 1)];
            do {
                while (i < map.Length && CompareKeys(x, map[i]) > 0) i++;
                while (j >= 0 && CompareKeys(x, map[j]) < 0) j--;
                if (i > j) break;
                if (i < j) {
                    int temp = map[i];
                    map[i] = map[j];
                    map[j] = temp;
                }
                i++;
                j--;
            } while (i <= j);
            if (j - left <= right - i) {
                if (left < j) QuickSort(map, left, j);
                left = i;
            }
            else {
                if (i < right) QuickSort(map, i, right);
                right = j;
            }
        } while (left < right);
    }
}

用于OrderedEnumerable排序的算法是:

1. 选择键
2. 使用Hoare的排序来排序索引映射.

3. 根据给定的索引映射从原始序列(变为Buffer - some IList)项中进行选择

      //  EnumerableSorter<TElement> does #1 and #2
      internal int[] Sort(TElement[] elements, int count) {
           ComputeKeys(elements, count);
           int[] map = new int[count];
           for (int i = 0; i < count; i++) map[i] = i;
           QuickSort(map, 0, count - 1);
           return map;
       }
   
    // OrderedEnumerable<TElement>.GetEnumerator() does #3
    public IEnumerator<TElement> GetEnumerator() {
           Buffer<TElement> buffer = new Buffer<TElement>(source);
           if (buffer.count > 0) {
               EnumerableSorter<TElement> sorter = GetEnumerableSorter(null);
               int[] map = sorter.Sort(buffer.items, buffer.count);
               sorter = null;
               for (int i = 0; i < buffer.count; i++) yield return buffer.items[map[i]];
           }
       }
   

PS:正如@JonSkeet指出的那样QuickSort,只是当前的实现.没有人知道它是否会在未来的某个版本中发生变化.也许可以为小型或特定集合添加一些优化,否则算法本身将被更改.