关于双路快排的疑问
来源：2-3 实现双路快速排序法
xiaobai00000
2020-12-24 22:20:08
# 具体遇到的问题
我感觉双路快排 就 partition2ways方法来说， 无法保证 一定是 “<特定值, =特定值,>特定值”这种形式，
只是尽量均匀的拆分， 因为 特定值可以排在两边任何一端，swap后 有可能 不能保证 与特定值相等的数 一定在中间。
取一组数 【4,6,5,2,3,8,7,1】， 标定点取 第一个元素【4】，双路快排后： [2,1,3,4,5,8,7,6] 完全符合；
取一组数 【4,6,5,2,3,8,7,4,1】， 标定点取 第一个元素【4】，双路快排后： [2,1,3,4,5,8,7,4,6] ，发现倒数第2个
元素 4 并没有排列到中间， 因为 4>=标定点【4】, 所以仍旧会-- 并不会停下来。
但经过 快排之中 sort里的拆分 和 partition2ways 协同合作时，就能正确排出顺序， 这里有点奇怪，partition2ways 明明没有将 =特定值 的元素放在最中间啊。
# 报错信息的截图
# 相关课程内容截图
# 尝试过的解决思路和结果
# 粘贴全部相关代码，切记添加代码注释（请勿截图）
在这里输入代码，可通过选择【代码语言】突出显示
2回答
-
双路快排没有保证分成三部分。三路快排保证分成三部分。课程后续会讲三路快排。
双路快排依然只是分成两部分，在你的例子中，分成了 < 和 >= 两部分。
2,1,3,4,5,8,7,4,6 中，前三个元素 [2, 1, 3] 是 < 4 的；后五个元素[5, 8, 7, 4, 6] 是 >= 4 的。
双路快排保证的是，当有大量重复元素的时候，最终 pivot 的位置尽量靠中间，从而防止算法的退化。
继续加油！：）
0 -
xiaobai00000
提问者
2020-12-24
是不是 因为 最终会拆成 两个数 两两比较的原因呢。归并排序是 拆成最小粒度为2 的 两个数去比， 那么 快排 是不是可以拆最小粒度为3，按照双路的法则 排< = >
0h020-12-25
相似问题