本次发布

spreadsort

作者

Peter Dimov

贡献者

Nigel Stewart

贡献者

Francisco Tapia

贡献者

依赖项

Config

Core

范围

Static Assert

Type Traits

Boost Sort Library 的目标是为用户提供最现代、最快的排序算法。

该库提供稳定和非稳定的排序算法，有单线程和并行版本。

这些算法不使用任何其他库或实用程序。并行算法需要一个符合 C++11 标准的编译器。

也可以获得详细的 Boost API 文档。

算法	稳定	额外的内存	最佳、平均和最坏情况	比较方法
spreadsort	否	键长	N, N sqrt(LogN),	混合基数排序
			min(N logN, N 键长)
pdqsort	否	Log N	N, N LogN, N LogN	比较运算符
spinsort	是	N / 2	N, N LogN, N LogN	比较运算符
flat_stable_sort	是	数据大小 / 256 + 8K	N, N LogN, N LogN	比较运算符

spreadsort 是一个由 Steven Ross 设计和开发的新颖的混合基数排序算法，速度极快。(论文)
pdqsort 是由 Orson Peters 设计和开发的快速排序算法的改进。(论文)
spinsort 是一个稳定的排序算法，对于随机数据和接近排序的数据都很快，由 Francisco Tapia 设计和开发。
flat_stable_sort 是一个稳定的排序算法，只需要少量的额外内存（约数据大小的 1%），速度可达到 spinsort 的 80% - 90%，对于随机数据和接近排序的数据都很快，由 Francisco Tapia 设计和开发。(论文)

算法	稳定	额外的内存	最佳、平均和最坏情况
block_indirect_sort	否	块大小 * 线程数	N, N LogN , N LogN
sample_sort	是	N	N, N LogN , N LogN
parallel_stable_sort	是	N / 2	N, N LogN , N LogN

Sample_sort 是由 Francisco Tapia 实现的 Samplesort 算法。
Parallel_stable_sort 基于 samplesort 算法，但使用了 sample_sort 一半的内存，由 Francisco Tapia 设计和实现。
Block_indirect_sort 是一个新颖的并行排序算法，速度非常快，内存消耗低，由 Francisco Tapia 设计和实现。(论文)

块大小 是算法的一个内部参数，为了达到最高速度，它会根据待排序对象的尺寸在下表中进行变化。字符串使用块大小 128。