cpp sort
1.16.0 — Taxonomics
如果只有一种或两种排序方法能够支配所有其他方法，无论使用什么应用程序或计算机，那就太好了。但事实上，每种方法都有其独特的优点。 [...] 因此，我们发现几乎所有的算法都值得被记住，因为在某些应用中它们被证明是最好的。 — Donald Knuth，《计算机编程艺术》，第 3 卷
cpp-sort是一个通用的 C++14 仅头文件排序库。它围绕一个主要的通用排序界面，并提供几个小工具来选择和/或设计排序算法。使用它的基本排序功能应该很简单：
# include < array >
# include < iostream >
# include < cpp-sort/sorters/smooth_sorter.h >
int main ()
{
std::array< int , 5 > arr = { 5 , 8 , 3 , 2 , 9 };
cppsort::smooth_sort (arr);
// prints 2 3 5 8 9
for ( int val: arr) {
std::cout << val << ' ' ;
}
}cpp-sort提供了一整套与排序相关的功能。以下是该库的主要构建块：
下面是一个更完整的示例，说明了可以使用该库完成哪些操作：
# include < algorithm >
# include < cassert >
# include < forward_list >
# include < functional >
# include < vector >
# include < cpp-sort/adapters.h >
# include < cpp-sort/sorters.h >
int main ()
{
struct wrapper { int value; };
std::forward_list<wrapper> li = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
std::vector<wrapper> vec = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
// When used, this sorter will use a pattern-defeating quicksort
// to sort random-access collections, and a mergesort otherwise
cppsort::hybrid_adapter<
cppsort::pdq_sorter,
cppsort::merge_sorter
> sorter;
// Sort li and vec in reverse order using their value member
sorter (li, std::greater<>{}, &wrapper::value);
sorter (vec, std::greater<>{}, &wrapper::value);
assert ( std::equal (
li. begin (), li. end (),
vec. begin (), vec. end (),
[]( const auto & lhs, const auto & rhs) { return lhs. value == rhs. value ; }
));
}即使在没有额外功能的情况下使用排序函数，它们仍然提供一些有趣的保证（通常取自 Ranges TS 的想法）：
iter_swap和iter_move正确处理代理迭代器operator()转换为函数指针您可以阅读有关所有可用工具的更多信息，并在 wiki 中找到一些有关使用和扩展cpp-sort 的教程。
下图是使用基准目录中的脚本生成的。它显示了heap_sort在不进行调整的情况下对一百万个元素进行排序所需的时间，以及使用drop_merge_adapter或split_adapter进行调整时所需的时间。
如上所示，使用任一适配器包装heap_sort使其能够以非侵入方式适应反转数量。用于适应它的算法有不同的优点和缺点，这取决于你使用哪一种。
这个基准主要是为了展示图书馆提供的可能性。您可以在专门的 wiki 页面中找到更多此类评论基准。
cpp-sort需要 C++14 支持，并且应与以下编译器配合使用：
/permissive- 。一些功能不可用。上面列出的编译器是 CI 管道使用的编译器，并且该库还定期使用这些编译器的最新版本进行测试。中间的所有其他编译器版本都未经测试，但也应该可以工作。如果情况并非如此，请随意提出问题。
库中的功能可能会有所不同，具体取决于所使用的 C++ 版本和启用的编译器扩展。这些更改记录在 wiki 中。
主存储库包含对 CMake 或 Conan 等标准工具的附加支持。您可以在 wiki 中阅读更多相关内容。
我有一辆新车。我只需要把它放在一起。它们更容易被一块一块地偷走。 — 贾罗德·金茨，3.33 美元
尽管该库的某些部分是原创研究，而其他部分则对应于标准排序算法的自定义且相当幼稚的实现， cpp-sort也重用了开源项目中的大量代码和想法，这些代码和想法通常经过修改以无缝集成到图书馆。以下是用于创建该库的外部资源的列表。我希望许多不同的许可证是兼容的。如果不是这种情况，请联系我（或提交问题），我们将看看可以采取什么措施：
insertion_sorter和pdq_sorter使用的一些算法来自 Orson Peters 的模式击败快速排序。基准测试的某些部分也来自那里。
tim_sorter使用的算法来自 Goro Fuji 的 Timsort 实现 (gfx)。
spread_sorter使用的三种算法来自Steven Ross Boost.Sort模块。
d_ary_spread_sorter使用的算法来自 Tim Blechmann 的 Boost.Heap 模块。
spin_sorter使用的算法来自 Boost.Sort 中实现的同名算法。作者：弗朗西斯科·何塞·塔皮亚。
utility::as_function 、 utility::static_const和几个投影增强辅助算法来自 Eric Niebler 的 Range v3 库。代理迭代器、定制点和投影等一些想法以及一些其他实用函数也来自该库或相关文章和标准 C++ 提案。
ska_sorter使用的算法来自 Malte Skarupke 对他自己的 ska_sort 算法的实现。
drop_merge_sorter使用的算法来自 Adrian Wielgosik C++ 对 Emil Ernerfeldt 的 drop-merge sort 的重新实现。
许多增强的标准算法直接改编自 libc++ 中的对应算法，并经过增强以处理投影和代理迭代器。
该库内部使用与前向迭代器一起使用的inplace_merge函数。它的实现使用了 Dudziński 和 Dydek 提出的合并算法，并由 Alexander Stepanov 和 Paul McJones 在他们的《编程元素》一书中实现。
当没有足够的内存来执行异地合并时，随机访问迭代器的inplace_merge重载使用 Pok-Son Kim 和 Arne Kutzner 在通过对称比较稳定最小存储合并中提出的Symmerge算法。
smooth_sorter使用的 Dijkstra 平滑排序的实现直接改编自 Keith Schwarz 的算法实现。
wiki_sorter使用的算法改编自 BonzaiThePenguin 的 WikiSort。
grail_sorter使用的算法改编自 Mrrl 的 GrailSort。
具有前向或双向迭代器的indirect_adapter使用的算法是Matthew Bentley 的indiesort 的稍微修改版本。
某些算法使用的nth_element随机访问重载的实现来自 Danila Kutenin 的 miniselect 库，并使用 Andrei Alexandrescu 的AdaptiveQuickselect算法。
sorting_network_sorter使用的排序网络都来自Bert Dobbelaere维护的这个列表。该页面引用了它列出的所有排序网络的来源。
sorting_network_sorter使用的一些优化来自 StackOverflow 上的讨论，并得到文章应用排序网络来综合优化排序库的支持。
该测试套件重新实现了最初在以下位置找到的随机数算法：
用于绘制排序网络的 LaTeX 脚本是 kaayy 的sortingnetwork.tex的修改版本，稍微修改为基于 0 并从上到下绘制网络。
项目中嵌入的 CMake 工具包括来自 RWTH-HPC/CMake-codecov 和 Crascit/DownloadProject 的脚本。
一些基准测试使用 Thøger Rivera-Thorsen 开发的色盲友好调色板。
