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

As per MSDN doc for Array.Sort,

根据Array.Sort的MSDN doc,

If the number of partitions exceeds 2 * logN, where N is the range of the input array, it uses a Heapsort algorithm.

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

What I don't know is what are the "number of partitions" and the "range" of an array. What are they?

我不知道的是数组的“分区数”和“范围”是什么。他们是什么?

1 个解决方案

#1

A partition in a sort is basically a section of the list based upon a pivot point. For example , using the quick sort algorithm to sort the following:

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

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

In the first pass, there are two partitions based off numbers that are less than or greater than 5

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

The range is the difference between the largest and smallest values, so in this example that is 7 (8 - 1)

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

So the line you are questioning works as

所以你提问的界限就像

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

#1