快速排序递归计数
使用快速排序对n个元素进行排序列表的最小递归调用数量是多少。 我不明白，实际调用了递归函数的次数，特别是“最低数字”的含义
What is the minimum number of recursive call to sort a list of n elements using quick sort.
I cannot understand that how many times the recursion function is actually called and specifically what is meant by "minimum number "
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
快速排序是算法的集合，其中通过选择枢轴值，分区数据并在分区上进行递归来对数据集进行排序，直到分区大小小于2
。数据分为2集：
有效实现的元素使用详尽的方法选择枢轴值并将数据分配为3组：
，它们也可能切换到在特定分区大小以下的不同算法和检测到病理分布以下的其他算法，以避免二次时间复杂性。
对于三组实现，最佳情况是所有元素比较相等且无需递归的情况。这构成了最小递归调用的数量：
0。在其他情况下，递归调用的数量高度取决于数据分布，枢轴选择方法和其他实现选择，例如：
平均而言，快速排序的递归调用数量大约是：
请注意，递归深度（这是一个不同但重要的问题）可以限于 log 2 （n），通过结合迭代和递归，在较小的分区上递归，迭代较大的一个。
还要注意，可以使用长度 log 2 （n）的小数组来跟踪待处理的分区。
Quick Sort is a collection of algorithms where a data set is sorted by choosing a pivot value, partitioning the data and recursing on the partitions until the partition size is smaller than 2.
Simple implementations use the first, last or middle element as pivot and partition the data into 2 sets:
Efficient implementations use elaborate methods to choose the pivot value and partition the data into 3 sets:
They might also switch to a different algorithm below a certain partition size and or if a pathological distribution is detected, to avoid quadratic time complexity.
For the 3 sets implementations, the optimal cases are those where all elements compare equal and no recursion is needed. This constitutes the minimum number of recursive calls:
0.In other cases, the number of recursive calls is highly dependent on the data distribution, the pivot selection method and other implementation choices such as:
On average the number of recursive calls for quick sort is approximately:
Note that the depth of recursion, which is a different but important question, can be limited to log2(n) by combining iteration and recursion, recursing on the smaller partition and iterating on the larger one.
Note also that quick sort can be implemented without recursion, using small arrays of length log2(n) to keep track of pending partitions.