C++ STL该如何选择排序函数？

通过前面的学习我们知道，C++ STL 标准库共提供了 4 种排序函数，这里先带大家回顾一下，如表 1 所示。 

关于以上 4 种排序函数各自的用法，读者可阅读之前的文章，这里不再过多赘述。

值得一提的是，以上 4 种排序函数在使用时，都要求传入随机访问迭代器，因此这些函数都只适用于 array、vector、deque 以及普通数组。

当操作对象为 list 或者 forward_list 序列式容器时，其容器模板类中都提供有 sort() 排序方法，借助此方法即可实现对容器内部元素进行排序。其次，对关联式容器（包括哈希容器）进行排序是没有实际意义的，因为这类容器会根据既定的比较函数（和哈希函数）维护内部元素的存储位置。

那么，当需要对普通数组或者 array、vector 或者 deque 容器中的元素进行排序时，怎样选择最合适（效率最高）的排序函数呢？这里为大家总结了以下几点：

1. 如果需要对所有元素进行排序，则选择 sort() 或者 stable_sort() 函数；
2. 如果需要保持排序后各元素的相对位置不发生改变，就只能选择 stable_sort() 函数，而另外 3 个排序函数都无法保证这一点；
3. 如果需要对最大（或最小）的 n 个元素进行排序，则优先选择 partial_sort() 函数；
4. 如果只需要找到最大或最小的 n 个元素，但不要求对这 n 个元素进行排序，则优先选择 nth_element() 函数。

除此之外，很多读者都关心这些排序函数的性能。总的来说，函数功能越复杂，做的工作越多，它的性能就越低（主要体现在时间复杂度上）。对于以上 4 种排序函数，综合考虑它们的时间和空间效率，其性能之间的比较如下所示：

建议大家，在实际选择排序函数时，应更多从所需要完成的功能这一角度去考虑，而不是一味地追求函数的性能。换句话说，如果你选择的算法更有利于实现所需要的功能，不仅会使整个代码的逻辑更加清晰，还会达到事半功倍的效果。