STL partial_sort_copy排序

STL partial_sort_copy排序算法

C++ STL 中的 partial_sort_copy() 函数的功能和 partial_sort() 类似，唯一的区别在于，前者不会对原有数据做任何变动，而是先将选定的部分元素拷贝到另外指定的数组或容器中，然后再对这部分元素进行排序。

STL partial_sort_copy函数详解

头文件

#include <algorithm>

语法

//默认以升序规则进行部分排序
RandomAccessIterator partial_sort_copy (
                       InputIterator first,
                       InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last);
//以 comp 规则进行部分排序
RandomAccessIterator partial_sort_copy (
                       InputIterator first,
                       InputIterator last,
                       RandomAccessIterator result_first,
                       RandomAccessIterator result_last,
                       Compare comp);

参数

参数	描述
first	输入迭代器
last	输入迭代器
result_first	随机访问迭代器
result_last	随机访问迭代器
comp	自定义排序规则

说明

partial_sort_copy() 函数会将 [first, last) 范围内最小（或最大）的 result_last-result_first 个元素复制到 [result_first, result_last) 区域中，并对该区域的元素做升序（或降序）排序。

值得一提的是，[first, last] 中的这 2 个迭代器类型仅限定为输入迭代器，这意味着相比 partial_sort() 函数，partial_sort_copy() 函数放宽了对存储原有数据的容器类型的限制。换句话说，partial_sort_copy() 函数还支持对 list 容器或者 forward_list 容器中存储的元素进行“部分排序”，而 partial_sort() 函数不行。

但是，介于 result_first 和 result_last 仍为随机访问迭代器，因此 [result_first, result_last) 指定的区域仍仅限于普通数组和部分类型的容器，这和 partial_sort() 函数对容器的要求是一样的。

案例

STL partial_sort_copy函数排序

使用 STL partial_sort_copy 函数实现排序

#include <iostream>   
#include <algorithm>  
#include <list>
using namespace std;
class mycomp
{
public:
    bool operator() (int i, int j) {
        return (i > j);
    }
};
int main() 
{
	cout << "嗨客网(www.haicoder.net)\n" << endl;
    int myints[5] = { 0 };
    std::list<int> mylist{ 11, 22, 10, 100, 23, 89, 1024 };
    partial_sort_copy(mylist.begin(), mylist.end(), myints, myints + 5);
    cout << "第一次排序：\n";
    for (int i = 0; i < 5; i++) 
    {
        cout << myints[i] << " ";
    }
    std::partial_sort_copy(mylist.begin(), mylist.end(), myints, myints + 5, mycomp());
    cout << "\n第二次排序：\n";
    for (int i = 0; i < 5; i++)
    {
        cout << myints[i] << " ";
    }
    cout << endl;
    return 0;
}

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

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

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

可以看到，程序中调用了 2 次 partial_sort_copy() 函数，其作用分别是：采用默认的升序排序规则，在 mylist 容器中筛选出最小的 5 个元素，然后将它们复制到 myints[5] 数组中，并对这部分元素进行升序排序。

采用自定义的 mycomp 降序排序规则，从 mylist 容器筛选出最大的 5 个元素，同样将它们复制到 myints[5] 数组中，并对这部分元素进行降序排序；

STL partial_sort_copy函数总结

C++ STL 中的 partial_sort_copy() 函数的功能和 partial_sort() 类似，唯一的区别在于，前者不会对原有数据做任何变动，而是先将选定的部分元素拷贝到另外指定的数组或容器中，然后再对这部分元素进行排序。