algorithm - 一组长度为2的Quicksort

当快速排序一个数据集时，列表会被拆分并且是递归的，因为解决方案会在较小的列表上调用自己。
我在一个算法上练习快速排序，但是一个长度为2的子列表是一块石头，我无法解决它最初的名单是：

2  0  1  7  4  3  5  6

轴在2，左在0，右在6，我开始向左移动到7，7>=2。右移到1，1

2  0      1      7  4  3  5  6

如您所见，第一个列表2和0是2个项目所以2是轴，0是左和右。左不移动，右移动到2，2我哪里做错了？

最佳答案

你的问题是因为我没有按顺序移动pivot。在使用pivot2进行分区之后，数组应该如下所示：

0  1  2  7  4  3  5  6
      ^

让我们使用输入数组来完成partition过程。让我们选择13 19 9 5 12 8 7 4 21 2 6 11作为轴心。
在这个过程中，您需要维护两个指针，一个是在第一个元素大于pivot11之前的元素指针，另一个是当前元素指针。
代码如下所示：

A is array left..right
pivot = A[right]
i = left - 1                 // the one before the first bigger than the pivot
for j = left to right - 1
    if A[j] <= pivot
        i = i + 1
        swap A[i] with A[j]
swap A[i+1] with A[right]    // put pivot at its place, i + 1 - is the index to split on

举个例子：

    13  19   9   5  12   8   7   4  21   2   6  11

    13  19   9   5  12   8   7   4  21   2   6  11   13 > 11, skip
^^  ||

    13  19   9   5  12   8   7   4  21   2   6  11   19 > 11, skip
^^      ||

     9  19  13   5  12   8   7   4  21   2   6  11    9 < 11, swap
    ^^      ||

     9   5  13  19  12   8   7   4  21   2   6  11    5 < 11, swap
        ^^      ||

     9   5  13  19  12   8   7   4  21   2   6  11   12 > 11, skip
        ^^          ||

     9   5   8  19  12  13   7   4  21   2   6  11    8 < 11, swap
            ^^          ||

     9   5   8   7  12  13  19   4  21   2   6  11    7 < 11, swap
                ^^          ||

     9   5   8   7   4  13  19  12  21   2   6  11    4 < 11, swap
                    ^^          ||

     9   5   8   7   4  13  19  12  21   2   6  11   21 > 11, skip
                    ^^              ||

你能继续吗？