分区元素

Question

我正在尝试理解以下文字：

你得到了一个列表，它刚刚使用标准分区算法进行了分区。你要说哪个元素可能是分区元素。例如，给定数字 [7, 6, 8, 20, 11, 5, 14]，那么只有 8 可能是分区元素，算法将继续对 [7, 6] 和 [20, 11, 5, 14].

我想了解 8 是这里的分隔元素吗？谢谢

Answer 1

在快速排序迭代结束时，主元 p（分区元素）左侧的每个元素都必须小于 p，右侧的每个元素都必须大于 p。这意味着 p 现在处于其最终排序位置。快速排序算法在两个结果子数组（左和右）上递归进行。

给定快速排序过程中的数组配置，您可以使用这个简单的二次过程识别可能已在上一次迭代中使用的主元：

foreach int m in the array
  if (all int l on the left of m verify l < m)
    AND (all int r on the right of m verify r >= m)
  then
    m was a possible pivot in the previous iteration

你可以做得比 O(n^2) 更好，但这是基本思想。

分区元素

Partitioning element

algorithm

partitioning