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

提问者：小点点

我需要帮助了解快速排序算法的工作原理。我一直在看教学录像，但还是没能完全掌握它。

我有一个未排序的列表:1，2，9，5，6，4，7，8，3，我必须使用6作为枢轴快速排序它。我需要在每个分区过程之后看到列表的状态。

我的主要问题是理解枢轴前后元素的顺序。所以在这种情况下，如果我们以6为中心，我知道数字1-5会在6之前，7-9会在6之后。但是，在上面列出的第一个分区中，数字1-5和7-9的顺序是什么呢？

下面是我要使用的分区算法（我使用中间元素作为我的初始枢轴:

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

对于列表中的剩余元素（从第二个元素开始），如果当前元素小于枢轴

A.增量B。用指向的数组元素交换当前元素。

用指向的数组元素交换第一个元素，即pivot。

如果有人能在算法中的列表发生的每一个单独的小变化之后显示列表，那将是令人惊奇的。

共1个答案

匿名用户

没关系的。

所有重要的事情（分区过程断言的所有事情）是，在运行之后，在中心点的左侧没有出现大于枢轴的值，并且在右侧没有出现小于枢轴值的值。

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