STL partial_sort排序

STL partial_sort排序算法

C++ STL 中的 partial_sort() 函数用于从指定区域中提取出部分数据，并对它们进行排序，但 “部分排序” 仅仅是对 partial_sort() 函数功能的一个概括。

STL partial_sort函数详解

使用场景

假设这样一种情境，有一个存有 100 万个元素的容器，但我们只想从中提取出值最小的 10 个元素，该如何实现呢？

我们可能会想到使用 sort() 或者 stable_sort() 排序函数，即通过对容器中存储的 100 万个元素进行排序，就可以成功筛选出最小的 10 个元素。但仅仅为了提取 10 个元素，却要先对 100 万个元素进行排序，可想而知这种实现方式的效率是非常低的。

对于解决类似的问题，C++ STL 标准库提供了更高效的解决方案，即使用 partial_sort() 或者 partial_sort_copy() 函数。

头文件

#include <algorithm>

语法

//按照默认的升序排序规则，对 [first, last) 范围的数据进行筛选并排序
void partial_sort (RandomAccessIterator first,
                   RandomAccessIterator middle,
                   RandomAccessIterator last);
//按照 comp 排序规则，对 [first, last) 范围的数据进行筛选并排序
void partial_sort (RandomAccessIterator first,
                   RandomAccessIterator middle,
                   RandomAccessIterator last,
                   Compare comp);

参数

参数	描述
first	随机访问迭代器
middle	随机访问迭代器
comp	自定义排序规则

说明

partial_sort() 函数会以交换元素存储位置的方式实现部分排序的。具体来说，partial_sort() 会将 [first, last) 范围内最小（或最大）的 middle-first 个元素移动到 [first, middle) 区域中，并对这部分元素做升序（或降序）排序。

技术细节

需要注意的是，partial_sort() 函数受到底层实现方式的限制，它仅适用于普通数组和部分类型的容器。换句话说，只有普通数组和具备以下条件的容器，才能使用 partial_sort() 函数：

容器支持的迭代器类型必须为随机访问迭代器。这意味着，partial_sort() 函数只适用于 array、vector、deque 这 3 个容器。
当选用默认的升序排序规则时，容器中存储的元素类型必须支持 <小于运算符；同样，如果选用标准库提供的其它排序规则，元素类型也必须支持该规则底层实现所用的比较运算符；
partial_sort() 函数在实现过程中，需要交换某些元素的存储位置。因此，如果容器中存储的是自定义的类对象，则该类的内部必须提供移动构造函数和移动赋值运算符。

案例

STL partial_sort函数排序

使用 STL partial_sort 函数实现排序

#include <iostream>   
#include <algorithm>  
#include <vector>
using namespace std;
class mycomp
{
public:
    bool operator() (int i, int j) {
        return (i > j);
    }
};
int main() 
{
	cout << "嗨客网(www.haicoder.net)\n" << endl;
    vector<int> myvector{ 11, 22, 10, 100, 23, 89, 1024 };
    partial_sort(myvector.begin(), myvector.begin() + 4, myvector.end());
    cout << "第一次排序:\n";
    for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
    {
        std::cout << *it << ' ';
    }
    cout << "\n第二次排序:\n";
    std::partial_sort(myvector.begin(), myvector.begin() + 4, myvector.end(), mycomp());
    for (vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) 
    {
        cout << *it << ' ';
    }
    cout << endl;
    return 0;
}

我们在 Linux 下使用 g++ 进行编译，具体命令如下：

g++ partial_sort.cpp -std=c++11

编译后，我们直接运行生成的二进制文件 a.out，如下图所示：

03_STL partial_sort排序算法.png

可以看到，我们使用了 partial_sort 实现了排序。

STL partial_sort函数总结

C++ STL 中的 partial_sort() 函数用于从指定区域中提取出部分数据，并对它们进行排序，但 “部分排序” 仅仅是对 partial_sort() 函数功能的一个概括。