使用中间元素作为枢轴的快速排序算法状态

Question

我需要帮助才能准确理解快速排序算法的工作原理。一直在看教学视频，还是没有完全掌握。

我有一个未排序的列表：1、2、9、5、6、4、7、8、3 我必须使用 6 作为基准对其进行快速排序。 我需要在每次分区过程后查看列表的状态。

我的主要问题是理解枢轴前后元素的顺序。因此，在这种情况下，如果我们将 6 作为主元，我知道数字 1 - 5 将在 6 之前，而 7 - 9 将在 6 之后。但是，根据我上面的列表，数字 1 - 5 和 7 - 9 在第一个分区中的顺序是什么？

这是我想要使用的分区算法（请记住我使用中间元素作为我的初始基准）：

1. 确定主元，并将主元与列表的第一个元素交换。

假设索引smallIndex指向最后一个小于主元的元素。索引 smallIndex 被初始化为列表的第一个元素。

2. 对于列表中剩余的元素（从第二个元素开始） 如果当前元素小于pivot

   一个。增量 smallIndex b.将当前元素与smallIndex.

指向的数组元素交换

3. 交换第一个元素，即枢轴，与smallIndex指向的数组元素。

如果任何人都可以在算法中对列表进行每次微小更改后显示该列表，那就太棒了。

Answer 1

没关系

所有重要的 - 分区过程断言的所有 - 是，在 运行 之后，出现的中心点左侧没有任何值大于pivot 并且右侧没有小于 pivot 值的值。

两个分区的内部顺序然后在随后的每一半的递归调用中处理。