破坏模式的快速排序。
pdqsort-------
Pattern-defeating quicksort (pdqsort) 是一种新的排序算法,它将随机快速排序的快速平均情况与堆排序的快速最坏情况相结合,同时在具有特定模式的输入上实现线性时间。pdqsort 是 David Mussers introsort 的扩展和改进。所有代码均可免费使用 zlib 许可证。
pdqsort 是 std::sort 的替代方案。只需将调用 std::sort 替换为 pdqsort，即可开始使用避免模式的快速排序。如果您的比较函数是无分支的，则可以调用 pdqsort_branchless，以实现潜在的大幅加速。如果您使用的是 C++11，则您正在排序的类型是算术类型，且您的比较函数未给出或为 std::less/std::greater，则 pdqsort 会自动委托给 pdqsort_branchless。
以下是使用 Timo Bingmann 的 The Sound of Sorting 程序生成的图像,该程序在 pdqsort 的开发过程中非常有用。为了制作此图像,插入排序的截止点被降低到 8 个元素。
对于相等的元素,使用了一个智能划分方案,该方案总是将相等的元素放入比中枢大的分区中。当选择新的中枢时,它会与之前分区中的最大元素进行比较。如果它们比较相等,
暂无开放 Issues，或尚未同步最近议题。