arrays - 数组的“分区数”和“范围”是多少？

Question

根据 MSDN 文档Array.Sort，

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

我不知道的是数组的“分区数”和“范围”是多少。这些是什么？

Answer 1

排序中的分区基本上是基于枢轴点的列表的一部分。例如，使用快速排序算法对以下内容进行排序：

                First Pass          Second Pass
3              3                     1
8              1                     3
5 <- Pivot     5---------            5
1              8                     7
7              7                     8

在第一遍中，有两个基于小于或大于5的数字的分区

范围是最大值和最小值之间的差，因此在本例中为7 (8 - 1)

所以你质疑的那条线是

 (2 * log(7)) > 2    == Use HeapSort
 1.691 > 2              false