You need to enable JavaScript to run this app. 3-way partitioning Quick sort是否为稳定的排序算法?
优惠活动
大模型
产品
解决方案
定价
更多

3-way partitioning Quick sort是否为稳定的排序算法?

3-way 快速排序的稳定性判定

经典原地实现的3-way分区快速排序,和2-way快排一样,不具备稳定排序的特性。
不少人第一次学3-way快排,会觉得它把和基准值相等的元素都归到中间段,总该比2-way快排稳定吧?这其实是个很常见的误解。
稳定排序的核心判定标准很简单:排序完成后,所有值相等的元素,在原数组中的相对先后顺序不能被打乱。而3-way快排的分区过程,是靠跨区间的元素交换完成的,这种没有保留原顺序上下文的交换操作,完全可能打乱同值元素的原有相对位置——它不稳定的本质原因,和2-way快排完全共通,和做几向分区没有直接关系。
我们可以用一个带顺序标记的小例子直观验证,比如原数组为:
[4ₐ, 2, 4ᵦ, 1]
这里两个值为4的元素,原本4ₐ排在4ᵦ前面,稳定排序必须保留这个先后关系。如果我们选数组开头的4ₐ当基准值做3-way分区:

  • 分区过程中遇到值为1的小于基准的元素,会把它换到数组前端的小值区块
  • 这次交换会直接跨过原本在基准位置的4ₐ,等整个分区流程走完,数组会变成[1, 2, 4ᵦ, 4ₐ]
    可以看到,原本在前的4ₐ被换到了4ᵦ的后面,同值元素的相对顺序已经被彻底打乱,自然不符合稳定排序的要求。
    补充两个容易混淆的点:
  • 只要是靠非相邻交换实现原地分区的快排,不管是2-way还是3-way,都没法保证稳定性。哪怕把等于基准的元素全堆到中间,交换过程中跨过同值元素的概率永远存在
  • 如果对3-way快排做改造:放弃原地交换的思路,遍历数组时用临时存储分别收集小于、等于、大于基准的元素,最后按顺序把三类元素拼接回原数组,这种非原地版本的3-way快排确实能做到稳定,但它的空间开销会从经典快排的O(log n)栈级开销涨到O(n),已经偏离了快排本身低空间开销的设计目标。我们日常讨论的3-way快排,默认都是原地版本,自然是不稳定的。

内容的提问来源于stack exchange,提问作者MJ1996

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.27 22:06:03