如何修改Lomuto分区方案？
Lomuto分区是快速排序中使用的一种简单分区算法。 Lomuto 算法对子数组 A[left] ... A[right] 进行分区，并假设 A[left] 是主元。如何修改此算法以使用给定的pivot P（与A[left]不同）分区A[left] ... A[right]代码>) ?
Lomuto partition is a simple partition algorithm used in quicksort. The Lomuto algorithm partitions subarray A[left] ... A[right] and assumes A[left] to be a pivot. How to modify this algorithm to partition A[left] ... A[right] using a given pivot P (which differs from A[left]) ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
Lomuto 的分区算法取决于主元是被分区子数组的最左边的元素。也可以修改为使用枢轴最右边的元素；例如，请参阅 CLRS 第 7 章。
对枢轴使用任意值（例如不在子数组中的值）会在快速排序实现中搞砸事情，因为无法保证您的分区使问题变得更小。假设您的旋转值为零，但所有 N 个数组条目均为正数。然后你的分区将给出元素 <= 0 的零长度数组和包含元素 >= 0 （这是全部）的长度为 N 的数组。在这种情况下，尝试进行快速排序时会出现无限循环。如果您尝试使用 Lomuto 分区的修改形式来查找数组的中位数，则相同。分区主要取决于从数组中选择一个元素作为旋转依据。您基本上会失去后置条件，即元素（枢轴）将在分区后永久固定到位，这是 Lomuto 的分区所保证的。
Lomuto 的算法还严重依赖于位于被分区数组的第一个或最后一个位置的元素的旋转。如果您以不位于数组最前端或最末尾的元素为旋转轴，那么作为 Lomuto 分区工作原理的核心的循环不变量将是一场噩梦。
作为第一步，您可以通过将其与第一个（或最后一个，如果您以这种方式实现）元素交换来对数组的不同元素进行旋转。查看 MIT 关于 Quicksort 的视频讲座，了解课程 6.046J，其中他们深入讨论了 Lomuto 的分区算法（尽管他们只是将其称为分区）以及基于该算法的快速排序的普通实现，更不用说在讨论随机形式的快速排序：
http://www.youtube.com/watch?v= vK_q-C-kXhs
CLRS 和Programming Pearls 都有关于快速排序的精彩部分，如果您可能在算法类或其他方面使用一本较差的书。
Lomuto's partioning algorithm depends on the pivot being the leftmost element of the subarray being partitioned. It can also be modified to use the rightmost element of the pivot instead; for instance, see Chapter 7 of CLRS.
Using an arbitrary value for the pivot (say something not in the subarray) would screw things up in a quicksort implementation because there would be no guarantee that your partition made the problem any smaller. Say you had zero as the value you pivoted on but all N array entries were positive. Then your partition would give at zero-length array of elements <= 0 and an array of length N containing the elements >= 0 (which is all of them). You'd get an infinite loop trying to do quicksort in that case. Same if you were trying to find the median of the array using that modified form of Lomuto's partition. The partition depends critically on choosing an element from the array to pivot on. You'd basically lose the postcondition that an element (the pivot) would be fixed in place for good after the partition, which Lomuto's partition guarantees.
Lomuto's algorithm also depends critically on pivoting on an element that is either in the first or last position of the array being partitioned. If you pivot on an element not located at either the very front or very end of the array, the loop invariant that is the core of why Lomuto's partition works would would be a nightmare.
You can pivot on a different element of the array by swapping it with the first (or last if you implement it that way) element as the first step. Check MIT's video lecture on Quicksort for course 6.046J where they go in depth discussing Lomuto's partitioning algorithm (though they just call it Partition) and a vanilla implementation of quicksort based on it, not to mention some great probability in discussing the expected runtime of a randomized form of quicksort:
http://www.youtube.com/watch?v=vK_q-C-kXhs
CLRS and Programming Pearls both have great sections on quicksort if perhaps you're stuck using an inferior book for an algorithms class or something.
取决于你如何定义 P，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，但我不明白为什么您需要这样做。
depends on how you define P, is P an index or a particular element?
if it is an index, then it is easy. you modify your two passes
... 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) ...if P is not an index, but a particular value, then you would need to search for it first, and only then do the above with the resultant index. Because the array is not sorted yet, you can only search linearly. You could also come up with a more clever scheme (hashtable) for finding your pivot P, but I don't see why you would need to do such a thing.