我以前从未见过双枢轴快速排序。
是快速排序的升级版吗？
双枢轴快速排序和快速排序有什么区别？
我在 Java 文档中找到了这个。
排序算法是双枢轴快速排序
作者：弗拉基米尔·雅罗斯拉夫斯基、乔恩·本特利和约书亚·布洛赫。这个算法
在许多数据集上提供 O(n log(n)) 性能，这会导致其他问题
快速排序会降低二次性能，并且通常是
比传统（单枢轴）快速排序实现更快。
然后我在谷歌搜索结果中找到了这个。
快速排序算法原理：
- 从数组中选取一个元素，称为主元。
- 重新排序数组，使所有小于基准的元素都位于基准之前
枢轴和所有大于枢轴的元素都位于它之后（相同的值可以
无论哪种方式）。划分之后，枢轴元素就处于其最终位置。
- 对较小元素的子数组和较大元素的子数组进行递归排序。
相比之下，双枢轴快速排序：
- 对于小数组（长度
- 选择两个主元元素 P1 和 P2。例如，我们可以得到第一个元素
a[left] 作为 P1，最后一个元素 a[right] 作为 P2。
- P1 must be less than P2, otherwise they are swapped. So, there are the following parts:
- 第 I 部分，索引从 left+1 到 L–1，元素小于 P1，
- 第二部分，索引从 L 到 K–1，元素大于或等于 P1 且小于或等于 P2，
- 第三部分，索引从 G+1 到 right–1，元素大于 P2，
- 第四部分包含其余要检查的元素，索引从 K 到 G。
- 第四部分中的下一个元素 a[K] 与两个主元 P1 和 P2 进行比较，
并放置到相应的 I、II 或 III 部分。
- 指针L、K和G沿相应方向改变。
- 当 K ≤ G 时，重复步骤 4 - 5。
- 主元元素 P1 与第 I 部分的最后一个元素交换，
枢轴元素 P2 与第 III 部分中的第一个元素交换。
- 对于第 I 部分、第 II 部分和第 III 部分的每个部分，递归地重复步骤 1 - 7。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
