.NET 的 Array.Sort() 方法使用哪种排序算法？

Question

.NET 的

Array.Sort()

方法使用哪种排序算法？

Answer 1

Array.Sort()

根据输入的大小选择三种排序算法之一：

1. 如果大小小于16个元素，则使用插入排序算法。
2. 如果大小超过

   2 * log^N

   （其中

   N

   是输入数组的范围），则使用堆排序算法。
3. 否则，它使用快速排序算法

来源：MSDN 上的 Array.Sort(Array) 方法。

Answer 2

事实上，这并不像看起来那么容易。看起来 .NET 正在根据输入及其大小实现一组不同的排序算法。我曾经从 CLR 反编译

Array.Sort()

，看起来它们同时使用了堆、插入和快速排序。

Answer 3

它使用QuickSort算法。

来源：

• Array.Sort 方法 _{（MSDN，备注部分）}

Answer 4

来自 MSDN

的更多注释

此方法使用 introspective 排序（introsort）算法作为 如下：

如果分区大小少于 16 个元素，则使用 插入 排序算法.

如果分区的数量超过2 * LogN，其中N是范围 输入数组，它使用Heapsort算法。

否则，它使用快速排序算法。

这个实现执行的排序不稳定；也就是说，如果两个 元素相等，它们的顺序可能不会保留。相比之下，一个 稳定排序保留相等元素的顺序。

对于使用堆排序和快速排序排序的数组 算法，在最坏的情况下，该方法是一个 O(n log n) 操作， 其中 n 是长度。

调用者注意事项 仅使用 .NET Framework 4 及更早版本 快速排序算法。快速排序识别无效比较器 排序操作抛出异常的某些情况 IndexOutOfRangeException 异常，并抛出 ArgumentException 调用者的例外。从 .NET Framework 4.5 开始， 可能之前抛出的排序操作 ArgumentException 不会抛出异常，因为插入 排序和堆排序算法不会检测无效的比较器。为了 大多数情况下，这适用于元素少于 16 个的数组。

Answer 5

如上所述的快速排序。但它并不适用于所有数据！

通过使用反射器：它确实在本机 dll 中进行排序 -> 对于一维数组最常见的情况，升序。然而，其他情况在托管代码中排序 - 几乎没有应用优化。因此他们的速度通常要慢得多。

Answer 6

它确实使用了Introsort算法，这是一种混合排序算法，由以下内容组成：

• 插入排序
• 堆排序
• 快速排序

在平均/最差情况下，性能为 O(n log n)。 Introsort 是就地（不需要大量 RAM）且不稳定（无法预测相等元素的顺序）算法

来自MSDN

该方法使用内省排序（introsort）算法作为 如下：

如果分区大小小于或等于16个元素，则使用插入排序算法。

如果分区数量超过 2 * LogN（其中 N 是输入数组的范围），则使用堆排序算法。

否则，它使用快速排序算法。

Answer 7

它使用快速排序来实现排序目的