quicksort - 以中间元素为基准的快速排序

Question

我对快速排序的理解是

1. 选择一个枢轴元素(在本例中我选择中间元素作为枢轴)
2. 在极值处初始化左指针和右指针。
3. 查找枢轴左侧第一个大于枢轴的元素。
4. 同样找到枢轴右侧第一个小于枢轴的元素
5. 交换 3 和 4 中找到的元素。
6. 重复 3,4,5，除非左 >= 右。
7. 对左右子数组重复整个过程，因为现在将枢轴放置在其位置。

我确信我在这里遗漏了一些东西并且非常愚蠢。但上面似乎不适用于这个数组:

  8,7,1,2,6,9,10,2,11 pivot: 6  left pointer at 8, right pointer at 11
  2,7,1,2,6,9,10,8,11 swapped 2,8  left pointer at 7, right pointer at 10

现在怎么办？它的右边没有小于6的元素。 7 如何位于 6 的右侧？

Answer 1

左侧和右侧之间没有预先划分。特别是，6 不是除法。相反，除法是将左指针和右指针彼此靠近直至相遇的结果。结果可能是一侧比另一侧小得多。

你对算法的描述很好。没有任何地方说你必须停在中间元素。只需继续按照给定的方式执行即可。

顺便说一句:在排序过程中枢轴元素可能会移动。继续与 6 进行比较，即使它已被移动。

更新:

您对算法的描述确实存在一些小问题。一是步骤 3 或步骤 4 需要包含等于主元的元素。让我们像这样重写它:

我对快速排序的理解是

1. 选择一个主值(在本例中，选择中间元素的值)
2. 在极值处初始化左指针和右指针。
3. 从左指针开始向右移动，找到第一个大于或等于主元值的元素。
4. 同样，从右指针开始向左移动，找到第一个元素，即小于主元值
5. 交换 3 和 4 中找到的元素。
6. 重复3、4、5，直到左指针大于或等于右指针。
7. 对左指针左侧和右侧的两个子数组重复整个操作。

pivot value: 6, left pointer at 8, right pointer at 11
8,7,1,2,6,9,10,2,11 left pointer stays at 8, right pointer moves to 2
2,7,1,2,6,9,10,8,11 swapped 2 and 8, left pointer moves to 7, right pointer moves to 2
2,2,1,7,6,9,10,8,11 swapped 2 and 7, left pointer moves to 7, right pointer moves to 1
pointers have now met / crossed, subdivide between 1 and 7 and continue with two subarrays