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

通过前面的学习我们知道,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 容器中的元素进行排序时,怎样选择最合适(效率最高)的排序函数呢?这里为大家总结了以下几点:
  1. 如果需要对所有元素进行排序,则选择 sort() 或者 stable_sort() 函数;
  2. 如果需要保持排序后各元素的相对位置不发生改变,就只能选择 stable_sort() 函数,而另外 3 个排序函数都无法保证这一点;
  3. 如果需要对最大(或最小)的 n 个元素进行排序,则优先选择 partial_sort() 函数;
  4. 如果只需要找到最大或最小的 n 个元素,但不要求对这 n 个元素进行排序,则优先选择 nth_element() 函数。

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

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

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