线性时间分区

快速排序的真正工作发生在划分步骤中，该步骤将子数组序列[p..r]分布在从子数组选择的枢轴周围。 虽然我们可以选择子数组中的任何元素作为枢轴，但如果我们选择子数组的最右边元素A[r]作为枢轴，则很容易实现分区。

选择了一个枢后，我们通过从左到右遍历它来对子数组进行分区，将每个元素与枢进行比较。 我们在子数组中保留了两个索引q 和 j，将其分为四组。 我们使用变量名称q，因为该索引最终将指向我们的枢。 我们使用j是因为它是一个常见的计数器变量名，一旦我们完成，变量就会被丢弃掉。

最初，q和j都等于p。 在每一步，我们将组A中最左边的元素A[j]与枢轴进行比较。 如果A[j]大于枢轴，那么我们只增加j，这样分组G和U的向右边滑动一位：

如果A[j]小于或等于枢轴，那么我们将A[j]与A[q]（组G中最左边的元素）交换，增加j，并增加q，从而将分割组L和组G的分割线，分割组G和组U的分割线都向右滑动一个位置：

一旦到了枢轴，U组是空的。我们就会用G组最左侧的元素来交换枢轴：用 A[r] 交换 A[q]。这种交换把枢轴放在了L组和G组之间，即使L组和G组是空的，它也是正确的。

实现了这个想法的 分区 也回到了它最终放置枢轴的索引 q，这样一来，快速排序 就可以直接调用它，并且知道如何划分。

在子数组 array[4..9] 里，[12, 7, 14, 9, 10, 11] 的分区步骤如下：

使用$n$‍元素对子数组进行分区需要$\mathrm{\Theta }(n)$‍ 时间。 每个元素A[j]与枢轴进行一次比较。 A [j]可以与A[q]交换，也可以不交换，q可以增加也可以不增加，并且j总是递增。 每个子阵列元素执行的总行数是常数。 由于子数组有$n$‍个元素，因此分区的时间是$\mathrm{\Theta }(n)$‍：线性时间分区。

本内容是 达特茅斯计算机科学 教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。