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。无交换。

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

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
^\#^