C++ STL标准库这么多排序函数，该如何选择？

发布时间：2020-12-16 07:35:50 所属栏目：百科来源：网络整理

导读：通过前面的学习我们知道，C++ STL 标准库共提供了 4 种排序函数，这里先带大家回顾一下，如表 1 所示。表 1 C++ STL排序函数排序函数功能 sort() 对指定范围内所有的数据进行排序，排序后各个元素的相对位置很可能发生改变。 stable_sort() 对指定范围内所

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

表 1 C++ STL排序函数
排序函数	功能
sort()	对指定范围内所有的数据进行排序，排序后各个元素的相对位置很可能发生改变。
stable_sort()	对指定范围内所有的数据进行排序，并确保排序后各个元素的相对位置不发生改变。
partial_sort()	对指定范围内最大或最小的 n 个元素进行排序。
nth_element()	调整指定范围内元素的存储位置，实现位于位置 n 的元素正好是全排序情况下的第 n 个元素，并且按照全排序规则排在位置 n 之前的元素都在该位置之前，按照全排序规则排在位置 n 之后的元素都在该位置之后。

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

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

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

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

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

nth_element() > partial_sort() > sort() > stable_sort()? ? ? ?<--从左到右，性能由高到低

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!