一月#

PdqSort - Pattern-defeating Quicksort#

Date

2022-01-28

拜读了 👤 zhangyunhao116 写的 Go 泛型版本的 PdqSort 实现:⛺ zhangyunhao116/pdqsort。 PdqSort 是一种较先进的 unstable 的混合排序算法,在 Boost 和 Rust 中均有使用。

小规模数据

insertion sort

默认情况

改进的 quick sort

表现不好时

heap sort 以保证最坏的复杂度 \(O(n\log n)\)

改进的 quick sort#

选取 pivot

采样,取中位数

处理 common case
近似有序
衡量

取样判断是否近似有序(选取 pivot 时顺便做的)

策略

Partial insertion sort(改进的插入排序)

大量重复元素
衡量

Sub-array 之外左侧的值(肯定比 sub-array 里的值小)等于选中的 pivot

策略

提前将重复元素排在一起,避免下次选中其作为 pivot

抵抗 bad case
近似逆序时
衡量

取样判断是否近似有序

策略

反转数组

Pivot 表现不佳
衡量

上次 partition 的 pivot 的位置离 sub-array 两端很近

策略

Shuffle 若干元素,如果还是不佳,fallback 到 heap sort

评论

如果你有任何意见,请在此评论。 如果你留下了电子邮箱,我可能会通过 回复你。