如何修改Lomuto分区方案?

Lomuto的分区算法依赖于被分区子数组中最左边的元素pivot。它也可以修改为使用pivot最右边的元素;例如,请参阅CLRS的第7章。

对轴使用任意值(比如说不在子数组中的某个值)会在快速排序实现中使事情变得更糟,因为无法保证分区会使问题变得更小。假设您的轴值为零,但所有N个数组项都为正。然后分区将给出一个长度为零的元素数组<=0和一个长度为N的数组,其中包含元素>=0(这就是所有元素)。在这种情况下,你会得到一个无限循环来尝试快速排序。如果您试图使用修改后的Lomuto分区形式来查找数组的中值,也是一样的。分区在很大程度上取决于从数组中选择要透视的元素。基本上,您将失去一个后置条件,即元素(轴心点)将在分区之后永久固定,这是Lomuto的分区保证的。

Lomuto的算法还非常依赖于旋转被分区数组的第一个或最后一个位置的元素。如果您的轴不在数组的最前端或最末端,那么Lomuto分区工作的核心循环不变量将是一个噩梦。

作为第一步,您可以通过将数组中的另一个元素与第一个(或者最后一个,如果您是这样实现的话)元素交换来对其进行透视。查看麻省理工学院6.046J课程关于快速排序的视频讲座,在那里他们深入讨论了Lomuto的分区算法(尽管他们只是称之为分区)和基于它的快速排序的普通实现,更不用说讨论随机形式的快速排序的预期运行时间的可能性了:

http://www.youtube.com/watch?v=vK_q-C-kXhs

clr和Programming Pearls在quicksort上都有很好的部分,如果你在算法类或其他东西上使用了一本劣质的书的话。

取决于如何定义P,P是索引还是特定元素? 如果它是一个索引,那么它很容易。你修改了你的两张通行证

...
i = left
j = right
while (a[i]<a[p]) i++
while (a[p]>a[j]) j--
if (i <= j)
    swap(a, i, j)
    qsort(a, left,i)
    qsort(a, j,right)
...

如果P不是一个索引,而是一个特定的值,那么您需要首先搜索它,然后对结果索引执行上述操作。由于数组尚未排序,因此只能进行线性搜索。你也可以想出一个更聪明的方案(哈希表)来找到你的pivot P,但我不明白你为什么需要这样做。