Boost C++ 库

Boost 排序库的目标是为用户提供最现代、快速和内存高效的排序算法。

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

这些算法不使用任何其他库或实用程序，您只需要包含 boost/sort/sort.hpp 或更具体的头文件之一。并行算法需要符合 C++11 标准的编译器。

单线程算法

                  |       |                            |                                            | Comparison          |
Algorithm         |Stable |   Additional memory        |Best, average, and worst case               | method              |
------------------+-------+----------------------------+--------------------------------------------+---------------------+
spreadsort        |  no   |      key_length            | N, N sqrt(LogN), min(N logN, N key_length) | Hybrid radix sort   |
pdqsort           |  no   |      Log N                 | N, N LogN, N LogN                          | Comparison operator |
spinsort          |  yes  |      N / 2                 | N, N LogN, N LogN                          | Comparison operator |
flat_stable_sort  |  yes  |size of the data / 256 + 8K | N, N LogN, N LogN                          | Comparison operator |
                  |       |                            |                                            |                     |

• spreadsort 是一种极其快速的混合基数排序算法，由 Steven Ross 设计和开发。
• pdqsort 是对快速排序算法的改进，由 Orson Peters 设计和开发。
• spinsort 是一种稳定的排序算法，对于随机或接近有序的数据速度很快，由 Francisco Tapia 设计和开发。
• flat_stable_sort 是一种稳定的排序算法，使用非常少的额外内存（大约是数据大小的 1%），提供 spinsort 速度的 80% - 90%，由 Francisco Tapia 设计和开发。

并行算法

                      |       |                        |                              |
Algorithm             |Stable |   Additional memory    |Best, average, and worst case |
----------------------+-------+------------------------+------------------------------+
block_indirect_sort   |  no   |block_size * num_threads| N, N LogN , N LogN           |
sample_sort           |  yes  |        N               | N, N LogN , N LogN           |
parallel_stable_sort  |  yes  |      N / 2             | N, N LogN , N LogN           |
                      |       |                        |                              |

• Sample_sort 是由 Francisco Tapia 完成的 样本排序算法 的实现。
• Parallel_stable_sort 基于样本排序算法，但使用 sample_sort 一半的内存，由 Francisco Tapia 构思和实现。
• Block_indirect_sort 是一种新颖的高速并行排序算法，具有低额外内存消耗，由 Francisco Tapia 构思和实现。

块大小 (block_size) 是算法的内部参数，为了实现最高速度，它会根据要排序的对象的大小按照下表进行更改。字符串使用 128 的块大小。

                                |        |         |         |         |         |         |          |
object size (bytes)             | 1 - 15 | 16 - 31 | 32 - 63 | 64 - 127|128 - 255|256 - 511| 512 -    |
--------------------------------+--------+---------+---------+---------+---------+---------+----------+
block_size (number of elements) |  4096  |  2048   |   1024  |   768   |   512   |   256   |  128     |
                                |        |         |         |         |         |         |          |