Boost C++ 库

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

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

这些算法不使用任何其他库或实用程序，您只需要包含 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 完成的 Samplesort 算法 的实现。
• Parallel_stable_sort 基于 samplesort 算法，但仅使用 sample_sort 一半的内存，由 Francisco Tapia 构思和实现。
• Block_indirect_sort 是一种新型高速并行排序算法，具有低额外内存消耗，由 Francisco Tapia 构思和实现。

The block_size 是算法的内部参数，为了获得最高速度，它会根据要排序对象的大小进行更改，如下表所示。字符串使用 128 的 block_size。

                                |        |         |         |         |         |         |          |
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     |
                                |        |         |         |         |         |         |          |