一月#
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
评论
如果你有任何意见，请在此评论。 如果你留下了电子邮箱，我可能会通过 回复你。