java - 快速排序可视化？

Question

我对编程还很陌生，想要一些使用三中位数分区和 3 截止值的快速排序算法的可视化表示。

我希望看到整个迭代过程，因为 Java 算法对我来说很难理解。

例如，尝试对这个数组应用快速排序:[2, 6, 3, 1, 6, 5, 2, 4, 8]

使用三中值规则，基准点是最左边、中间和最右边元素的中值。所以 2、6 和 8 的中位数是 6。现在怎么办？

Answer 1

下一步是划分:当你选择了一个枢轴后，将所有小于该枢轴的元素向左移动，将所有大于该枢轴的元素向右移动。完成后，您可以分别在左侧和右侧排序。

分区前:

[2,6,3,1,6,5,2,4,8]

分区后<6在左边，>=6右边:

[2,3,1,5,2,4] [6,6,8]

要左右排序，在两边重复相同的步骤。

我让您发现分区过程的非常详细信息(真正的分区过程以不同的顺序保留元素)。

要记住的问题:

• 划分后，两边必须至少保留一个元素，否则程序会一直循环下去(更糟的是，只剩下一个元素可能是主元)；

• 理想情况下，分区将数组拆分为大小大致相等的两个子数组；但是也会出现非常不相等的大小，使算法慢得多；三中值启发法并不能完全避免这种现象；

• 算法是以递归方式编写的(排序函数调用自身)。对两个子数组进行排序时，从最小的开始，以使嵌套调用的数量最少。这很重要；

• 该过程对于小型阵列来说是多余的，这就是为什么建议切换到更简单的方法，例如在这种情况下使用 StraightInsertion 或 StraightSelection。

您可以将整个排序过程描绘成一棵二叉树，其中一个节点持有一个数组，区分主元，并且有两个儿子持有子数组。