algorithm - 3路分区快速排序稳定吗？

Question

我是来自韩国的中学生。

我知道 2 路分区快速排序不稳定。

三路快速排序怎么样？这是一个稳定的排序算法吗？

标签： algorithmsorting

Answer 1

不，三向快速排序也不稳定。

例如，如果arr[i]>pivot and arr[j]<pivot，那么这些值将被交换，下一个比较将是arr[i+1]和arr[j-1]。现在如果arr[i]==arr[i+1]，那么我们发现在交换之后，这两个值的顺序已经颠倒了。

3-way 算法仅对等于主元的值进行不同处理，但对于不同于主元的值（如上例），算法保持不变，因此该算法不提供稳定的排序.