按年被提到
20212023 · 2 次2026
算法与数据结构›经典算法与数据结构·arXiv:2106.05123 · cs.DS

Pattern-defeating Quicksort

模式击败快速排序(Pattern-defeating Quicksort)
Orson R. L. Peters · 2021

对已排序、重复元素多等输入自适应提速的混合快速排序

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2021-07-18 · 最近 2023-06-13
3不同的人
3活跃月份
3讨论串
18被引(OpenAlex)

论文提出一种不需要三路比较的荷兰国旗问题新解法,使含 k 个不同元素的输入有 O(nk) 的最坏情况运行时间。结合其他已知与新的技术,构成一种混合排序(pdqsort),它不会显著慢于普通快速排序,而在许多输入分布上大幅加速。

HN 为什么提它

评论者把 pdqsort 当作比标准库 std::sort 更快的常用替代实现来提,并强调它对已排序和有规律输入的适应性。

方法难度 3 / 5约 40 分钟经得起时间
读之前最好知道
1快速排序(quicksort)
2荷兰国旗问题(Dutch national flag problem)
3比较排序与大 O 记号

学习路径

读这篇之前,按顺序读书架上的 1 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

只有一篇候选与目标直接相关:BlockQuicksort 解决分支预测失败,pdqsort 在其基础上扩展,所以先读它。

  1. 1
    BlockQuicksort: How Branch Mispredictions don't affect QuicksortBlockQuicksort:分支预测失败如何不再影响快速排序 · 2016

    pdqsort 的划分步骤借用了它的分块缓冲思想,以减少分支预测失败。

    读分块比较并缓冲结果的划分方法,以及为何能避免分支预测失败。

  2. 2
    Pattern-defeating Quicksort模式击败快速排序(Pattern-defeating Quicksort) · 2021 · 就是这篇

    目标论文:在快速排序上加入荷兰国旗新解法等技术,适应各种输入分布。

    读重复元素的划分、对已排序和模式输入的检测,以及最坏情况回退到堆排序。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用nightcracker · 2021-07

“I've long since implemented that in pdqsort [2], along with other techniques described by me in [3]”

说自己早已在 pdqsort 中实现了该技术
Do Low-Level Optimizations Matter? (2020)原评论 ↗
引用sanxiyn · 2023-05

“pdqsort (for pattern-defeating quicksort) Pattern-defeating Quicksort is also popular.”

补充提到 pdqsort 也很流行
Ask HN: What is new in Algorithms / Data Structures these days?原评论 ↗
引用mlochbaum · 2023-06

“pdqsort paper: Pattern-defeating Quicksort”

贴出 pdqsort 论文
10~17x faster than what? A performance analysis of Intel x86-SIMD-sort (AVX-512)原评论 ↗