C++中的std::sort
是STL提供的快速排序实现,具有高效(平均O(n log n))、泛型(支持自定义比较函数)和原地排序(不额外占用内存)三大核心优势。以下是其关键特性解析:
-
高效排序算法
std::sort
采用混合排序策略:对小规模数据使用插入排序,大规模数据递归应用快速排序,并在递归深度过深时切换为堆排序以避免最坏情况下的O(n²)时间复杂度。 -
泛型容器支持
可对vector
、deque
等随机访问容器排序,通过迭代器指定范围。例如:cppCopy Code
std::sort(v.begin(), v.end()); // 默认升序
-
灵活的比较逻辑
支持lambda表达式或函数对象自定义排序规则:cppCopy Code
std::sort(v.begin(), v.end(), [](int a, int b){ return a > b; }); // 降序
-
稳定性与优化
非稳定排序(相同元素可能变序),需稳定排序时可选用std::stable_sort
;针对部分有序序列,std::sort
会通过自适应优化减少操作次数。
提示:对基本类型排序时,内置比较器效率最高;复杂对象建议传递引用避免拷贝开销。