数据结构（邓俊辉）学习笔记】排序 3——快速排序：快速划分（ LGU 版）

1. 不变性

实际上同样是按照霍尔爵士最初的设想和思路，快速排序算法还有很多其它的实现方式，比如在第一节我们就来介绍其中的一个有趣变种。

新算法的原理及过程同样可以由这样一组图来示意。可以看到与此前的基本版本相比，这里的不几乎完全一样。

首先，我们也是始终将整个序列视作为四个部分，也就是一个候选的轴点，以及名为 L G 和 U 的三个子序列。而且这里同样始终要求，在数值上子系列 L 中的元素都必须严格的小于候选轴点，而且对称的子序列 G 中的元素在数值上也不得小于候选轴点。

然而从这图中我们也可以发现，这个新的版本与此前的基础版本也的确存在着微细而本质的差异，这种差异就体现在 L、U 和 G 这三个子序列的相对位置。你应该记得在基础版本中子序列 U 是加在 L 与 G 之间的，而现在的次序则由以前的 LUG 变成了现在的 LGU。当然我们在这里也约定这三个子区间的边界将分别由 lo mi hi 以及 k 来界定。

也就是说 lo 和 mi 之间是 L，mi 与 k 之间是 G，而 k 到 hi 则为 U。那么在继续维持不变性的前提下，新的这个算法是如何使得子序列 L 和 G 得以单调的递增呢。

2. 单调性

实际上新的这个算法依然是反复迭代式进行的，在每一步迭代中，我们考察的都是子序列 U 的首元素，也就是由当前的 k 所指示的那个元素 x。我们将根据 x 的数值大小将它归入到 G 或者 L 子序列当中。具体来说，根据这个元素与候选轴点之间的数值大小，无非两种情况。

• 首先如果这个元素不小于候选轴点，我们就可以直接地拓展子序列 G。这种情况在图中显而易见。既然 x 不小于候选节点，所以它自然有资格加入到子序列 G 中，因此我们只需简明的将它归入到 G 中。请注意在这种情况下，L 会保持不变。

  从代码实现的角度来看，这种情况也是非常好描述的，具体来说，经过一次比较即可判断是否属于这种情况。若果真属于这种情况，我们就简明地令 k 递增一个单位，令它指向原先的后继，从而隐式地完成将元素 x 归入 G 中的功能。

• 那么反过来，如果当前的这个元素要小于候选轴点呢？自然的此时应该将这个 x 归入到子序列 L 中。然而我们却发现，此时的 L 无论向左或向右都无法拓展。因此我们需要通过一种变通的方法将 x 加入到 L 中。

  具体来说，我们需要将子序列 G 向后移动一个单元，从而等效于腾出一个空间，以便 x 能够转入其中，从而完成 L 向右的拓展。那么难道我们真的需要将 G 整体的向右移动一个单元吗？

  当然，如果你不考虑效率，这种方法固然是可行的。但实际上我们有更好的方法来使 G 向后移动一个单元。只要学过初等的物理，你就应该知道，在沿着一个表面移动物体时，我们有两种移动的方法，效率各自不同。

  当然这里的效率是指在移动过程中所受到的阻力或者说摩擦力，如果是整体的后移，也就相当于物理学上的平行移动。我们知道这种平行移动所遇到的摩擦力是更大的，你应该记得在这种情况下，你的物理老师曾经建议过你改用滚动的方式来替代平行移动的方式。

  没错，相对而言，滚动的方式所遇到的摩擦力会更小。那么在这里我们如何将这种思路具体的兑现为 G 的一次高效移动呢？没错，只需将 G 此前的首元素直接挪至到最后作为末元素，而其余的绝大多数元素都可以在原地保持不动。

  我们知道子系列 G 此前的首元素是由 mi 加 1 所指示的，而此后新的末元素应该是由 k 加 1 所指定的。当然这个末元素当前也就是 x，因此我们可以将 G 的滚动后移以及 x 归入到 L 中去，这样两步紧凑地实现为这样一个交换语句。

至此，虽然我们只介绍了这样两种情况的处理方法，但在算法整个过程中的绝大多数时刻，我们凭借这两招就已足够了，我们唯一还需要交代的是这个算法终止之前的最后一步。

到了那样一个时刻，子系列 U 已经变成了空，而 L 和 G 已经占据了除候选轴点之外的所有范围。至此也就到了这个候选轴点就位，并成为一个真正轴点的时刻了，那么这个候选轴点应该被安放到什么位置呢？

没错，根据我们 L 小 G大的不变性，这个候选轴点应该被安置于 L 和 G 之间的交接处。更准确地讲，G 将保持不动，而 L 的末元素则应该被替换为这个候选轴点。同样的，为此我们只需在这个末元素与候选轴点之间完成一次互换。

3. 实现

在这里我们就给出这个新的 partition 算法的一种实现。

1. 沿用我们的习惯，依然将首元素作为候选轴点。

2. 接下来是一个循环，将反复地考察子区间 U 的首元素，也就是由 k 所指定的那个元素。按照刚才所介绍的算法原理，如果当前的这个元素 k 相对于候选轴点而言更小，就需要将它归入到子序列 L 当中。

3. 刚才讲过，这可以通过在子序列 G 的首元素与元素 k 之间的一次交换来完成。

   至此，你或许会感到疑惑。是的，如果当前元素 k 不小于候选轴点，又该如何呢？也就是说这里的 if 按说还应该有一个配对的 else。没错，的确应该有一个 else，只不过这里的 else 是隐藏的，看不见的。刚才我们已经分析过，在 else 那种情况下，我们只需简明的令 k 递增一个单位，而实际上在刚才 if 那个分支本来也应该有一个可以递增的功能。既然无论if 或 else 我们都需要令 k 向后平移一个单位，因此不妨将这两种情况合并起来，统一计入 for 循环的更新环节。如此，不仅 if 分支中的 k++ 可以省略掉，而更重要的是整个 else 分支也不必显示给出了。

4. 当然在整个循环退出之后，算法返回之前，我们还需要另做一次交换操作，实现候选节点的真正就位。

另外一点需要倒过来补充说明的是，在算法的入口处，我们还需要通过在整个序列中随机地选取一个元素，并将它与首元素互换，实现对候选轴点更为随机的选取，从而降低最快情况出现的概率，如我们此前所介绍的与三者取中法一样，这也是为此可以采用的常见手法。

4. 实例

在告别本节之前，我们不妨通过一个具体的实例，来切实的体验快速排序的这个新的版本。这里的输入序列由11个元素构成。

• 这个算法会首先将首元素6作为候选轴点，而其余的元素则整体构成子序列 U，当然相应的子序列 L 和 G 此时都是空。以下进入算法的迭代部分。

1. 首先在第一步迭代中，我们考虑的是 U 当前的首元素3。这个元素要比候选轴点更小。因此它应该被归入到子序列 L 中。在我们刚才实现的算法中，这就对应于 if 分支。当然这是一种退化的情况，因为这个兑换实际上就是它自己和自己，所以在位置上这个元素并没有实质的改变。然而此后在逻辑上，子序列 L 将拥有第一个元素，而不再是空。

2. 接下来我们继续考察新的首元素8a。因为它在数值上要大于候选轴点，所以对应于 else 那个分支，这是一个只需简明处理的分支。

   具体来说，我们在这种情况下只需解明的令 k++，从而在使得子序列 U 缩短一个单位的同时，使得子序列 G 拥有了第一个元素。

3. 再接下来我们会进而考虑新的首元素 1，可以看到它比候选轴点要更小，因此应该被归入到子序列 L 当中。我们需要令它和子序列 G 的首元素互换位置。当然此时 G 的首元素，也就是它那个唯一的元素 8a，可以看到在经过了这样一次交换之后，二者的位置的确颠倒了过来。

   请注意，在经过了这样一次交换之后，更主要的在逻辑上是等效于子序列 L 向后拓展了一个单位，同时子序列 G 滚动式的后移了一个单位。

4. 接下来，我们继续考察子序列 U 的首元素，也就是5a，可以看到它依然应该被归入到子序列 L 当中。为此我们依然需要令它和子序列 G 的首元素，也就是8a, 做一次交换。经过了这样的一次交换之后，不仅这两个元素的相对位置颠倒过来了，而且更重要的是在逻辑上，子序列 L 又继续向后拓展了一个单位，同时子序列 G 也滚动式的右后移了一个单位。

5. 接下来我们依然要考察子序列 U 新的这个首元素9，作为大于候选轴点的元素，它自然应该归入子序列 G 中。我知道这对于算法中的 else 分支，因此只需简明地利用 k ++， 就可以在逻辑上令子序列 G 向后拓展一个单位。

6. 在以下，我们仍然是要考察子序列 U 的首元素，这回轮到的是 8b，因为它不小于候选轴点，因此同样对应的是 else 那个分支。也就是说，我们依然只需简明地令k++，就可以使得子序列G继续向后拓展一个单位。

7. 接下来这个首元素4要小于候选轴点，所以它对应的是 if 分支，于是我们需要令它与子序列 G 的首元素8a 互换位置。在经过了这样一次交换之后，此序列 L 向后继续拓展一个单位，同时此序列 G 也滚动式的后移了一个单位。

8. 再接下来的这个首元素5b 同样应该被归入于子序列 L 当中。因此我们仍然需要令它与子序列 G 的首元素 9 互换位置。同理，在经过了这样一次交换之后，子序列 L 得以向后继续拓展一个单位，同时子序列 G 再次滚动式的后移一个单位。

9. 现在轮到新的首元素7了。它要比候选轴点更大，所以应该通过简明的 k ++，将它归入到子序列 G 中。同时子序列 L 保持不变。

10. 现在轮到子序列 U 的最后一个元素2了，它比候选轴点更小，因此应该被归入到子序列 L 中。我们的处理手法依然也就是要令这个元素与子序列 G 当前的首元元素8b 做一次交换。

    在经过最后的这一次交换之后，L 再次向后扩展了一个单位，而子序列 G 再次滚动的后移一个单位。至此子序列 U 变成空，因此循环得以退出。

11. 在算法终止之前，我们还需要完成最后一步，也就是令候选轴点就位，并成为一个名副其实的轴点。你应该记得我们的做法是，另这个候选轴点与当前子序列 L 的末元素，也就是2，互换位置。可以看到在如此交换之后，候选节点6的确成为了一个名副其实的轴点。

5. 时间 + 空间 + 稳定性

纵观整个算法的计算过程，我们为每一个元素只需花费常数的时间，因此这个新的 partition 算法总体依然只需线性的时间。当然，这里也只需要常数的辅助空间，因此它依然是一个就地的算法。

那么这个算法的稳定性呢？

在这个实例中我们可以看到，无论是5a 和5b，还是8a 和8b，重复元素之间的相对次序似乎是可以保持的。然而我们说这只是一个假象，对于子序列 L 中的重复元素而言，它们之间的相对位置的确是可以保持，因为根据这个算法的原理，所有此类的重复元素都是严格按照它们此前的相对次序加入到子序列 L 当中。
  ~  
那至此你可能会说，根据算法的原理，子系列 G 中的所有重复元素也是按照它们原有的次序加入到这个序列当中的，所以它们之间的相类次序也应该得以保持才是啊。当然这一判断并不全面，这里需要注意的是，与此序列 L 不同，子系列 G 有可能会向后滚动。

是的，尽管这种滚动的方式可以保证时间效率的最优，而由此却有可能导致不稳定性。

我们就以这里的重复元素8a 和8b 为例。当在最初进入到子序列G之后，的确保持了原始的相对次序。然而在经过了一次滚动之后，二者的次序已然颠倒了过来。而在经过了此后的另一次滚动之后，它们次序又再颠倒了一次，从而造成了能够保持原状的假象。

当然，子序列 L 中的重复元素之间的相对位置也并非是绝对一成不变的。你能举出这样的一个实例吗？