以中间元素为枢轴的快速排序 [英] Quick sort with middle element as pivot

问题描述

我对快速排序的理解是

1. 选择一个枢轴元素(在这种情况下，我选择中间元素作为枢轴)
2. 在极端情况下初始化左右指针.
3. 找到枢轴左侧的第一个大于枢轴的元素.
4. 类似地找到pivot右侧的第一个小于pivot的元素
5. 交换在 3 和 4 中找到的元素.
6. 重复 3,4,5 除非左 >= 右.
7. 对左右子数组重复整个操作，因为现在将枢轴放置在其位置.

我确定我在这里遗漏了一些东西并且非常愚蠢.但以上似乎不适用于此数组:

I am sure I am missing something here and being very stupid. But above does not seems to be working fot this array:

  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 的右边?

Now what ? There is no element smaller than 6 on it's right side. How 7 is going to go to the right of 6 ?

推荐答案

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

There is no upfront division between the left and the right side. In particular, 6 is not the division. Instead, the division is the result of moving the left and right pointer closer to each other until they meet. The result might be that one side is considerably smaller than the other.

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

Your description of the algorithm is fine. Nowhere does it say you have to stop at the middle element. Just continue the execute it as given.

顺便说一句:在排序期间可能会移动枢轴元素.即使已经移动，也只需继续与 6 进行比较.

BTW.: The pivot element might be moved during the sorting. Just continue to compare against 6 even if it has been moved.

更新:

您对算法的描述确实存在一些小问题.一个是第 3 步或第 4 步需要包含与枢轴相等的元素.让我们像这样重写它:

There are indeed a few minor problem in your description of the algorithm. One is that either step 3 or step 4 need to include elements that are equal to the pivot. Let's rewrite it like this:

我对快速排序的理解是

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

这篇关于以中间元素为枢轴的快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！