为什么 Quicksort 的函数调用栈很深，输入有很多重复项？
Why does Quicksort have deep function call stack with many duplicates in input?
我正在阅读 Elements of Programming Interviews，第 43 页上有以下 line/quote：
Implemented naively, quicksort has large run times and deep function call stacks
on arrays with many duplicates because the subarrays may differ greatly in size.
One solution is to reorder the array so that all emements less than the pivot appear first,
followed by elements equal to the pivot, followed by elements greater than the pivot.
This is known as Dutch National Flag partitioning.
我很难想象第一行中描述的问题，所以我不明白荷兰国旗分区方案有何帮助。我找不到能清楚解释这一点的网页。我可以得到一些帮助来直观地解释一下吗？
快速排序算法的步骤之一需要一些算法根据选定的枢轴分区数据。理想的情况是每个分区都尽可能小，这样就需要更少的进一步划分。如果超过一半的元素最终在一个分区中，则需要更多的步骤来结束算法。
作为为什么重复导致这种不对称的说明性示例，请考虑对以下列表进行排序，其中八个元素中有六个具有相同的值：
2, 2, 1, 2, 2, 2, 2, 3
如果要求您将其划分为两个列表，您最好将所有小于主元的元素放入一个分区，将所有大于或等于主元的元素放入另一个。
这就是常见的 "Lomuto's algorithm" 的工作方式，其中枢轴本身被排除在两个分区之外。该算法通常被认为相对容易理解和实现，因此可能是作者使用短语“简单实现”时的想法。
在这个方案中，第一步可能将列表划分如下：
- 枢轴：2
- 小于枢轴: 1
- 大于或等于主元：2, 2, 2, 2, 2, 3
然后递归划分第二个分区：
- 枢轴：2
- 小于主元：[空列表]
- 大于或等于主元：2, 2, 2, 2, 3
第 3 步：
- 枢轴：2
- 小于主元：[空列表]
- 大于或等于主元：2、2、2、3
第 4 步：
- 枢轴：2
- 小于主元：[空列表]
- 大于或等于主元：2、2、3
第 5 步：
- 枢轴：2
- 小于主元：[空列表]
- 大于或等于主元：2、3
第 6 步：
- 枢轴：2
- 小于主元：[空列表]
- 大于或等于枢轴：3
这里递归终于可以停止了。如果分区总是大小相等（分区 4、2，然后 1），这比我们预期的 3 个步骤要糟糕得多。枢轴的选择无关紧要，因为即使我们早点找到 3 的正确位置，我们仍然需要为列表中的每个 2 走一步。
“胖主元”或“荷兰国旗”分区方案通过将所有 等于 主元的值分成第三个分区来扩展上述方案。不仅仅是平衡分区，结果是两个分区都变小了。
在我们的示例中，结果立即如下所示：
- 枢轴：2
- 等于主元：2, 2, 2, 2, 2
- 小于枢轴: 1
- 超过支点：3
由于新分区中的值都相等，因此不需要进一步排序。在我们的示例中，其余分区各有一个元素，因此根本不需要执行任何递归。对于不太极端的情况，剩下要排序的两个分区都会变小，因此需要更少的进一步排序步骤。
但是，由于分区算法的复杂性更高，因此一个分区步骤的成本会更高。
其他分区方案有两个分区，但允许等于主元的值位于任一分区中。这意味着分区可以在每一步均匀调整大小，即使有重复值（尽管它不保证它们会是）。 The original algorithm proposed by Tony Hoare 发明快速排序时有这个 属性.
在这种情况下，第一步可能会给出这样的结果：
- 左分区: 2, 2, 1, 2
- 右分区: 2, 2, 2, 3
对于我们的极端示例，这比“胖主元”效率低，但比拥有一个非常大的分区和一个非常小的分区要高效得多。
quicksort has large run times and deep function call stacks
on arrays with many duplicates
这仅适用于 Lomuto 类型的分区方案，它是 1984 年首次出现的快速排序的变体，与 1961 年发布的原始 Hoare 分区方案相对。通常 Lomuto 分区步骤会产生 3 个子分区：元素< pivot, pivot (单个元素), elements >= pivot.在所有元素都相等的情况下，那么一个划分步骤导致0个元素=pivot，在n-1个元素划分上递归，每层递归只去掉一个元素，最差时间复杂度为 O(n^2).
的快速排序的案例行为
对于 Hoare 分区方案，随着重复次数的增加，分区将导致更接近大小相等的子分区。在所有元素都相等的情况下，Hoare 分区方案会导致理想的 50% / 50% 拆分，因为分区循环会导致工作左（维基文章中的i）右边（维基文章中的j）索引在中间相遇。会有不必要的相等元素交换，但避免交换的检查通常会比仅对典型情况进行交换增加 运行 时间。一般来说，随着重复百分比的增加，索引在分区中间附近相遇的可能性就越大。
当主元是重复值之一时，按照原始问题中的建议进行三向分区会有所帮助。在枢轴成为子数组中的重复项之一之前可能需要相当多的递归级别，但会从进一步的递归中消除枢轴及其重复项。这将避免由于大量相等值而导致的最坏情况时间复杂度 O(n^2)，但会比 Hoare 慢，除非存在大量相等值。
https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme
https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
https://en.wikipedia.org/wiki/Quicksort#Repeated_elements
虽然在原始问题中没有要求，但已经发表了一些评论，要求解释 Hoare 和 Lomuto 方案。两种方案都使用两个索引，并进行了优化以减少比较次数（以更多交换为代价）。这些解释是针对上面链接的 Hoare 和 Lomuto 的 Wiki 示例，我添加了一个基于 Lomuto 的荷兰国旗示例。
Hoare - 设置 pivot = 数组的中间元素，array[floor((lo + hi)/2)]。内循环的简单实现：从左到右扫描一个元素 > pivot (index i)，从右到左扫描一个元素 < pivot (index j), 交换元素，继续这个过程，直到两个索引相遇或交叉。内部循环需要检查以确保索引没有超出被分区的子数组的边界。 Hoare 通过将比较更改为 >= 和 <= 对此进行了优化，这消除了对超出子数组边界的检查的需要，代价是有时交换相等的元素。此后，array[lo .. j] 的元素 <= pivot 和 array[j+1 .. hi] 的元素 >= pivot.
Lomuto - 设置 pivot = array[hi]。 i 初始化为 lo。 j 当前查找元素的索引 < pivot.主循环：for j = lo until j == hi increment j: if array[j] < pivot, then: swap(array[i], array[j]) and increment i.每次迭代后，array[lo .. i-1] < pivot, array[i .. j-1] >= pivot 的元素。请注意 i == j 直到 array[j] >= pivot 的第一个实例，虽然在 i == j 时交换是不必要的，但它比检查 i==j 以避免交换更快，因为 i != j 之后array[j] >= pivot 的第一个实例。主循环完成后，array[i] 与 array[hi] 交换以将枢轴放置到位。此后，array[lo .. i-1] 的元素 < pivot, array[i] == pivot, array[i+1 .. hi] 的元素 >= pivot.
基于 Lomuto 的荷兰国旗方案 - 在 Lomuto 主分区循环完成后，在数组 [i+1 .. hi] 上使用类似的逻辑重复该过程，（使用 j和 k)，以 array[lo .. i-1] < pivot, array[i .. j] == pivot, array[j+1 .. hi] 结束> 枢轴。
“因为子数组的大小可能相差很大”这样说。主元和数组值可以是这样的，即大小为 N 的子数组被分成两个大小为 N-1 和 1 的子数组。这会造成退化情况，使得 N 次递归调用被堆叠。
我正在阅读 Elements of Programming Interviews，第 43 页上有以下 line/quote：
Implemented naively, quicksort has large run times and deep function call stacks on arrays with many duplicates because the subarrays may differ greatly in size.
One solution is to reorder the array so that all emements less than the pivot appear first, followed by elements equal to the pivot, followed by elements greater than the pivot.
This is known as Dutch National Flag partitioning.
我很难想象第一行中描述的问题，所以我不明白荷兰国旗分区方案有何帮助。我找不到能清楚解释这一点的网页。我可以得到一些帮助来直观地解释一下吗？
快速排序算法的步骤之一需要一些算法根据选定的枢轴分区数据。理想的情况是每个分区都尽可能小，这样就需要更少的进一步划分。如果超过一半的元素最终在一个分区中，则需要更多的步骤来结束算法。
作为为什么重复导致这种不对称的说明性示例，请考虑对以下列表进行排序，其中八个元素中有六个具有相同的值：
2, 2, 1, 2, 2, 2, 2, 3
如果要求您将其划分为两个列表，您最好将所有小于主元的元素放入一个分区，将所有大于或等于主元的元素放入另一个。
这就是常见的 "Lomuto's algorithm" 的工作方式，其中枢轴本身被排除在两个分区之外。该算法通常被认为相对容易理解和实现，因此可能是作者使用短语“简单实现”时的想法。
在这个方案中，第一步可能将列表划分如下：
- 枢轴：2
- 小于枢轴: 1
- 大于或等于主元：2, 2, 2, 2, 2, 3
然后递归划分第二个分区：
- 枢轴：2
- 小于主元：[空列表]
- 大于或等于主元：2, 2, 2, 2, 3
第 3 步：
- 枢轴：2
- 小于主元：[空列表]
- 大于或等于主元：2、2、2、3
第 4 步：
- 枢轴：2
- 小于主元：[空列表]
- 大于或等于主元：2、2、3
第 5 步：
- 枢轴：2
- 小于主元：[空列表]
- 大于或等于主元：2、3
第 6 步：
- 枢轴：2
- 小于主元：[空列表]
- 大于或等于枢轴：3
这里递归终于可以停止了。如果分区总是大小相等（分区 4、2，然后 1），这比我们预期的 3 个步骤要糟糕得多。枢轴的选择无关紧要，因为即使我们早点找到 3 的正确位置，我们仍然需要为列表中的每个 2 走一步。
“胖主元”或“荷兰国旗”分区方案通过将所有 等于 主元的值分成第三个分区来扩展上述方案。不仅仅是平衡分区，结果是两个分区都变小了。
在我们的示例中，结果立即如下所示：
- 枢轴：2
- 等于主元：2, 2, 2, 2, 2
- 小于枢轴: 1
- 超过支点：3
由于新分区中的值都相等，因此不需要进一步排序。在我们的示例中，其余分区各有一个元素，因此根本不需要执行任何递归。对于不太极端的情况，剩下要排序的两个分区都会变小，因此需要更少的进一步排序步骤。
但是，由于分区算法的复杂性更高，因此一个分区步骤的成本会更高。
其他分区方案有两个分区，但允许等于主元的值位于任一分区中。这意味着分区可以在每一步均匀调整大小，即使有重复值（尽管它不保证它们会是）。 The original algorithm proposed by Tony Hoare 发明快速排序时有这个 属性.
在这种情况下，第一步可能会给出这样的结果：
- 左分区: 2, 2, 1, 2
- 右分区: 2, 2, 2, 3
对于我们的极端示例，这比“胖主元”效率低，但比拥有一个非常大的分区和一个非常小的分区要高效得多。
quicksort has large run times and deep function call stacks on arrays with many duplicates
这仅适用于 Lomuto 类型的分区方案，它是 1984 年首次出现的快速排序的变体，与 1961 年发布的原始 Hoare 分区方案相对。通常 Lomuto 分区步骤会产生 3 个子分区：元素< pivot, pivot (单个元素), elements >= pivot.在所有元素都相等的情况下，那么一个划分步骤导致0个元素
对于 Hoare 分区方案，随着重复次数的增加，分区将导致更接近大小相等的子分区。在所有元素都相等的情况下，Hoare 分区方案会导致理想的 50% / 50% 拆分，因为分区循环会导致工作左（维基文章中的i）右边（维基文章中的j）索引在中间相遇。会有不必要的相等元素交换，但避免交换的检查通常会比仅对典型情况进行交换增加 运行 时间。一般来说，随着重复百分比的增加，索引在分区中间附近相遇的可能性就越大。
当主元是重复值之一时，按照原始问题中的建议进行三向分区会有所帮助。在枢轴成为子数组中的重复项之一之前可能需要相当多的递归级别，但会从进一步的递归中消除枢轴及其重复项。这将避免由于大量相等值而导致的最坏情况时间复杂度 O(n^2)，但会比 Hoare 慢，除非存在大量相等值。
https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme
https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
https://en.wikipedia.org/wiki/Quicksort#Repeated_elements
虽然在原始问题中没有要求，但已经发表了一些评论，要求解释 Hoare 和 Lomuto 方案。两种方案都使用两个索引，并进行了优化以减少比较次数（以更多交换为代价）。这些解释是针对上面链接的 Hoare 和 Lomuto 的 Wiki 示例，我添加了一个基于 Lomuto 的荷兰国旗示例。
Hoare - 设置 pivot = 数组的中间元素，array[floor((lo + hi)/2)]。内循环的简单实现：从左到右扫描一个元素 > pivot (index i)，从右到左扫描一个元素 < pivot (index j), 交换元素，继续这个过程，直到两个索引相遇或交叉。内部循环需要检查以确保索引没有超出被分区的子数组的边界。 Hoare 通过将比较更改为 >= 和 <= 对此进行了优化，这消除了对超出子数组边界的检查的需要，代价是有时交换相等的元素。此后，array[lo .. j] 的元素 <= pivot 和 array[j+1 .. hi] 的元素 >= pivot.
Lomuto - 设置 pivot = array[hi]。 i 初始化为 lo。 j 当前查找元素的索引 < pivot.主循环：for j = lo until j == hi increment j: if array[j] < pivot, then: swap(array[i], array[j]) and increment i.每次迭代后，array[lo .. i-1] < pivot, array[i .. j-1] >= pivot 的元素。请注意 i == j 直到 array[j] >= pivot 的第一个实例，虽然在 i == j 时交换是不必要的，但它比检查 i==j 以避免交换更快，因为 i != j 之后array[j] >= pivot 的第一个实例。主循环完成后，array[i] 与 array[hi] 交换以将枢轴放置到位。此后，array[lo .. i-1] 的元素 < pivot, array[i] == pivot, array[i+1 .. hi] 的元素 >= pivot.
基于 Lomuto 的荷兰国旗方案 - 在 Lomuto 主分区循环完成后，在数组 [i+1 .. hi] 上使用类似的逻辑重复该过程，（使用 j和 k)，以 array[lo .. i-1] < pivot, array[i .. j] == pivot, array[j+1 .. hi] 结束> 枢轴。
“因为子数组的大小可能相差很大”这样说。主元和数组值可以是这样的，即大小为 N 的子数组被分成两个大小为 N-1 和 1 的子数组。这会造成退化情况，使得 N 次递归调用被堆叠。