对于适用的数据类型，良好的基数排序可以大幅击败比较排序，但是std::sort通常作为 introsort 实现。有没有理由不使用基数排序来实现std::sort？基数排序不足以实现std::sort因为std::sort仅要求类型具有可比性，但对于比较和基于基数的排序产生相同答案的类型（例如int）这似乎是一个悬而未决的果实，没有被采摘。
实施是否合法std::sort在适当的时候使用基数排序的重载？有什么要求吗std::sort从根本上防止这种情况发生？
Edit:我应该更清楚一点。我问标准库的实现这样做是否合法。我并不是在询问标准库实现的用户将任何内容放入std命名空间。我知道，除特殊情况外，这样做是违法的。
评论引用了“假设”规则。这其实是没有必要的。std::sort未指定“如同使用 introsort”。规格为std::sort很简短，只需要效果（已排序）和比较次数的复杂性（O(N log N)）。基数排序满足两者。
25.4.1.1 排序
template<class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class
Compare> void sort(RandomAccessIterator first, RandomAccessIterator
last, Compare comp);
1 Effects：对[first,last)范围内的元素进行排序。
2 Requires：RandomAccessIterator 应满足 ValueSwappable (17.6.3.2) 的要求。 *first 的类型应满足 MoveConstructible（表 20）和 MoveAssignable（表 22）的要求。
3 复杂：O(N log(N )) （其中 N == 最后 - 第一个）比较。
在实践中，比较两个寄存器宽度值a<b即使我们使用位或十六进制数字，它也比提取数字并比较这些数字的序列要快得多。当然，这是一个常数因子差异，但提取和比较 32 个单独的位将比直接比较慢大约 100 倍。这击败了大多数理论上的担忧，特别是因为log N在今天的计算机上实际上不可能是 100。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
