以中间元素为轴心进行快速排序

Question

我对快速排序的理解是

选择一个枢轴元素（在本例中我选择中间元素作为枢轴）
在极值处初始化左右指针。
找到主元左侧第一个大于主元的元素。
类似地找到pivot右边第一个小于pivot的元素
交换在 3 和 4 中找到的元素。
重复 3、4、5，除非左 >= 右。
对左子数组和右子数组重复整个操作，因为现在将主元放在它的位置。

我确定我在这里遗漏了一些东西并且非常愚蠢。但是上面的这个数组似乎不起作用：

  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 步需要包含与基准等于的元素。让我们这样重写它：

我对快速排序的理解是

选择一个枢轴值（在本例中，选择中间元素的值）
在极值处初始化左右指针。
从左指针开始向右移动，找到第一个大于或等于枢轴值的元素。
同理，从右指针开始向左移动，找到第一个元素，即小于枢轴值
交换在 3 和 4 中找到的元素。
重复 3,4,5 直到左指针大于或等于右指针。
对左指针左右两个子数组重复整个过程。

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

Answer 2

Quick Sort Given an array of n elements (e.g., integers):
-If array only contains one element, return
-Else
  pick one element to use as pivot.
  Partition elements into two sub-arrays:
    Elements less than or equal to pivot
    Elements greater than pivot
  Quicksort two sub-arrays
  Return results

Let i and j are the left and right pivots, then code for one array will look like this:

1) While data[i] <= data[pivot]
    ++i
2) While data[j] > data[pivot]
    --j
3) If i < j
    swap data[i] and data[j]
4) While j > i, go to 1.
5) Swap data[j] and data[pivot_index]

Position of index j is where array is to-be partitioned in two half and then same steps are applied to them recursively.

最后你得到一个排序数组。

Answer 3

你的困惑是因为你认为分区应该是分隔两者的界标。这不是真的（对于中间元素枢轴）！

Lomuto 的分区（枢轴 = 最右边的分区）。左：(lo ... p-1) （注意不包括枢轴） 右：(p+1 ... 高)
中间元素作为枢轴。该段被分区：左：（lo ... p）右：（p+1 ... 高） [https://en.wikipedia.org/wiki/Quicksort]

以中间元素为轴心进行快速排序

Quick sort with middle element as pivot

quicksort