以第一个元素为轴心的快速排序

Question

我正在学习Quick-Sort，当第一个元素被选为轴心点时，我对它的工作原理感到困惑。

我正在尝试跟踪快速排序算法的第一步，将pivot S1移动到适当的位置。

例如: 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次交换才能将pivot S1移动到正确的位置？

Answer 1

快速排序将具有两个移动指针和一个旋转指针

并且这些移动指针的初始位置将是0和n-1个位置(第一个和最后一个元素)，并且右指针将向左移动以寻找较短的元素，然后一旦发现元素，左指针开始向右移动以搜索大于枢轴的元素一旦它们找到这些元素，它们都交换并继续执行相同的操作，直到两个指针相遇

一旦它们相遇，就会用pivot元素交换该元素。

查看下面示例中的指针移动

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