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

部份排序。

该函数等价于:

template<class _RanIt,
class _Ty,
class _Pr> inline
void _Partial_sort(_RanIt _First, _RanIt _Mid, _RanIt _Last,
    _Pr _Pred, _Ty *)
{    // order [_First, _Last) up to _Mid, using _Pred
    _STD make_heap(_First, _Mid, _Pred);
    for (_RanIt _Next = _Mid; _Next < _Last; ++_Next)
        if (_DEBUG_LT_PRED(_Pred, *_Next, *_First))
            {    // replace top with new largest
            _Ty _Val = _Move(*_Next);
            _Pop_heap(_First, _Mid, _Next, _Move(_Val), _Pred,
                _Dist_type(_First));
            }
    _STD sort_heap(_First, _Mid, _Pred);
}
  • firstlast

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

    middle

    指向范围 [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 PartialSort_1() {
            CLASSFOO_VECTOR(int, BigVector1, { 8, 23, -5, 7, 29, 0, 7, 7, -7, 1, -1 });
    
            // 使用 operator<
            std::partial_sort(
                std::begin(BigVector1),
                std::begin(BigVector1) + 5,
                std::end(BigVector1)
                );
            // 输出结果
            std::copy(
                BigVector1.begin(),
                BigVector1.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
    
            // 使用自定义函数
            std::partial_sort(
                std::begin(BigVector1),
                std::begin(BigVector1) + 5,
                std::end(BigVector1),
                IsGreater
                );
            // 输出结果
            std::copy(
                BigVector1.begin(),
                BigVector1.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
    
            // 使用函数对象
            std::partial_sort(
                std::begin(BigVector1),
                std::begin(BigVector1) + 5,
                std::end(BigVector1),
                IsLess
                );
            // 输出结果
            std::copy(
                BigVector1.begin(),
                BigVector1.end(),
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::PartialSort_1();
        return 0;
    }

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

    例 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 PartialSort_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::partial_sort(
                std::begin(NodeVector),
                std::begin(NodeVector) + 4,
                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::PartialSort_2();
        return 0;
    }

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

    例 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 PartialSort_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::partial_sort(
                BigVector.begin(),
                BigVector.begin() + 5,
                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::partial_sort(
                std::begin(NodeVector),
                std::begin(NodeVector) + 4,
                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::PartialSort_3();
        return 0;
    }

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

  • 复杂度

    O(n*log2(m))n 为 last first.mmiddle - first

    数据争用相关

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

    异常安全性相关

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

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