企业官网建设流程全解析

前言

std::partial_sort解决的是「只要前 K 个,而且这 K 个要有序」的问题。它把区间重排成两部分:[first, middle)存放整个区间中最小的middle - first个元素,并且按升序排列;[middle, last)存放其余元素,顺序未指定。如果 K 接近 N,它退化为一次完整排序;如果 K 远小于 N,它比「全部排序再取前 K 个」更省。

最常见的误解是以为[middle, last)也会被排好序。标准只保证前半部分有序,后半部分「未指定」——不是「保持原顺序」,也不是「降序」,而是实现可以任意摆放。依赖后半部分顺序的代码,在不同标准库实现或不同数据下会得到不同结果。

第二个误解是把middle当成「第 K 个元素的下标」并写成begin() + k - 1。middle是一个尾后位置,表示「有序前缀的结束」,所以要取前 K 个就写begin() + k。当k == 0时middle == first,函数什么也不做;当k == N时middle == last,等价于std::sort。

第三个误解是认为它稳定。std::partial_sort不保证相等元素的相对顺序,和std::sort一样。需要稳定时,要么在比较器里加入能区分元素的次关键字,要么改用std::stable_sort并对整体排序。

本文讲清它的语义、复杂度、与nth_element/ 优先队列的取舍,并给出完整示例与常见坑点。示例以 C++17 为基准。

一、函数签名与语义

<algorithm>中提供两个重载:

// 适用于 C++17
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、last是随机访问迭代器,且满足first <= middle <= last。若middle不在这个范围内,行为未定义(undefined behavior, UB)。这一点和很多算法不同:它不会在运行时检查,传错就是 UB,可能越界写。

默认版本用operator<比较,把较小的元素放在前面;传入comp后,「较小」由comp定义。若comp是std::greater<>,排在前面的就是最大的 K 个,并按降序排列。

复杂度约为 O(N log K):需要对每个元素与当前前缀的最大值比较,必要时替换并调整堆。标准没有规定具体常数,也不保证某种实现策略,但复杂度上界是明确的。

二、与相关算法的取舍

如果只需要「前 K 个是谁」而不要求它们有序,std::nth_element更合适:它把第 K 个位置放上正确的元素,并保证左边的都不大于它、右边的都不小于它,平均复杂度 O(N),但不保证两侧内部有序。需要前缀有序时,再对[first, first + k)调用一次std::sort,总代价仍是 O(N + K log K),在 K 较小时通常比partial_sort的直接实现更省。

如果数据是流式的、事先不知道总量,或者需要在线维护前 K 个,用大小为 K 的最大堆(std::priority_queue)逐个处理,复杂度 O(N log K),内存 O(K)。这与partial_sort的复杂度同阶,但不需要把全部数据放进内存。

如果需要完整排序,直接用std::sort。partial_sort在 K 接近 N 时并没有优势,反而多了一层不必要的逻辑。

三、partial_sort_copy

partial_sort_copy(first, last, d_first, d_last)把源区间中最小的若干个元素复制到目标区间,目标区间能放多少就复制多少,返回指向目标区间中「最后一个被复制元素之后」的迭代器。它不修改源区间,适合源数据需要保留的场景。

目标区间的大小决定了实际复制多少个元素:若目标容量小于源长度,复制目标容量个;若目标容量大于源长度,只复制源长度个,剩余位置不动。返回值可以用于确定有效范围,不要假设目标区间一定被填满。

同样有带comp的重载。它要求源区间是输入迭代器即可,目标区间是随机访问迭代器。

四、完整示例

下面的示例演示三件事:取最小的 K 个并排序、取最大的 K 个、以及用partial_sort_copy保留原数据。

// 适用于 C++17
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <vector>

void print(const std::vector<int>& v) {
for (int x : v) {
std::cout << x << ' ';
}
std::cout << '\n';
}

int main() {
const std::vector<int> original{9, 1, 8, 2, 7, 3, 6, 4, 5, 0};
const std::size_t k = 4;

// 取最小的 4 个,并让这 4 个升序
std::vector<int> v1 = original;
std::partial_sort(v1.begin(), v1.begin() + k, v1.end());
print(v1); // 前四个为 0 1 2 3,其余顺序未指定

// 取最大的 4 个,并让这 4 个降序
std::vector<int> v2 = original;
std::partial_sort(v2.begin(), v2.begin() + k, v2.end(),
std::greater<int>());
print(v2); // 前四个为 9 8 7 6

// 不修改源数据,复制最小的 4 个到目标区间
std::vector<int> out(k);
const auto end = std::partial_sort_copy(
original.begin(), original.end(), out.begin(), out.end());
std::cout << "copied " << (end - out.begin()) << " elements: ";
print(out); // 0 1 2 3

// k 等于 0:middle == first,不做任何事
std::vector<int> v3 = original;
std::partial_sort(v3.begin(), v3.begin(), v3.end());
print(v3); // 原样

// k 等于 N:等价于完整排序
std::vector<int> v4 = original;
std::partial_sort(v4.begin(), v4.end(), v4.end());
print(v4); // 0 1 2 3 4 5 6 7 8 9

// 自定义比较器:按绝对值排序取前 4 个
std::vector<int> v5{-5, 2, -1, 4, -3, 0};
std::partial_sort(v5.begin(), v5.begin() + 4, v5.end(),
[](int a, int b) {
return std::abs(a) < std::abs(b);
});
print(v5);
return 0;
}

按标准语义推演:第一组前四个是 0、1、2、3;第二组用greater后前四个是 9、8、7、6;partial_sort_copy返回out.begin() + 4,输出 0、1、2、3;k == 0时容器不变;k == N时输出完整升序;绝对值比较器使用std::abs(int),对应的整数重载由<cstdlib>提供。以上只按算法语义推导,未经编译运行核对。

常见坑点

一、以为后半部分也有序

❌ 调用partial_sort后遍历整个容器,期望得到完整升序。

✅ 只有[first, middle)有序;要完整排序用std::sort,要前 K 个就只读前 K 个。

二、middle写成begin() + k - 1

❌std::partial_sort(v.begin(), v.begin() + k - 1, v.end());只排出前 K-1 个,且k == 0时下标下溢。

✅middle是尾后位置,写v.begin() + k;先确认k <= v.size()。

三、k大于容器长度

❌v.begin() + k越过end(),middle不在[first, last]内,是 UB。

✅ 先k = std::min(k, v.size()),再调用;或者提前返回。

四、求最大 K 个却忘了比较器

❌ 直接调用默认版本,得到的是最小的 K 个。

✅ 传std::greater<int>()(或std::greater<>());注意此时前缀是降序。

五、期望算法稳定

❌ 依赖相等元素在结果中的先后顺序与输入一致。

✅partial_sort不保证稳定;在比较器中加入学号、下标等次关键字,或改用std::stable_sort。

六、只求无序的前 K 个却用了partial_sort

❌ 每个元素都维护有序前缀,做了不必要的工作。

✅ 用std::nth_element,平均 O(N);确需有序时再对前 K 个排序。

七、传给非随机访问迭代器

❌ 对std::list调用partial_sort,编译失败。

✅ 先复制到std::vector,或改用支持双向迭代器的算法;std::list自身提供sort成员。

八、忽略partial_sort_copy的返回值

❌ 假设目标区间一定被填满,读取未写入的位置。

✅ 用返回的迭代器确定有效范围;目标容量小于源长度时只复制容量个元素。

总结

std::partial_sort的语义可以用一句话概括:前 K 个一定对,后 N-K 个不要看。把middle的尾后语义、降序要传greater、以及不稳定性这三点记住,再根据「要不要有序」「要不要保留原数据」「数据是不是流式」选择算法,就不会用错。