C sort、stable_sort、nth_element全排序、保序与第 K 小怎么选需要最大值却先对整个数组排序能工作但做了多余的事情。排序相关算法各有承诺选择时先问结果究竟需要多有序最低标准C17。nth_element 的下标从 0 开始。1. 一个示例看三种不同目标#includealgorithm#includeiostream#includestring#includevectorstructTask{std::string name;intpriority;};intmain(){std::vectorintnumbers{9,1,7,3,5};autosortednumbers;std::sort(sorted.begin(),sorted.end());for(intn:sorted)std::coutn ;std::cout\n;conststd::size_t k2;if(knumbers.size()){std::nth_element(numbers.begin(),numbers.begin()k,numbers.end());std::coutnumbers[k]\n;}std::vectorTasktasks{{A,2},{B,1},{C,2}};std::stable_sort(tasks.begin(),tasks.end(),[](constTaska,constTaskb){returna.priorityb.priority;});for(constautotask:tasks)std::couttask.name ;std::cout\n;}输出依次是 1 3 5 7 9、5、B A C。最后 A 与 C 的优先级相同stable_sort 保留它们原来的先后顺序。2. sort需要完整顺序时使用std::sort 不保证等价元素维持输入顺序现代 C 标准要求其比较次数为 O(N log N) 量级。适合生成排行榜、展示有序列表或为后续多次二分查找准备数据。“等价”由比较器定义comp(a,b) 与 comp(b,a) 都为 false不一定要求 a b。3. stable_sort并列元素的原顺序也有意义例如输入顺序就是提交顺序希望同优先级任务继续先来先到就可以稳定排序。稳定性可能需要更多额外内存其复杂度还与可用额外存储有关不能简单把它理解成免费的 sort 升级版。4. nth_element只确定一个位置nth_element 让第 k 个位置得到完整排序后该位置的元素并把其余数据分到符合顺序关系的两侧。但两侧内部不保证排序因此不能把它的整个输出当成有序数组。普通非并行重载平均线性复杂度适合找中位数、阈值或第 K 小。口语里的“第 K 小”对应下标 K-1必须检查 K 至少为 1 且不超过元素数量。即便某些边界迭代器调用合法也不能解引用 end。若要排序后的前 K 项可考虑 partial_sort若只要最大或最小值则 max_element、min_element 更直接。选算法的诀窍是只购买自己真正需要的排序承诺。