algorithm - 以第一个元素为中心的快速排序

Question

我正在研究快速排序，当第一个元素被选为轴心点时，我很困惑它是如何工作的。

我试图追踪快速排序算法的第一步，将枢轴 S[1] (17) 移动到适当的位置。

示例：[17, -10, 7, 19, 21, 23, -13, 31, 59]。

^# = pivot
^ pointer

我的理解：

对第一部分进行分区（这部分中的所有元素都小于枢轴）。

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                               ^

比较 1. 没有交换。

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                           ^

比较 2. 没有交换。

17, -10, 7, 19, 21, 23, -13, 31, 59
^#                      ^

比较 3. 交换。

-13, -10, 7, 19, 21, 23, 17, 31, 59
                     ^   ^#  

比较 4. 交换。

-13, -10, 7, 19, 21, 17, 23, 31, 59
                 ^   ^#  

比较 5. 交换。

-13, -10, 7, 19, 17, 21, 23, 31, 59
             ^   ^# 

比较 6. 交换。

-13, -10, 7, 17, 19, 21, 23, 31, 59
          ^  ^# 

比较 7. 没有交换。

 -13, -10, 7, 17, 19, 21, 23, 31, 59
       ^      ^# 

比较 9. 没有交换。

-13, -10, 7, 17, 19, 21, 23, 31, 59
  ^          ^# 

比较 10. 没有交换。

这是它的工作原理吗？是否需要 10 次比较和 4 次交换才能将枢轴 S[1] (17) 移动到正确位置？

标签： algorithmsortingquicksort

Answer 1

快速排序将有两个移动指针和一个枢轴指针

并且这些移动指针的初始位置将是 0 和 n-1 个位置（第一个和最后一个元素），并且右点将向左移动以寻找更短的元素，然后一旦找到该元素左指针开始向右移动以寻找一个大于枢轴的元素一旦他们找到这些元素，他们就会交换并继续做同样的事情，直到两个指针相遇

一旦他们相遇，就会将该元素与枢轴元素交换。

查看下面示例的指针移动

17, -10, 7, 19, 21, 23, -13, 31, 59 ^# ^

17, -10, 7, 19, 21, 23, -13, 31, 59 ^# ^

17, -10, 7, 19, 21, 23, -13, 31, 59 ^# ^

右指针找到 -13 < 17 现在开始移动左指针

17, -10, 7, 19, 21, 23, -13, 31, 59 \# ^ ^

17, -10, 7, 19, 21, 23, -13, 31, 59 \# ^ ^

17, -10, 7, 19, 21, 23, -13, 31, 59 \# ^ ^

左点找到一个值 19 > 17 现在交换两个指针值

17, -10, 7, -13, 21, 23, 19, 31, 59 \# ^ ^

开始移动正确的点以找到较小的值然后枢轴点

17, -10, 7, -13, 21, 23, 19, 31, 59 \# ^ ^

17, -10, 7, -13, 21, 23, 19, 31, 59 \# ^ ^

17, -10, 7, -13, 21, 23, 19, 31, 59 \# ^ ^

-13, -10, 7, 17, 21, 23, 19, 31, 59 ^ \#^