一月

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

评论

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