algorithm - 对长度为 2 的集合进行快速排序

Question

当对数据集进行快速排序时，列表会被拆分并递归，因为解决方案会在较小的列表上调用自身。我在算法上练习快速排序，但长度为 2 的子列表是我鞋中的一 block 石头，我无法解决它。原始列表是:

2  0  1  7  4  3  5  6

枢轴在 2，左边在 0，右边在 6，我开始了。向左移动到 7，7>=2。向右下移到 1，1<=2。左和右已经交叉了。据我了解，现在右成为 split 点并形成两个新列表。

2  0      1      7  4  3  5  6

如您所见，第一个列表 2 和 0 有 2 个项目。所以2是枢轴，0是左右。左不顺，右顺到2，2<=2。左右已经交叉，所以 p 替换 R 并且 L 向前是一个新列表。但这会使 2 和 0 未排序。

我哪里错了？

Answer 1

你的问题来自于我没有在它的排序位置移动枢轴。使用 pivot 2 进行分区后，您的数组应如下所示:

0  1  2  7  4  3  5  6
      ^

让我们通过输入数组 13 19 9 5 12 8 7 4 21 2 6 11 完成分区过程。让我们选择 11 作为基准。

在这个过程中，你需要维护两个指针，一个指向第一个大于基准^^的元素之前的元素，另一个指向你正在查看的当前 ||。

代码如下所示:

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

你能继续吗？