// <algorithm> 
// 默认(1)    
template <class RandomAccessIterator>
    void sort (RandomAccessIterator first,
        RandomAccessIterator last);
// 自定义(2)    
template <class RandomAccessIterator, class Compare>
    void sort (RandomAccessIterator first,
        RandomAccessIterator last, Compare comp);

排序元素。

该函数等价于:

template<class _RanIt,
class _Diff,
class _Pr> inline
void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal, _Pr _Pred)
{    // order [_First, _Last), using _Pred
    _Diff _Count;
    for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
    {    // divide and conquer by quicksort
        pair<_RanIt, _RanIt> _Mid =
            _Unguarded_partition(_First, _Last, _Pred);
        _Ideal /= 2, _Ideal += _Ideal / 2;    // allow 1.5 log2(N) divisions

        if (_Mid.first - _First < _Last - _Mid.second)
            {    // loop on second half
            _Sort(_First, _Mid.first, _Ideal, _Pred);
            _First = _Mid.second;
            }
        else
            {    // loop on first half
            _Sort(_Mid.second, _Last, _Ideal, _Pred);
            _Last = _Mid.first;
            }
    }

    if (_ISORT_MAX < _Count)
        {    // heap sort if too many divisions
        _STD make_heap(_First, _Last, _Pred);
        _STD sort_heap(_First, _Last, _Pred);
        }
    else if (1 < _Count)
        _Insertion_sort(_First, _Last, _Pred);    // small
}
  • firstlast

    分别指向被排序序列中初始及末尾位置的随机访问迭代器(Random-access Iterators)。这个范围即 [first,last) ,包括 first 到 last 间的所有元素,包括 first 指向的元素,但不包括 last 指向的元素。

    comp

    二元谓词(Binary)函数,以两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • 无。

  • 例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
    
    namespace ClassFoo{
        bool IsGreater(int m, int n) {
            return m > n;
        }
        struct _IsLess{
            bool operator()(int m, int n) {
                return m < n;
            }
        }IsLess;
        void Sort_1() {
            CLASSFOO_VECTOR(int, BigVector1, { 8, 23, -5, 7, 29, 0, 7, 7, -7, 1, -1 });
    
            // 使用 operator<
            std::sort(
                std::begin(BigVector1),
                std::end(BigVector1)
                );
            // 输出结果
            std::copy(
                BigVector1.begin(),
                BigVector1.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
    
            // 使用自定义函数
            std::sort(
                std::begin(BigVector1),
                std::end(BigVector1),
                IsGreater
                );
            // 输出结果
            std::copy(
                BigVector1.begin(),
                BigVector1.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
    
            // 使用函数对象
            std::sort(
                std::begin(BigVector1),
                std::end(BigVector1),
                IsLess
                );
            // 输出结果
            std::copy(
                BigVector1.begin(),
                BigVector1.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::Sort_1();
        return 0;
    }

    -7 -5 -1 0 1 7 7 7 8 23 29
    29 23 8 7 7 7 1 0 -1 -5 -7
    -7 -5 -1 0 1 7 7 7 8 23 29 

    例 2

    排序对象数组

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    namespace ClassFoo{
        class Node{
        public:
            Node(int m, int n) : x(m), y(n) {}
            int x;
            int y;
        };
        std::ostream& operator<<(std::ostream& o, Node& a) {
            o << "(" << a.x << "," << a.y << ")";
            return o;
        }
        bool MyNodeLessFunc(Node& a, Node& b) {
            if (a.x == b.x)
                return a.y < b.y;
            return a.x < b.x;
        }
        void Sort_2() {
            // 初始化对象数组
            std::vector<Node> NodeVector;
            NodeVector.push_back(Node(3, 7));
            NodeVector.push_back(Node(1, 9));
            NodeVector.push_back(Node(1, 3));
            NodeVector.push_back(Node(6, 3));
            NodeVector.push_back(Node(7, 2));
            NodeVector.push_back(Node(6, 2));
    
            // 排序
            std::sort(
                std::begin(NodeVector),
                std::end(NodeVector),
                MyNodeLessFunc
                );
            // 输出
            for (std::vector<Node>::iterator it = NodeVector.begin();
                it != NodeVector.end(); ++it) {
                std::cout << *it << " ";
            }
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::Sort_2();
        return 0;
    }

    (1,3) (1,9) (3,7) (6,2) (6,3) (7,2) 

    例 3

    C++11

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    namespace ClassFoo{
        class Node{
        public:
            Node(int m, int n) : x(m), y(n) {}
            int x;
            int y;
        };
        std::ostream& operator<<(std::ostream& o, Node& a) {
            o << "(" << a.x << "," << a.y << ")";
            return o;
        }
    
        void Sort_3() {
            // 初始化整数数组
            std::vector<int> BigVector = { 8, 23, -5, 7, 29, 0, 7, 7, -7, 1, -1 };
            // 初始化对象数组
            std::vector<Node> NodeVector = { {3, 7}, {1, 9}, {1, 3}, {6, 3}, {7, 2}, {6, 2} };
    
            // 排序整数数组
            // 按从大到小排序
            std::sort(
                BigVector.begin(),
                BigVector.end(),
                [](int m, int n) { return m > n; }
            );
            // 输出结果
            std::copy(
                BigVector.begin(),
                BigVector.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
    
            // 排序对象数组
            std::sort(
                std::begin(NodeVector),
                std::end(NodeVector),
                [](Node& a, Node& b) {
                    if (a.x == b.x)
                        return a.y < b.y;
                    return a.x < b.x;
                }
            );
            // 输出
            for (std::vector<Node>::iterator it = NodeVector.begin();
                it != NodeVector.end(); ++it) {
                std::cout << *it << " ";
            }
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::Sort_3();
        return 0;
    }

    29 23 8 7 7 7 1 0 -1 -5 -7
    (1,3) (1,9) (3,7) (6,2) (6,3) (7,2) 

  • 复杂度

    O(n*log2(n))n 为 last first.

    数据争用相关

    范围 [first,last) 中的所有元素都有可能被修改过。

    异常安全性相关

    如果元素比较(Compare)、元素交换(Swap)、元素移动(Move)或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)