我要评论std::partial_sort 是 c++ 标准库中的一个算法，它可以对容器中的一部分元素进行排序，使得前 n 个元素按顺序排列，而不保证剩余部分有序。它的时间复杂度为 o(n log n + (m-n))，其中 m 是整个范围的大小，n 是要排序的元素数量。
1. 语法
#include <algorithm> template< class randomit > void partial_sort( randomit first, randomit middle, randomit last ); template< class randomit, class compare > void partial_sort( randomit first, randomit middle, randomit last, compare comp );
first：要排序的范围的起始迭代器。middle：指定排序后的前n个元素的终点，即first + n。last：排序范围的结束迭代器。comp（可选）：自定义比较函数。
2. 基本用法
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {7, 3, 9, 1, 6, 2, 8, 5, 4};
// 仅对前 5 个元素排序
std::partial_sort(vec.begin(), vec.begin() + 5, vec.end());
// 输出前 5 个排序后的元素
std::cout << "前 5 个最小的元素: ";
for (int i = 0; i < 5; ++i) {
std::cout << vec[i] << " ";
}
std::cout << "\n";
// 输出整个数组
std::cout << "整个数组: ";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << "\n";
return 0;
}
输出
前 5 个最小的元素: 1 2 3 4 5
整个数组: 1 2 3 4 5 9 8 7 6
注意：前 5 个元素是有序的，但整个数组仍然是部分无序的。
3. 使用自定义比较函数
可以使用 std::greater<int>() 进行降序排序：
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec = {7, 3, 9, 1, 6, 2, 8, 5, 4};
// 获取前 5 个最大的元素（降序）
std::partial_sort(vec.begin(), vec.begin() + 5, vec.end(), std::greater<int>());
// 输出前 5 个排序后的元素
std::cout << "前 5 个最大的元素: ";
for (int i = 0; i < 5; ++i) {
std::cout << vec[i] << " ";
}
std::cout << "\n";
return 0;
}
输出
前 5 个最大的元素: 9 8 7 6 5
4. 与 std::sort 和 std::nth_element 的比较
| 算法 | 作用 | 复杂度 | 适用场景 |
|---|---|---|---|
| std::sort | 全部排序 | o(n log n) | 需要排序整个序列 |
| std::partial_sort | 仅保证前 n 个元素有序 | o(n log n + (m-n)) | 只需要最小/最大 n 个有序元素 |
| std::nth_element | 只保证 n 处的元素正确，左侧比它小，右侧比它大 | o(m) | 只需要找到第 n 小的元素，且不关心其他元素顺序 |
5. 适用场景
- 求前 k 个最小/最大值
- 数据流处理（流式计算）
- top-k 查询
- 快速获取排名前 n 的元素
到此这篇关于c++中std::partial_sort的使用小结的文章就介绍到这了,更多相关c++ std::partial_sort内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论